재귀 함수의 작동 방식 이해

재귀 함수의 작동 방식 이해

---

제목에서 알 수 있듯이 아직 막을 수 없었던 매우 근본적인 프로그래밍 질문이 있습니다. "재귀를 이해하려면 먼저 재귀를 이해해야합니다." 다양한 온라인 스레드에서 답글을 아직 얻지 못했습니다.

우리가 모르는 것을 모르는 것에 직면 할 때, 우리는 잘못된 질문을하거나 올바른 질문을 잘못 묻는 경향이있을 수 있음을 이해합니다. 나는 내 생각이 비슷한 것을 가진 사람이 재귀 전구를 켜는 데 도움이되는 약간의 지식!

다음은 함수입니다 (구문은 Swift로 작성 됨).

func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a: a + 1, b: b)
    }
}

우리는 논쟁으로 2와 5를 사용할 것입니다.

println(sumInts(a: 2, b: 5))

분명히 답은 14입니다. 그러나 그 가치가 어떻게 달성되는지는 확실하지 않습니다.

이들은 내 2 행업입니다.

1. 조건이 충족 될 때까지이 함수를 재귀 적으로 호출합니다. 그 상태는 a> b입니다. 이 조건이 충족되면 0을 반환합니다. 언뜻보기에는 반환 값이 0이 될 것으로 예상됩니다.

2. 각 반복에서 'a'의 값을 인쇄하면 2, 3, 4, 5 (첫 번째 조건을 충족시키는 5 + 1> b : a> b)가 예상되는 값을 얻습니다. 14의 값이 어떻게 달성되는지보십시오.

내 첫 생각은 다음과 비슷한 것이 마술처럼 일어나고 있다는 것입니다.

var answer = a;
answer += a+1 until a > b;
return answer;   

그래서 마법을 배제하고, 나는 무언가를 얻지 못하고 있습니다. 나는 암묵적으로 일어나는 것 이상을 이해하고 싶습니다.

누군가가 이런 종류의 기능을 수행하는 동안 기술적으로 어떤 일이 발생하는지, 왜 결과가 0이 아닌지, 결국에는 어떻게 a + sumInts(a: a + 1, b: b) = 14빚을지게 될지 친절하게 설명 할 수 있습니다.

---

나는 혼동이 그것을 "동일한 기능"이라고 여러 번 생각하는 데 기인 한다고 생각 합니다. "동일한 함수의 여러 복사본"이라고 생각하면 더 명확 할 수 있습니다.

함수의 사본 하나만 0을 반환하고 첫 번째 사본이 아닙니다 (마지막 사본). 따라서 첫 번째 호출의 결과는 0이 아닙니다.

혼란의 두 번째 부분에서는 영어로 재귀를 철자가 더 쉬울 것이라고 생각합니다. 이 줄을 읽으십시오 :

return a + sumInts(a + 1, b: b)

" 'a'의 값을 더한 값 (함수의 다른 사본의 반환 값, 'a'의 사본 값, 더하기 (함수의 다른 사본의 반환 값, 두 번째 사본의 ' a> 더하기 (... ") : a> b 조건이 충족 될 때까지 함수의 각 사본이 1 씩 증가한 새 사본을 생성합니다.

a> b 조건에 도달 할 때, 실행 중에 중간에 (임의로) 긴 함수 사본 스택을 갖게됩니다. 모두 다음 사본의 결과를 기다리고 있습니다. 'a'에 추가해야합니다.

