[function] 재귀 함수 작동 방식 이해

재귀는 이해하기 까다로운 주제이며 여기서 완전히 정의 할 수 없다고 생각합니다. 대신 여기에있는 특정 코드에 초점을 맞추고 솔루션이 작동하는 이유에 대한 직관과 코드가 결과를 계산하는 방법에 대한 메커니즘을 모두 설명하려고 노력할 것입니다.

여기에 제공 한 코드는 다음 문제를 해결합니다. 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 + 1과 b 사이의 정수의 합을 계산하라”는 것은 우리가 이미 풀려고하는 문제와 거의 비슷하지만 매개 변수가 약간 다르다는 것을 알게 될 것입니다. a에서 b로 계산하는 대신 a + 1에서 b로 계산합니다. 이것이 재귀 적 단계입니다. 더 큰 문제 ( “a에서 b 로의 합, 포함”)를 해결하기 위해 문제를 더 작은 버전 ( “a + 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) 으로 시작하고 싶은을 .

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

답변

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

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

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

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

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

---> 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

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)
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)

//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.

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);
    }
}