함수형 프로그래밍-재귀를 많이 강조하는 이유는 무엇입니까?

함수형 프로그래밍-재귀를 많이 강조하는 이유는 무엇입니까?

---

함수형 프로그래밍 [FP] (Scala 사용)에 대해 소개 받고 있습니다. 내 초기 학습에서 나온 한 가지는 FP가 재귀에 크게 의존한다는 것입니다. 또한 순수 FP에서 반복적 인 작업을 수행하는 유일한 방법은 재귀 함수를 작성 하는 것 같습니다 .

그리고 재귀를 많이 사용하기 때문에 FP가 걱정해야 할 다음 일은 StackoverflowExceptions일반적으로 긴 감기 재귀 호출 때문인 것 같습니다 . 이것은 몇 가지 최적화를 도입하여 해결되었습니다 ( @tailrecScala v2.8 이후 의 스택 프레임 및 주석 유지 관리에서 꼬리 재귀 관련 최적화 ).

함수형 프로그래밍 패러다임에서 재귀가 왜 그렇게 중요한지 누군가 제게 알려 주실 수 있습니까? 함수형 프로그래밍 언어의 사양에 우리가 반복적으로 작업을하면 "위반"되는 것이 있습니까? 그렇다면 저도 알고 싶습니다.

추신 : 나는 함수형 프로그래밍에 초보자이므로 내 질문에 대해 설명 / 답변하면 기존 리소스를 알려주십시오. 또한 특히 Scala가 반복적 인 작업을 지원한다는 것을 이해합니다.

---

Church Turing 논문 은 다른 계산 가능성 모델 간의 동등성을 강조합니다.

재귀를 사용하면 문제 를 해결 하는 동안 변경 가능한 상태 가 필요하지 않으므로 더 간단한 용어로 의미 체계를 지정할 수 있습니다. 따라서 공식적인 의미에서 솔루션은 더 간단 할 수 있습니다.

Prolog는 기능적 언어보다 재귀의 효과 (반복이 없음)와 사용시 발생하는 실질적인 한계를 더 잘 보여준다고 생각합니다.

---

순수 함수형 프로그래밍은 부작용없는 프로그래밍을 의미합니다. 즉, 예를 들어 루프를 작성하면 루프 본문이 부작용을 생성 할 수 없습니다. 따라서 루프에서 무언가를 수행하려면 이전 반복의 결과를 재사용하고 다음 반복을 위해 무언가를 생성해야합니다. 따라서 루프의 본문은 이전 실행의 결과를 매개 변수로 취하고 자체 결과로 다음 반복을 위해 자신을 호출하는 함수입니다. 이것은 루프에 대한 재귀 함수를 직접 작성하는 것보다 큰 이점이 없습니다.

사소한 일을하지 않는 프로그램은 어떤 시점에서 무언가를 반복해야합니다. 함수형 프로그래밍의 경우 이는 프로그램이 재귀 함수를 사용해야 함을 의미합니다.

---

재귀 적으로 작업을 수행해야하는 요구 사항 을 가져 오는 기능 은 불변 변수입니다.

(의사 코드에서) 목록의 합계를 계산하는 간단한 함수를 고려하십시오.

fun calculateSum(list):
    sum = 0
    for each element in list: # dubious
        sum = sum + element # impossible!
    return sum

이제 element목록의 각 반복마다 다르지만 foreach람다 인수가 있는 함수 를 사용 하여이 문제를 제거 하도록 다시 작성할 수 있습니다 .

fun calculateSum(list):
    sum = 0
    foreach(list, lambda element:
        sum = sum + element # impossible!
    )
    return sum

그래도 sum변수 의 값은 람다를 실행할 때마다 변경되어야합니다. 이것은 변경 불가능한 변수를 가진 언어에서는 불법이므로 상태를 변경하지 않는 방식으로 다시 작성해야합니다.

fun calculateSum([H|T]):
    return H + calculateSum(T)

fun calculateSum([]):
    return 0

이제이 구현은 호출 스택에서 많이 푸시하고 팝해야하며 모든 작은 작업이이를 수행하는 프로그램은 매우 빠르게 실행되지 않습니다. 따라서 우리는이를 테일 재귀 적으로 다시 작성하므로 컴파일러는 테일 호출 최적화를 수행 할 수 있습니다.

fun calculateSum([H|T], partialSum):
    return calculateSum(T, H + partialSum)

fun calculateSum([], partialSum):
    return partialSum

fun calculateSum(list):
    return calculateSum(list, 0)

물론 무한 반복을 원할 경우 반드시 꼬리 재귀 호출이 필요합니다. 그렇지 않으면 스택 오버플로가 발생합니다.

@tailrecScala 의 주석은 꼬리 재귀 함수를 분석하는 데 도움이되는 도구입니다. "이 함수는 꼬리 재귀 적입니다"라고 주장하면 컴파일러가 실수인지 알려줄 수 있습니다. 이것은 스칼라에서 실행되는 머신 인 JVM이 테일 호출 최적화를 잘 지원하지 않기 때문에 다른 기능 언어와 비교하여 스칼라에서 특히 중요합니다. 따라서 스칼라에서 얻을 수있는 모든 동일한 상황에서 테일 호출 최적화를 얻을 수 없습니다. 다른 기능 언어로.