(편집 : 또한 알아야 할 것은 내가 언급 한 함수의 사본 스택이 실제 메모리를 차지하고 너무 커지면 프로그램이 중단된다는 것입니다. 컴파일러는 일부에서 최적화 할 수 있습니다 그러나 많은 언어에서 스택 공간을 소진하는 것은 재귀 함수의 중요하고 불행한 한계입니다.

---

1. 조건이 충족 될 때까지이 함수를 재귀 적으로 호출합니다. 그 조건은 a > b입니다. 이 조건이 충족되면 0을 반환합니다. 언뜻보기에는 반환 값이 0이 될 것으로 예상됩니다.

다음은 컴퓨터 컴퓨팅 sumInts(2,5)이 가능할 것이라고 생각하는 내용입니다.

I want to compute sumInts(2, 5)
for this, I need to compute sumInts(3, 5)
and add 2 to the result.
  I want to compute sumInts(3, 5)
  for this, I need to compute sumInts(4, 5)
  and add 3 to the result.
    I want to compute sumInts(4, 5)
    for this, I need to compute sumInts(5, 5)
    and add 4 to the result.
      I want to compute sumInts(5, 5)
      for this, I need to compute sumInts(6, 5)
      and add 5 to the result.
        I want to compute sumInts(6, 5)
        since 6 > 5, this is zero.
      The computation yielded 0, therefore I shall return 5 = 5 + 0.
    The computation yielded 5, therefore I shall return 9 = 4 + 5.
  The computation yielded 9, therefore I shall return 12 = 3 + 9.
The computation yielded 12, therefore I shall return 14 = 2 + 12.

보시다시피, 함수에 대한 일부 호출은 sumInts실제로 0을 반환하지만 컴퓨터는 여전히 그 0에 5를 더한 다음 결과에 4를 추가 한 다음 3, 2를 추가해야하기 때문에 최종 값이 아닙니다. 우리 컴퓨터의 생각. 재귀에서 컴퓨터는 재귀 호출을 계산할 필요가있을뿐만 아니라 재귀 호출에 의해 반환 된 값으로 무엇을해야하는지 기억해야합니다. 이러한 종류의 정보가 저장 되는 스택 이라는 컴퓨터 메모리의 특수 영역이 있습니다 .이 공간은 제한되어 있으며 너무 재귀적인 기능은 스택을 소진시킬 수 있습니다. 이것은 가장 많이 사랑하는 웹 사이트에 이름을주는 스택 오버플로 입니다.

귀하의 진술은 컴퓨터가 재귀 호출을 할 때 있었던 것을 잊어 버린다는 암시 적 가정을하는 것처럼 보이지만 그렇지 않으므로 결론이 귀하의 관찰과 일치하지 않습니다.

2. 각 반복에서 'a'의 값을 인쇄하면 2, 3, 4, 5 (첫 번째 조건을 충족시키는 5 + 1> b : a> b)가 예상되는 값을 얻습니다. 14의 가치가 어떻게 달성되는지 보지 마십시오.

반환 값 a자체가 아니라 a재귀 호출에 의해 반환 된 값과 값의 합 이기 때문 입니다.

---

재귀를 이해하려면 문제를 다른 방식으로 생각해야합니다. 전체적으로 의미가있는 논리적 인 일련의 단계 대신에 큰 문제를 해결하고 더 작은 문제로 나누고 문제를 해결합니다. 하위 문제에 대한 답변이 있으면 하위 문제의 결과를 결합하여 더 큰 문제에 대한 해결책. 당신과 당신의 친구가 거대한 양동이에 구슬의 수를 계산해야한다고 생각하십시오. 당신은 각각 더 작은 양동이를 가져다가 개별적으로 계산하고 합계를 합산합니다. 이제 친구가 친구를 찾고 양동이를 더 나누면 다른 친구가 기다릴 필요가 있습니다. 그들의 총계를 알아내어 각자에게 다시 가져 오십시오. 등등.

함수가 재귀 적으로 호출 할 때마다 문제의 하위 집합으로 새로운 컨텍스트를 생성 할 때마다 기억해야합니다. 해당 부분이 해결되면 이전 반복이 완료 될 수 있도록 반환됩니다.

단계를 보여 드리겠습니다.

sumInts(a: 2, b: 5) will return: 2 + sumInts(a: 3, b: 5)
sumInts(a: 3, b: 5) will return: 3 + sumInts(a: 4, b: 5)
sumInts(a: 4, b: 5) will return: 4 + sumInts(a: 5, b: 5)
sumInts(a: 5, b: 5) will return: 5 + sumInts(a: 6, b: 5)
sumInts(a: 6, b: 5) will return: 0

sumInts (a : 6, b : 5)가 실행되면 결과를 계산할 수 있으므로 결과를 체인으로 되돌릴 수 있습니다.

 sumInts(a: 6, b: 5) = 0
 sumInts(a: 5, b: 5) = 5 + 0 = 5
 sumInts(a: 4, b: 5) = 4 + 5 = 9
 sumInts(a: 3, b: 5) = 3 + 9 = 12
 sumInts(a: 2, b: 5) = 2 + 12 = 14.

재귀의 구조를 나타내는 또 다른 방법 :

 sumInts(a: 2, b: 5) = 2 + sumInts(a: 3, b: 5)
 sumInts(a: 2, b: 5) = 2 + 3 + sumInts(a: 4, b: 5)  
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + sumInts(a: 5, b: 5)  
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + 5 + sumInts(a: 6, b: 5)
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + 5 + 0
 sumInts(a: 2, b: 5) = 14 

---

재귀는 이해하기 까다로운 주제이며 여기서 완전히 정의 할 수 있다고 생각하지 않습니다. 대신, 여기에있는 특정 코드에 중점을두고 솔루션이 작동하는 이유에 대한 직관과 코드가 결과를 계산하는 방식에 대해 설명하려고합니다.

여기에 제공된 코드는 다음 문제를 해결합니다. a에서 b까지의 모든 정수의 합계를 알고 싶습니다. 예를 들어, 2에서 5까지의 숫자의 합을 원합니다.

2 + 3 + 4 + 5

문제를 재귀 적으로 해결하려고 할 때 첫 번째 단계 중 하나는 문제를 동일한 구조의 작은 문제로 나누는 방법을 알아내는 것입니다. 따라서 2에서 5까지의 숫자를 합산한다고 가정하십시오. 이를 단순화하는 한 가지 방법은 위의 합계를 다음과 같이 다시 작성할 수 있음을 알 수 있습니다.

2 + (3 + 4 + 5)

여기서 (3 + 4 + 5)는 3에서 5 사이의 모든 정수의 합입니다. 즉, 2와 5 사이의 모든 정수의 합을 알고 싶다면 3과 5 사이의 모든 정수의 합을 계산 한 다음 2를 더하십시오.

그렇다면 3에서 5 사이의 모든 정수의 합계를 어떻게 계산합니까? 음, 그 합계는

3 + 4 + 5

대신에 생각할 수 있습니다

3 + (4 + 5)

여기에서 (4 + 5)는 4와 5 사이의 모든 정수의 합입니다. 따라서 3에서 5 사이의 모든 숫자의 합을 계산하려면 4에서 5 사이의 모든 정수의 합을 계산 한 다음 3을 더합니다.

여기에 패턴이 있습니다! a와 b 사이의 정수 합계를 계산하려면 다음을 수행하십시오. 먼저 a + 1과 b 사이의 정수 합계를 계산하십시오. 다음으로 그 합계에 a를 추가하십시오. "a + 1과 b 사이의 정수의 합계를 계산하는 것"은 이미 해결하려고했던 것과 거의 같은 문제이지만 매개 변수가 약간 다르다는 것을 알 수 있습니다. a에서 b까지를 계산하는 대신, +1에서 b까지를 계산합니다. 그것은 재귀적인 단계입니다 – 더 큰 문제 ( "a에서 b까지의 합계")를 해결하기 위해, 우리는 문제를 더 작은 버전 ( "+에서 1까지의 b 포함)"으로 줄입니다.

위의 코드를 살펴보면이 단계가 있음을 알 수 있습니다.

return a + sumInts(a + 1, b: b)

이 코드는 단순히 위의 논리를 변환 한 것입니다. a에서 b까지를 합산하려면 a + 1을 b로 합산하여 시작하십시오 (즉, s에 대한 재귀 호출 sumInt) a.

물론이 방법 자체로는 실제로 작동하지 않습니다. 예를 들어 5에서 5 사이의 모든 정수의 합계를 어떻게 계산합니까? 현재 논리를 사용하여 6에서 5 사이의 모든 정수의 합을 계산 한 다음 5를 더합니다. 그러면 6에서 5 사이의 모든 정수의 합을 어떻게 계산합니까? 현재 논리를 사용하여 7에서 5 사이의 모든 정수의 합을 계산 한 다음 6을 더합니다. 여기에 문제가 있음을 알 수 있습니다. 계속 진행됩니다!

재귀 문제 해결에는 문제 단순화를 중단하고 대신 직접 해결하는 방법이 필요합니다. 일반적으로 답변을 즉시 확인할 수있는 간단한 사례를 찾은 다음 간단한 사례가 발생할 때 직접 해결하도록 솔루션을 구성하십시오. 이것을 기본 사례 또는 재귀 기준 이라고 합니다 .

이 특정 문제의 기본 사례는 무엇입니까? a에서 b까지의 정수를 합산 할 때 a가 b보다 큰 경우 대답은 0입니다. 범위에 숫자가 없습니다! 따라서 다음과 같이 솔루션을 구성합니다.

1. a> b이면 답은 0입니다.
2. 그렇지 않으면 (a ≤ b) 다음과 같이 답을 얻으십시오.
   1. a + 1과 b 사이의 정수의 합을 계산합니다.
   2. 답을 얻으려면를 추가하십시오.

이제이 의사 코드를 실제 코드와 비교하십시오.

func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a + 1, b: b)
    }
}

