| English | 의미 |
|---|---|
| Recursion/rɪˈkɜːʃn/ | 재귀 |
| base case/beɪs keɪs/ | 기본 사례 |
| recursive case/rɪˈkɜːsɪv keɪs/ | 재귀 사례 |
| unwind/ʌnˈwaɪnd/ | 언와인드(unwind) |
자신을 호출하는 방법
- 재귀(recursion) 는 같은 문제의 더 작은 버전을 해결하기 위해 본인을 다시 호출하는 방법이다.
- 모든 재귀에는 두 부분이 필요하다: 기저 사례(base case) 와 재귀 사례(recursive case) .
- 기저 사례 는 재귀를 멈춘다—method가 직접 답을 주는 작은 입력 값이다.
- 재귀 사례 는 더 작은 입력 값으로 method를 다시 호출한다.
기저 사례
- 기저 사례가 없으면 method가 영원히 자신을 호출하게 되며, 이는
StackOverflowError( Stack Overflow )이다. - 기저 사례는 추가적인 호출 없이 가장 작은 입력을 처리한다.
- 예:
factorial(0)는1를 직접 반환—더 이상 호출하지 않는다. - 항상 확인하라: 모든 경로가 결국 기저 사례에 도달하는가?
재귀 사례
- 재귀 사례는少し 작업을 한 뒤 더 작은 입력으로 자신을 다시 호출한다.
factorial(n)는n * factorial(n - 1)를 반환—입력이 매 호출마다 하나씩 줄어든다.- 각 호출은 더 작은 호출이 반환될 때까지 대기한다.
- 호출들이 쌓이고, 기저 사례에 도달한 뒤 위쪽(초기 호출)으로 풀려(unwind) 올라온다.
호출 스택의 흐름
factorial(3)→3 * factorial(2)→3 * (2 * factorial(1))→3 * (2 * (1 * factorial(0))).factorial(0)가1를 반환하면, 스택이 풀려 올라간다:1, 1, 2, 6.- 각 호출은 반환될 때까지 자체 parameter의 복사본을 유지한다.
- 재귀를 추적trace한다는 것은 호출들을 아래로 따라가고, 반환들을 위로 따라가는 것이다.
모든 재귀에는 이를 멈출 기저 사례가 있어야 하며, 각 재귀 호출은 반드시 그 기저 사례 쪽으로 이동해야 한다(입력이 작아져야 함). 기저 사례를 누락하거나 동일한 또는 더 큰 입력으로 호출하면 method는 영구 재귀에 빠져 StackOverflowError( Stack Overflow )이 발생한다. 아래로 호출을 따라가 기저 사례에 도달하고, 위로 반환을 따라가며 추적trace하라.
sum(n) = 1 + 2 + … + n (재귀):
- 기저 사례:
if (n == 0) return 0; - 재귀 사례:
return n + sum(n - 1); sum(3)→3 + sum(2)→3 + (2 + sum(1))→ … →6.
재귀(recursion) 는 더 작은 입력 값으로 본인을 다시 호출하는 방법이다. 기저 사례(직접 멈춤, 추가 호출 없음)와 재귀 사례(약간의 작업 후 더 작은 입력으로 재귀)가 필요하다. 호출들은 아래로 쌓여 기저 사례에 도달한 뒤 위쪽으로 풀려(unwind) 올라온다. 기저 사례를 누락하면 StackOverflowError( Stack Overflow )이 발생한다.
factorial(3)은 기본 경우(base case)에서 위로 unfolds됨
fact(0)은 1을 반환(기본 경우); 각 부모 함수가 곱셈: 1, 1, 2, 6.
재귀 메서드는 ...인 메서드입니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
재귀 = 메서드가 자신을 호출함.
기본 경우(base case)는...
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
기본 경우는 재귀를 멈춥니다.
도달 가능한 기본 경우가 없는 재귀는 ...을 유발합니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
스택이 오버플로우될 때까지 무한히 재귀합니다.
재귀 경우(self-call)는 ...에서自身를 호출해야 합니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
각 호출은 기본 경우로 수축되어야 합니다.
factorial(0)=1이고 factorial(n)=n*factorial(n-1)일 때, factorial(3)은?
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
3 * 2 * 1 * 1 = 6.
각 재귀 호출은 반환될 때까지 자신의 파라미터의 고유한 복사본을 유지합니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
스택에서 독립적으로 호출된 후 unfold됩니다.