---

TL은, DR : 재귀 유도 정의 데이터를 처리하는 데 사용 되어 편재한다.

더 높은 수준의 추상화에서 작업 할 때 재귀는 자연 스럽습니다. 함수형 프로그래밍은 단순히 함수로 코딩하는 것이 아닙니다. 그것은 자연스럽게 기능을 사용하는 더 높은 수준의 추상화에서 작동하는 것입니다. 함수를 사용하면 의미가있는 컨텍스트에서 동일한 함수를 재사용 (다시 호출하기 위해)하는 것은 당연합니다.

세계는 유사하거나 동일한 빌딩 블록의 반복으로 구축됩니다. 천 조각을 두 개로 자르면 두 조각의 천이 있습니다. 수학적 귀납법은 수학의 핵심입니다. 우리, 인간, 카운트 (1, 2,3 ... ). 귀납적으로 정의 된 모든 것 (예 : {numbers from 1}은 {1 , numbers from 2} )은 해당 사물이 정의 / 구성되는 동일한 경우에 따라 재귀 함수로 처리 / 분석하는 것이 당연합니다.

재귀는 어디에나 있습니다. 반복 루프는 어쨌든 변장의 재귀입니다. 왜냐하면 해당 루프를 다시 입력 하면 동일한 루프를 다시 입력하기 때문입니다 (다른 루프 변수를 사용하여). 따라서 컴퓨팅에 대한 새로운 개념을 발명 하는 것이 아니라 기초를 발견 하고이를 명시 적으로 만드는 것과 같습니다 .

---

따라서 재귀는 자연 스럽습니다. 우리는 문제에 대한 몇 가지 법칙, 정의하고있는 함수와 관련된 몇 가지 방정식을 작성하여 일부 불변성을 보존하고 (함수가 일관되게 정의된다는 가정하에) 문제를 단순화 된 용어로 다시 지정하고 짜잔! 해결책이 있습니다.

예를 들어, 목록의 길이를 계산하는 함수 (유도 적으로 정의 된 재귀 데이터 유형). 정의되어 있다고 가정하고 놀랍지 않게 목록의 길이를 반환합니다. 준수해야하는 법은 무엇입니까? 문제의 단순화에 따라 어떤 불변이 보존됩니까?

가장 즉각적인 것은 목록을 헤드 요소로 분리하고 나머지는 목록의 꼬리 (목록 정의 / 구성 방법에 따라)입니다. 법은

length (x:xs) = 1 + length xs

어! 하지만 빈 목록은 어떻습니까? 그것은 틀림 없다

length [] = 0

그래서 우리는 어떻게 그런 함수를 작성합니까? ... 잠깐 ... 우리는 이미 작성했습니다! (Haskell에서 함수 응용 프로그램이 병치로 표현되는 곳이 궁금하다면 괄호는 그룹화에만 사용 되며 첫 번째 요소와 나머지 요소 (x:xs)가있는 목록입니다 ).xxs

이러한 스타일의 프로그래밍을 허용하기 위해 필요한 언어는 TCO (그리고 약간 고급 스럽게도 TRMCO )가 있기 때문에 스택 폭발이없고 준비가 완료되었습니다.

---

또 다른 것은 순수성-코드 변수 및 / 또는 데이터 구조 (레코드의 필드 등)의 불변성입니다.

그것은 우리의 마음이 언제 무엇이 변하는 지 추적 할 필요가 없도록하는 것 외에도, "변경되는"가변 변수 / 데이터에 숨기는 대신 코드에서 시간을 명시 적으로 명백하게하는 것입니다. 명령형 코드 에서 지금부터 변수의 값만 "변경" 할 수 있습니다. 과거에는 그 값을 잘 변경할 수 없었습니다.

And so we end up with lists of recorded change history, with change explicitly apparent in the code: instead of x := x + 2 we write let x2 = x1 + 2. It makes reasoning about code so much easier.

---

To address immutability in the context of tail recursion with TCO, consider this tail recursive re-write of the above function length under accumulator argument paradigm:

length xs = length2 0 xs              -- the invariant: 
length2 a []     = a                  --     1st arg plus
length2 a (x:xs) = length2 (a+1) xs   --     length of 2nd arg

Here TCO means call frame reuse, in addition to the direct jump, and so the call chain for length [1,2,3] can be seen as actually mutating the call stack frame's entries corresponding to the function's parameters:

length [1,2,3]
length2 0 [1,2,3]       -- a=0  (x:xs)=[1,2,3]
length2 1 [2,3]         -- a=1  (x:xs)=[2,3]
length2 2 [3]           -- a=2  (x:xs)=[3]
length2 3 []            -- a=3  (x:xs)=[]
3

In a pure language, without any value-mutating primitives, the only way to express change is to pass updated values as arguments to a function, to be processed further. If the further processing is the same as before, than naturally we have to invoke the same function for that, passing the updated values to it as arguments. And that's recursion.

---