의사 코드에 요약 된 솔루션과이 실제 코드 사이에는 거의 일대일 맵이 있습니다. 첫 번째 단계는 기본 사례입니다. 빈 숫자 범위의 합계를 요청하면 0이됩니다. 그렇지 않으면 a + 1과 b 사이의 합계를 계산 한 다음 a를 더합니다.

지금까지 코드 뒤에 기본 개념을 제시했습니다. 하지만 다른 좋은 질문이 두 개있었습니다. 첫째, 함수가 a> b 인 경우 0을 반환한다고 말하면 왜 항상 0을 반환하지 않습니까? 둘째, 14는 실제로 어디에서 왔습니까? 이것들을 차례로 살펴 보자.

매우 간단한 사례를 시도해 봅시다. 전화하면 sumInts(6, 5)어떻게 되나요? 이 경우 코드를 추적하면 함수가 0을 반환한다는 것을 알 수 있습니다. 범위에 숫자가없는 것이 올바른 방법입니다. 이제 더 열심히 노력하십시오. 전화하면 sumInts(5, 5)어떻게 되나요? 글쎄, 여기에 무슨 일이 일어나는가 :

1. 당신은 전화 sumInts(5, 5). else브랜치에 들어가 `a + sumInts (6, 5)의 값을 반환합니다.
2. 현재 상황 sumInts(5, 5)을 파악 하려면 현재 sumInts(6, 5)하고있는 일을 일시 중지하고에 전화를 걸어야합니다 sumInts(6, 5).
3. sumInts(6, 5)호출됩니다. if지점에 들어가서를 반환합니다 0. 그러나이 인스턴스가에 sumInts의해 호출 sumInts(5, 5)되었으므로 반환 값은 sumInts(5, 5)최상위 호출자가 아닌 (으)로 다시 전달됩니다 .
4. sumInts(5, 5)이제 5 + sumInts(6, 5)다시 계산할 수 있습니다 5. 그런 다음 최상위 발신자에게 반환합니다.

여기서 값 5가 어떻게 형성되었는지 확인하십시오. 에 대한 한 번의 통화로 시작했습니다 sumInts. 이로 인해 다른 재귀 호출이 시작되었고 해당 호출에서 반환 된 값이 정보를 다시 전달했습니다 sumInts(5, 5). sumInts(5, 5)그런 다음 호출 은 계산을 수행하고 호출자에게 값을 반환했습니다.

이 작업을 시도하면 다음과 같은 sumInts(4, 5)결과가 발생합니다.

• sumInts(4, 5)돌아 오려고 4 + sumInts(5, 5)합니다. 이를 위해을 호출합니다 sumInts(5, 5).
  • sumInts(5, 5)돌아 오려고 5 + sumInts(6, 5)합니다. 이를 위해을 호출합니다 sumInts(6, 5).
  • sumInts(6, 5)sumInts(5, 5).</li> <li>sumInts (5, 5) now has a value forsumInts (6, 5) , namely 0. It then returns5 + 0 = 5`로 다시 0을 반환합니다 .
• sumInts(4, 5)이제 값이 sumInts(5, 5)5 4 + 5 = 9입니다. 그런 다음를 반환합니다 .

즉, 반환되는 값은 한 번에 하나씩 값을 합산하여 매번 특정 재귀 호출에 의해 반환 된 하나의 값을 취하고 sumInts에 현재 값을 더하여 구성됩니다 a. 재귀가 바닥에 도달하면 가장 깊은 호출은 0을 반환합니다. 그러나 해당 값이 재귀 호출 체인을 즉시 종료하지는 않습니다. 대신, 그 값을 그 위의 한 계층의 재귀 호출에 다시 전달합니다. 그런 식으로 각 재귀 호출은 하나 이상의 숫자를 더하고 체인에서 더 높은 값을 반환하여 전체 합계로 끝납니다. 연습으로에 대해 추적 해보십시오 sumInts(2, 5).

도움이 되었기를 바랍니다!

---

여기까지 좋은 답변이 있지만 다른 압정이 필요한 것을 하나 더 추가하겠습니다.

먼저 간단한 재귀 알고리즘에 대해 많은 기사를 작성했습니다. 보다

http://ericlippert.com/tag/recursion/

http://blogs.msdn.com/b/ericlippert/archive/tags/recursion/

그것들은 가장 최신의 순서이므로 맨 아래부터 시작하십시오.

둘째, 지금까지 모든 대답은 함수 활성화 를 고려하여 재귀 의미론을 설명했습니다 . 각각의 각 호출은 새로운 활성화 를 만들고 재귀 호출은이 활성화의 컨텍스트에서 실행됩니다. 그것은 그것을 생각하는 좋은 방법이지만, 또 다른 동등한 방법이 있습니다 : 스마트 텍스트 seach-and-replace .

함수를 좀 더 간결한 형태로 다시 작성하겠습니다. 이것을 특정 언어로 생각하지 마십시오.

s = (a, b) => a > b ? 0 : a + s(a + 1, b)

나는 그것이 의미가 있기를 바랍니다. 조건부 연산자에 익숙하지 않은 경우 형식 연산자이므로 condition ? consequence : alternative그 의미가 명확 해집니다.

이제 우리는 평가하고자하는 s(2,5)함수 본문이있는 통화의 대체 텍스트를 수행하여 우리는 그렇게, 다음 교체 a로 2와 b함께 5:

s(2, 5) 
---> 2 > 5 ? 0 : 2 + s(2 + 1, 5)

이제 조건을 평가하십시오. 우리는 문자 적으로로 대체 2 > 5합니다 false.

---> false ? 0 : 2 + s(2 + 1, 5)

이제 텍스트로 모든 거짓 조건을 대체하고 모든 참 조건을 결과로 대체하십시오. 우리는 그래서 우리는 단지 거짓 조건문을 텍스트로 대체하여 해당 표현을 대체 :

---> 2 + s(2 + 1, 5)

이제 모든 +부호 를 입력하지 않아도되도록 상수 계산을 텍스트로 대체하십시오. (이것은 약간의 속임수이지만 모든 괄호를 추적하고 싶지는 않습니다!)

---> 2 + s(3, 5)

이제 검색 및 교체, 이번에는 전화를 3위한 본문, a및 5b. 통화를 대체 할 내용을 괄호 안에 넣습니다.

---> 2 + (3 > 5 ? 0 : 3 + s(3 + 1, 5))

이제 우리는 동일한 텍스트 대체 단계를 계속 수행합니다.

---> 2 + (false ? 0 : 3 + s(3 + 1, 5))  
---> 2 + (3 + s(3 + 1, 5))                
---> 2 + (3 + s(4, 5))                     
---> 2 + (3 + (4 > 5 ? 0 : 4 + s(4 + 1, 5)))
---> 2 + (3 + (false ? 0 : 4 + s(4 + 1, 5)))
---> 2 + (3 + (4 + s(4 + 1, 5)))
---> 2 + (3 + (4 + s(5, 5)))
---> 2 + (3 + (4 + (5 > 5 ? 0 : 5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (false ? 0 : 5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (5 + s(6, 5))))
---> 2 + (3 + (4 + (5 + (6 > 5 ? 0 : s(6 + 1, 5)))))
---> 2 + (3 + (4 + (5 + (true ? 0 : s(6 + 1, 5)))))
---> 2 + (3 + (4 + (5 + 0)))
---> 2 + (3 + (4 + 5))
---> 2 + (3 + 9)
---> 2 + 12
---> 14

우리가 여기서 한 것은 단순한 텍스트 대체 일뿐 입니다. 실제로 "3"을 "2 + 1"로 대체하지 말아야 할 때까지는 교육적 측면에서 읽기 어려웠습니다.

함수 활성화는 함수 호출을 호출 본문으로 바꾸고 형식 매개 변수를 해당 인수로 바꾸는 것입니다. 괄호를 지능적으로 도입하는 데주의를 기울여야하지만 그 외에도 텍스트 대체 일뿐입니다.

물론 대부분의 언어는 실제로 텍스트 대체로 활성화를 구현 하지 않지만 논리적으로 그 기능을 수행합니다.

그렇다면 무한 재귀는 무엇입니까? 텍스트 대체가 멈추지 않는 재귀! 공지 사항이 어떻게 결국 우리는 더 이상이 있었다 단계에 도착 s대체하기 위해, 우리는 단지 산술 규칙을 적용 할 수 있습니다.

---

일반적으로 재귀 함수의 작동 방식을 알아내는 방법은 기본 사례를보고 거꾸로 작업하는 것입니다. 이 기능에 적용되는 기술은 다음과 같습니다.

먼저 기본 사례 :

sumInts(6, 5) = 0

그런 다음 호출 스택 에서 바로 위의 호출 :

sumInts(5, 5) == 5 + sumInts(6, 5)
sumInts(5, 5) == 5 + 0
sumInts(5, 5) == 5

그런 다음 호출 스택에서 바로 위에있는 호출 :

sumInts(4, 5) == 4 + sumInts(5, 5)
sumInts(4, 5) == 4 + 5
sumInts(4, 5) == 9

등등:

sumInts(3, 5) == 3 + sumInts(4, 5)
sumInts(3, 5) == 3 + 9
sumInts(3, 5) == 12

등등:

sumInts(2, 5) == 2 + sumInts(3, 5)
sumInts(4, 5) == 2 + 12
sumInts(4, 5) == 14

통지 우리가 함수에 우리의 원래 통화에 도착했습니다 sumInts(2, 5) == 14

이러한 호출이 실행되는 순서 :

sumInts(2, 5)
sumInts(3, 5)
sumInts(4, 5)
sumInts(5, 5)
sumInts(6, 5)

이러한 호출이 반환되는 순서 :

sumInts(6, 5)
sumInts(5, 5)
sumInts(4, 5)
sumInts(3, 5)
sumInts(2, 5)

우리는 기능들이 순서대로 호출 추적하여 작동하는 방식에 대한 결론에 도달합니다 반환을 .

---

나는 그것을 줄 것이다.

방정식 a + sumInts (a + 1, b)를 실행하여 최종 답이 14 인 방법을 보여 드리겠습니다.

//the sumInts function definition
func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a + 1, b)
    }
}