And the following makes the whole history of calculating the length of an argument list explicit (and available for reuse, if need be):

length xs = last results
  where
     results = length3 0 xs
     length3 a []     = [a]
     length3 a (x:xs) = a : length3 (a+1) xs

In Haskell this is variably known as guarded recursion, or corecursion (at least I think it is).

---

There is nothing 'special' in recursion. It is widespread tool in programming and mathematics and nothing more. However, functional languages are usually minimalistic. They do introduce many fancy concepts like pattern matching, type system, list comprehension and so on, but it is nothing more then syntactic sugar for very general and very powerful, but simple and primitive tools. This tools are: function abstraction and function application. This is conscious choice, as simplicity of the language core makes reasoning about it much easier. It also makes writing compilers easier. The only way to describe a loop in terms of this tools is to use recursion, so imperative programmers may think, that functional programming is about recursion. It is not, it is simply required to imitate that fancy loops for poor ones that cannot drop this syntactic sugar over goto statement and so it is one of the first things they stuck into.

Another point where (may be indirect) recursion required is processing of recursively defined data structures. Most common example is list ADT. In FP it is usually defined like this data List a = Nil | Branch a (List a) . Since definition of the ADT here is recursive, the processing function for it should be recursive too. Again, recursion here is not anyway special: processing of such ADT in recursive manner looks naturally in both imperative and functional languages. Well, In case of list-like ADT imperative loops still can be adopted, but in case of different tree-like structures they can't.

So there is no anything special in recursion. It is simply another type of function application. However, because of limitations of modern computing systems (that comes from poorly made design decisions in C language, which is de-facto standard cross-platform assembler) function calls cannot be nested infinitely even if they are tail calls. Because of it, designers of functional programming languages have to either limit allowed tail-calls to tail recursion (scala) or use complicated techniques like trampoling (old ghc codegen) or compile directly to asm (modern ghc codegen).

TL;DR: There is no anything special in recursion in FP, no more than in IP at least, however, tail recursion is the only type of tail calls allowed in scala because of limitations of JVM.

---

Avoiding side effects is one of the pillars of functional programming (the other is using higher order functions).

Imagine how you might make use of imperative flow control without relying on mutation. Is it possible?

Of course for (var i = 0; i < 10; i++) ... depends on mutation (i++). In fact, any conditional loop construct does. In while (something) ... the something will depend on some mutable state. Sure, while (true) ... doesn't use mutation. But if you ever want out of that loop you'll need an if (something) break. Really, try to think of a (non-infinite) looping mechanism other than recursion that doesn't rely on mutation.

What about for (var x in someCollection) ...? Now we're getting closer to functional programming. The x can be thought of as a parameter to the body of the loop. Reusing the name isn't the same as reassigning a value. Perhaps in the body of the loop you're yield returning values as an expression in terms of x (no mutation).

Exactly equivalently, you could move the body of the for loop into the body of a function foo (x) ... and then map that over someCollection using a higher order function - replacing your loop construct with something like Map(foo, someCollection).

But then how is the library function Map implemented without mutation? Well, using recursion of course! It's done for you. It becomes less common to have to implement recursive functions yourself once you begin making use of the second pilar of higher order functions to replace your looping constructs.

Additionally, with tail call optimization a recursive definition is equivalent to an iterative process. You might also enjoy this blog post: http://blogs.msdn.com/b/ashleyf/archive/2010/02/06/recursion-is-the-new-iteration.aspx

---

There are two properties that I consider essential to functional programming:

1. Functions are first class members (only relevant, because to make it useful the second property is needed)

2. Functions are pure, i.e. a function called with the same arguments returns the same value.

Now if you program in an imperative style you have to use assignment.

Consider a for loop. It has an index and on each iteration the index has a different value. So you could define a function that returns this index. If you call that function twice you might get different results. Thus breaking the principle no 2.

If you break principle no 2. passing around functions (principle no 1) becomes something extremely dangerous, because now the result of the function might depend on when and how often a function gets called.

---

Last time I used a Functional language (Clojure) I was never even tempted to use recursion. Everything could be dealt with as a set of things, to which a function was applied to get part products, to which another function was applied, until the final result was reached.

Recursion is only one way, and not necessarily the clearest way, to handle the multiple items you usually have to handle to deal with any g

---

For the sake of new FP learners I would like to add my 2 cents.As mentioned in some of the answers, recursion is their to make use of immutable variables but why we need to do that ? its because it makes it easy to run the program on multiple cores in parallel, but why we want that ? Can't we run it in single core and be happy as always we have been ? No because content to process is increasing day by day and CPU Clock cycle can't be increased so significantly than adding more cores. From past one decade the clock speed has been around upto 2.7 ghz to 3.0 ghz for consumer computers and chip designers are having issues in fitting more and more transistors in their.Also FP has been their from very long time, but didn't pick up as it used recursion and memory was very expensive in those days but as clock speeds were soaring year after year so community decided to keep on going with OOP Edit: it was quite fast, I had only couple of minutes

참고URL : https://stackoverflow.com/questions/12659581/functional-programming-lots-of-emphasis-on-recursion-why