Given: a = 2 and b = 5

1) 2 + sumInts(2+1, 5)

2) sumInts(3, 5) = 12
   i) 3 + sumInts(3+1, 5)
   ii) 4 + sumInts(4+1, 5)
   iii) 5 + sumInts(5+1, 5)
   iv) return 0
   v) return 5 + 0
   vi) return 4 + 5
   vii) return 3 + 9

3) 2 + 12 = 14.

더 궁금한 점이 있으면 알려주십시오.

다음은 재귀 함수의 또 다른 예입니다.

한 남자가 방금 대학을 졸업했습니다.

t는 년 단위의 시간입니다.

은퇴하기 전에 근무한 총 실제 년 수는 다음과 같이 계산할 수 있습니다.

public class DoIReallyWantToKnow 
{
    public int howLongDoIHaveToWork(int currentAge)
    {
      const int DESIRED_RETIREMENT_AGE = 65;
      double collectedMoney = 0.00; //remember, you just graduated college
      double neededMoneyToRetire = 1000000.00

      t = 0;
      return work(t+1);
    }

    public int work(int time)
    {
      collectedMoney = getCollectedMoney();

      if(currentAge >= DESIRED_RETIREMENT_AGE 
          && collectedMoney == neededMoneyToRetire
      {
        return time;
      }

      return work(time + 1);
    }
}

그리고 그것은 누군가를 우울하게하기에 충분해야합니다. ;-피

---

재귀. 컴퓨터 과학에서 재귀는 유한 한 Automata의 주제에 따라 심층적으로 다룹니다.

가장 간단한 형태는 자체 참조입니다. 예를 들어, "내 차는 자동차"라는 말은 재귀적인 진술입니다. 문제는 그 진술이 결코 끝나지 않을 것이라는 점에서 무한 재귀라는 것입니다. "자동차"의 진술에서 정의는 그것이 "자동차"이므로 대체 될 수 있다는 것이다. 그러나 대체의 경우에도 여전히 "내 차는 자동차"가되기 때문에 끝이 없습니다.

"내 차는 벤틀리입니다. 내 차는 파란색입니다." 어떤 경우에 자동차에 대한 두 번째 상황에서의 대체는 "벤틀리"일 수 있으며 "나의 벤틀리는 파란색입니다". 이러한 유형의 대체는 Context-Free Grammars를 통해 컴퓨터 과학에서 수학적으로 설명됩니다 .

실제 대체는 생산 규칙입니다. 명령문이 S로 표시되고 자동차가 "벤틀리"일 수있는 변수 인 경우이 명령문은 재귀 적으로 재구성 될 수 있습니다.

S -> "my"S | " "S | CS | "is"S | "blue"S | ε
C -> "bentley"

각 |방법은 선택의 여지가 있으므로 여러 가지 방법으로 구성 할 수 있습니다 . S그 중 하나를 대체 할 수 있으며 S는 항상 비어 있습니다. ε수단은 생성을 종료한다. S대체 할 수있는 것처럼 다른 변수도 가능합니다 (하나만 있으며 C"bentley"를 나타냅니다).

그래서 시작으로 S비어있는, 그리고 첫 번째 선택으로 대체 "my"S S된다

"my"S

S변수를 나타내므로 대체 할 수 있습니다. "my"를 다시 선택하거나 ε을 선택하여 끝낼 수 있지만, 원래 진술을 계속할 수 있습니다. 우리 S는 다음과 같이 대체 되는 공간을 선택합니다." "S

"my "S

다음으로 C를 선택할 수 있습니다

"my "CS

그리고 C는 교체를위한 하나의 선택 만 있습니다

"my bentley"S

그리고 S를위한 공간

"my bentley "S

등등 "my bentley is"S, "my bentley is "S, "my bentley is blue"S, "my bentley is blue"(ε에 대한 S를 교체하면 생산을 종료) 우리는 반복적으로 우리의 문 "내 벤틀리이 파란색"을 구축했다.

재귀를 이러한 생산 및 교체로 생각하십시오. 프로세스의 각 단계는 최종 결과를 생성하기 위해 선행 작업을 대체합니다. 2에서 5까지의 재귀 합계의 정확한 예에서는 생산이 끝납니다.

S -> 2 + A
A -> 3 + B
B -> 4 + C
C -> 5 + D
D -> 0

이것은

2 + A
2 + 3 + B
2 + 3 + 4 + C
2 + 3 + 4 + 5 + D
2 + 3 + 4 + 5 + 0
14

---

재귀 함수를 이해하는 가장 좋은 방법은 재귀 데이터 구조를 처리하도록 만들어진 것입니다. 그러나 원래의 기능에 sumInts(a: Int, b: Int)재귀 적 계산에서 숫자의 합 것을 a하려면 b, 재귀 데이터 구조 ...하자 시도 약간 수정 된 버전이하지 않는 것 같습니다 당신이 추가 할 것입니다 얼마나 많은 숫자입니다.sumInts(a: Int, n: Int)n

이제 sumInts는 n자연수 보다 재귀 적 입니다. 여전히 재귀 데이터가 아닙니다. 음, 자연수는 Peano 공리를 사용하는 재귀 데이터 구조로 간주 될 수 있습니다.

enum Natural = {
    case Zero
    case Successor(Natural)
}

따라서 0 = 0, 1 = Succesor (Zero), 2 = Succesor (Succesor (Zero)) 등입니다.

재귀 데이터 구조가 있으면 함수에 대한 템플리트가 있습니다. 재귀가 아닌 각 경우에 대해 값을 직접 계산할 수 있습니다. 재귀 사례의 경우 재귀 함수가 이미 작동 한다고 가정 하고 함수를 사용하여 사례를 계산하지만 인수를 해체하십시오. 자연의 경우, 대신 것을 의미한다 Succesor(n)우리가 사용하는 것 n대신에, 동등, 또는 n우리가 사용하는 것입니다 n - 1.

// sums n numbers beginning from a
func sumInts(a: Int, n: Int) -> Int {
    if (n == 0) {
        // non recursive case
    } else {
        // recursive case. We use sumInts(..., n - 1)
    }
}

이제 재귀 함수는 프로그래밍하기가 더 간단합니다. 먼저 기본 사례 n=0입니다. 숫자를 더하지 않으려면 무엇을 반환해야합니까? 대답은 물론 0입니다.

재귀 사례는 어떻습니까? 우리가 n시작하는 숫자 를 추가하고 싶다면 a이미 작동하는 sumInts기능이 n-1있습니까? 음, 우리는 추가해야 a하고있는 invoke sumInts와 a + 1, 우리가 끝낼 수 있도록 :

// sums n numbers beginning from a
func sumInts(a: Int, n: Int) -> Int {
    if (n == 0) {
        return 0
    } else {
        return a + sumInts(a + 1, n - 1)
    }
}

좋은 점은 이제 낮은 수준의 재귀를 생각할 필요가 없다는 것입니다. 다음을 확인하면됩니다.

• 재귀 데이터의 기본 경우 재귀를 사용하지 않고 답을 계산합니다.
• 재귀 데이터의 재귀 사례의 경우 비정형 데이터에 대한 재귀를 사용하여 답을 계산합니다.

---

Nisan과 Schocken의 함수 구현에 관심이있을 수 있습니다 . 링크 된 PDF는 무료 온라인 과정의 일부입니다. 학생이 가상 머신 언어 대 머신 언어 컴파일러를 작성해야하는 가상 머신 구현의 두 번째 부분을 설명합니다. 그들이 제안한 함수 구현은 스택 기반이기 때문에 재귀가 가능하다.

함수 구현을 소개하려면 다음 가상 머신 코드를 고려하십시오.

Swift가이 가상 머신 언어로 컴파일 된 경우 다음 Swift 코드 블록이 있습니다.

mult(a: 2, b: 3) - 4

컴파일

push constant 2  // Line 1
push constant 3  // Line 2
call mult        // Line 3
push constant 4  // Line 4
sub              // Line 5

가상 머신 언어는 글로벌 스택을 중심으로 설계되었습니다 . push constant n이 전역 스택으로 정수를 푸시합니다.

행 1과 2를 실행 한 후 스택은 다음과 같습니다.

256:  2  // Argument 0
257:  3  // Argument 1

256및 257메모리 주소입니다.

call mult 리턴 라인 번호 (3)를 스택으로 푸시하고 함수의 로컬 변수를위한 공간을 할당합니다.

256:  2  // argument 0
257:  3  // argument 1
258:  3  // return line number
259:  0  // local 0

... 라벨로 이동 function mult합니다. 내부 코드 mult가 실행됩니다. 이 코드를 실행 한 결과 함수의 0 번째 로컬 변수에 저장된 2와 3의 곱을 계산합니다.

256:  2  // argument 0
257:  3  // argument 1
258:  3  // return line number
259:  6  // local 0

복수 return에서 나오기 직전에 다음 줄을 알 수 있습니다.

push local 0  // push result

제품을 스택에 밀어 넣습니다.

256:  2  // argument 0
257:  3  // argument 1
258:  3  // return line number
259:  6  // local 0
260:  6  // product

돌아 오면 다음과 같은 일이 발생합니다.

• 스택의 마지막 값을 0 번째 인수의 메모리 주소 (이 경우 256)로 팝하십시오. 이것은 가장 편리한 장소입니다.
• 스택의 모든 내용을 0 번째 인수 주소까지 버립니다.
• 리턴 라인 번호 (이 경우 3)로 이동 한 다음 진행하십시오.

돌아온 후 4 행을 실행할 준비가되었으며 스택은 다음과 같습니다.

256:  6  // product that we just returned

이제 스택에 4를 넣습니다.

256:  6
257:  4

sub가상 머신 언어의 기본 기능입니다. 두 개의 인수를 사용하여 결과를 일반적인 주소 (0 번째 인수의 주소)로 반환합니다.

이제 우리는

256:  2  // 6 - 4 = 2

함수 호출의 작동 방식을 알았으므로 재귀의 작동 방식을 이해하는 것이 비교적 간단합니다. 마술 이 아니라 스택입니다.

sumInts이 가상 머신 언어로 기능을 구현했습니다 .

function sumInts 0     // `0` means it has no local variables.
  label IF
    push argument 0
    push argument 1
    lte              
    if-goto ELSE_CASE
    push constant 0
    return
  label ELSE_CASE
    push constant 2
    push argument 0
    push constant 1
    add
    push argument 1
    call sumInts       // Line 15
    add                // Line 16
    return             // Line 17
// End of function

이제 전화하겠습니다.

push constant 2
push constant 5
call sumInts           // Line 21

코드가 실행되고 lte리턴 지점에서 중지 지점까지 이동 합니다 false. 이 시점에서 스택은 다음과 같습니다.

// First invocation
256:  2   // argument 0
257:  5   // argument 1
258:  21  // return line number
259:  2   // augend
// Second
260:  3   // argument 0
261:  5   // argument 1
262:  15  // return line number
263:  3   // augend
// Third
264:  4   // argument 0
265:  5   // argument 1
266:  15  // return line number
267:  4   // augend
// Fourth
268:  5   // argument 0
269:  5   // argument 1
270:  15  // return line number
271:  5   // augend
// Fifth
272:  6   // argument 0
273:  5   // argument 1
274:  15  // return line number
275:  0   // return value

이제 우리의 재귀를 "풀기"하자. return0으로 이동하여 15 행으로 이동하십시오.

271:  5
272:  0

16 행 : add

271:  5

17 행 : return5 행으로 이동하여 15 행으로 이동하십시오.

267:  4
268:  5

16 행 : add

267:  9

17 행 : return9 행 및 15 행으로 이동하십시오.

263:  3
264:  9

16 행 : add

263:  12

17 행 : return12 행 및 15 행으로 이동하여 진행하십시오.

259:  2
260:  12

16 행 : add

259:  14

17 행 : return14 행으로 이동하여 21 행으로 이동하십시오.

256:  14

거기 있어요 재귀 : 영광 goto.

---

재귀를 배우고 이해하는 데있어 정말 유용한 팁 중 하나는 재귀를 통한 것 이외의 다른 루프 구조가없는 언어를 배우는 데 시간을 보내는 것입니다. 그렇게하면 연습을 통해 재귀를 사용하는 방법에 대해 좋은 느낌을 얻을 수 있습니다.

나는 Scheme 튜토리얼뿐만 아니라 http://www.htdp.org/ 를 따랐으며 아키텍처와 디자인 측면에서 프로그램을 디자인하는 방법에 대한 훌륭한 소개입니다.

그러나 기본적으로 시간을 투자해야합니다. 재귀를 '확실히 파악'하지 않으면 역 추적과 같은 특정 알고리즘이 항상 '하드'또는 '매직'처럼 보일 것입니다. 따라서 인내하십시오. :-디

도움이 되길 바랍니다. 행운을 빌어 요!

---

이미 좋은 답변이 많이 있습니다. 여전히 시도하고 있습니다.
호출되면 함수는 할당 된 메모리 공간을 얻습니다 .이 공간 은 호출자 함수 의 메모리 공간 에 쌓 입니다. 이 메모리 공간에서 함수는 전달 된 매개 변수, 변수 및 해당 값을 유지합니다. 이 메모리 공간 은 함수의 종료 리턴 호출과 함께 사라집니다. 스택 개념이 진행됨에 따라 이제 호출자 함수 의 메모리 공간 이 활성화됩니다.

재귀 호출의 경우 동일한 함수가 여러 메모리 공간을 서로 쌓아 놓습니다. 그게 다야. 컴퓨터의 메모리에서 스택이 작동 하는 방법에 대한 간단한 아이디어는 구현에서 재귀가 어떻게 발생하는지에 대한 아이디어를 제공해야합니다.

---

약간의 주제를 벗어난 주제는 알고 있지만 Google에서 재귀 를 찾아보십시오. 예를 들어 의미가 무엇인지 알 수 있습니다 :-)

---

이전 버전의 Google은 다음 텍스트 (메모리에서 인용)를 반환했습니다.

재귀

재귀 참조

2014 년 9 월 10 일에 재귀에 대한 농담이 업데이트되었습니다.

재귀

당신은 의미 했습니까 : 재귀

---

다른 답변은 이 답변을 참조하십시오 .

---

재귀는 같은 일 을하는 여러 클론 으로 생각하십시오 ...

복제 요청 [1] : "2와 5 사이의 합수"

+ clone[1]               knows that: result is 2 + "sum numbers between 3 and 5". so he asks to clone[2] to return: "sum numbers between 3 and 5"
|   + clone[2]           knows that: result is 3 + "sum numbers between 4 and 5". so he asks to clone[3] to return: "sum numbers between 4 and 5"
|   |   + clone[3]       knows that: result is 4 + "sum numbers between 5 and 5". so he asks to clone[4] to return: "sum numbers between 5 and 5"
|   |   |   + clone[4]   knows that: result is 5 + "sum numbers between 6 and 5". so he asks to clone[5] to return: "sum numbers between 6 and 5"
|   |   |   |   clone[5] knows that: he can't sum, because 6 is larger than 5. so he returns 0 as result.
|   |   |   + clone[4]   gets the result from clone[5] (=0)  and sums: 5 + 0,  returning 5
|   |   + clone[3]       gets the result from clone[4] (=5)  and sums: 4 + 5,  returning 9
|   + clone[2]           gets the result from clone[3] (=9)  and sums: 3 + 9,  returning 12
+ clone[1]               gets the result from clone[2] (=12) and sums: 2 + 12, returning 14

그리고 voilá !!

---

위의 많은 답변이 매우 좋습니다. 재귀를 해결하기위한 유용한 기술은 먼저 우리가하고 싶은 것을 먼저 설명하고 인간이 해결할 수있는 코드를 작성하는 것입니다. 위의 경우 연속 된 정수 시퀀스를 합산하려고합니다 (위의 숫자 사용).

2, 3, 4, 5  //adding these numbers would sum to 14

이제이 줄들은 혼란 스럽습니다 (잘못되지는 않지만 혼란 스럽습니다).

if (a > b) {
    return 0 
}

왜 시험을 a>b합니까?return 0

사람이하는 일을 더 자세히 반영하도록 코드를 변경해 봅시다.

func sumInts(a: Int, b: Int) -> Int {
  if (a == b) {
    return b // When 'a equals b' I'm at the most Right integer, return it
  }
  else {
    return a + sumInts(a: a + 1, b: b)
  }
}

우리는 더 인간처럼 할 수 있습니까? 예! 보통 우리는 왼쪽에서 오른쪽으로 요약합니다 (2 + 3 + ...). 그러나 위의 재귀는 오른쪽에서 왼쪽으로 합산됩니다 (... + 4 + 5). 그것을 반영하도록 코드를 변경하십시오 ( -약간 협박 할 수는 있지만 많이는 아닙니다)

func sumInts(a: Int, b: Int) -> Int {
  if (a == b) {
    return b // When I'm at the most Left integer, return it
  }
  else {
    return sumInts(a: a, b: b - 1) + b
  }
}

어떤 사람들은 우리가 '먼'끝에서 시작한 이래로이 기능이 더 혼란 스러울 수 있지만 연습을하면 자연스럽게 느껴질 수 있습니다 (재귀를 풀 때 '양쪽'을 시도하는 또 다른 좋은 '생각'기술입니다). 다시 말하지만,이 함수는 인간 (가장 많이?)이하는 일을 반영합니다. 모든 왼쪽 정수의 합을 취하고 '다음'오른쪽 정수를 추가합니다.

---

나는 재귀를 이해하는데 어려움을 겪고 있었다. 그리고 나는 이 블로그를 발견 했고 나는 이미이 질문을 보았 기 때문에 내가 공유해야한다고 생각했다. 이 블로그를 읽어야한다는 것이 스택에서 설명하는 매우 유용한 것으로 나타 났으며 두 개의 재귀가 스택으로 작동하는 방식을 단계별로 설명합니다. 난 당신이 먼저 여기에 아주 잘 설명 할 방법 스택 작품을 이해하는 것이 좋습니다 여행 -에 - 더 - 스택

then now you will understand how recursion works now take a look of this post: 단계별 재귀 이해

그 프로그램 :

def hello(x):
    if x==1:
        return "op"
    else:
        u=1
        e=12
        s=hello(x-1)
        e+=1
        print(s)
        print(x)
        u+=1
    return e

hello(3)

---

재귀는 다른 사람들이 그것에 대해 말하는 것을 읽거나 그것을 피할 수 있고 코드를 작성한 것으로 보는 것을 멈추었을 때 나에게 의미가 있기 시작했습니다. 솔루션에서 문제를 발견하고 보지 않고 솔루션을 복제하려고했습니다. 나는 무기력하게 붙어있을 때만 해결책을 보았습니다. 그런 다음 다시 복제하려고했습니다. 재귀 문제를 식별하고 해결하는 방법에 대한 내 자신의 이해와 감각을 개발할 때까지 여러 문제에 대해 다시이 작업을 수행했습니다. 이 수준에 도달하면 문제를 해결하고 해결하기 시작했습니다. 더 도움이되었습니다. 때때로, 당신은 스스로 시도하고 고투함으로써 만 배울 수 있습니다. 당신이 그것을 얻을 때까지.

---

피보나치 시리즈의 예를 들어 보겠습니다. 피보나치는

t (n) = t (n-1) + n;

n = 0이면 1

그래서 재귀 작품, 난 그냥 교체하는 방법을 살펴 보겠습니다 n에서 t(n)와 n-1등등. 그것은 본다:

t (n-1) = t (n-2) + n + 1;

t (n-1) = t (n-3) + n + 1 + n;

t (n-1) = t (n-4) + n + 1 + n + 2 + n;

.

.

.

t (n) = t (nk) + ... + (nk-3) + (nk-2) + (nk-1) + n;

우리는 다음 과 t(0)=(n-k)같은지 알고 있으므로 1다음 과 같이 바꿉니다 .n-k=0n=kkn

t (n) = t (nn) + ... + (n-n + 3) + (n-n + 2) + (n-n + 1) + n;

우리가 생략 n-n하면 :

t (n) = t (0) + ... + 3 + 2 + 1 + (n-1) + n;

3+2+1+(n-1)+n자연 수도 마찬가지 입니다. 그것은 다음과 같이 계산된다Σ3+2+1+(n-1)+n = n(n+1)/2 => n²+n/2

fib의 결과는 다음과 같습니다. O(1 + n²) = O(n²)

재귀 관계를 이해하는 가장 좋은 방법

참고 URL : https://stackoverflow.com/questions/25676961/understanding-how-recursive-functions-work