이 페이지는 최신 브라우저(SharedArrayBuffer 지원)가 필요합니다. Chrome, Edge, Firefox 또는 Safari를 최신 버전으로 업데이트해 주세요.
자신을 호출하는 함수
- 재귀는 함수가 동일한 문제의 더 작은 버전을 해결하기 위해 자신을 호출하는 것입니다.
- 두 부분이 필요합니다: 멈추게 하는 **기저 경우(base case)**와 문제를 축소시키는 재귀 경우(recursive case).
- 기본 사례가 없으면 무한히 자신을 호출하여 충돌합니다.
기저 경우
- 기저 경우는 더 이상 호출 없이 직접 답할 수 있는 가장 작은 문제입니다.
- 계승(factorial)의 경우,
0!과1!은 모두1입니다 — 이것이 기저 경우입니다. - 항상 기저 경우를 먼저 처리하십시오, 그래야 재귀가 멈출 수 있는 지점이 생깁니다.
재귀 경우
- 재귀 경우는 더 작은 문제의 답을 사용하여 문제를 해결합니다.
n! = n × (n - 1)!, 따라서factorial(n)은n * factorial(n - 1)를 반환합니다.- 매번 호출이 기저 경우에 더 가까워져야 합니다, 그렇지 않으면 절대 멈추지 않습니다.
English
#include <stdio.h>
int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
int main(void) {
printf("%d\n", factorial(5)); // 120
return 0;
}
배열에 대한 재귀
- 배열을 따라 재귀할 수 있는데, 각 호출마다 앞으로 이동하는 **인덱스(index)**를 전달하면 됩니다.
- 기저 경우는 "인덱스가 끝에 도달했다"입니다 (합계 합산의 경우
0을 반환). - 재귀 경우는
a[i] + sum(a, i + 1, n)— 현재 항목 plus 나머지들의 합입니다.
흔한 실수
- 재귀에는 기저 경우가 필요합니다, 그렇지 않으면 호출 스택 오버플로우가 발생합니다.
- 각 호출은 반드시 기본 경우에 가까워져야 합니다.
이제 직접 해보기
- 먼저 기본 사례를 작성한 다음, 더 작은 입력에 대해 자신을 호출하는 재귀적 사례를 작성하십시오.
- 테스트 값은 작게 유지하여 숫자가
int범위 안에 머물게 하십시오. main을 작성하지 마십시오—체크기가 하나 제공합니다.
탐색하기
재귀는 상향으로 값을 반환합니다.
기본 조건(base case)까지 분할한 후 호출이 상향으로 값을 반환합니다.
난이도 4/5 · 280코인 + 오늘 첫 완료 시 작은 보너스 추가
int factorial(int n)을 완성하여 재귀(recursion)를 사용하십시오. n <= 1일 때는 1을 반환(기저 사례), 그렇지 않을 때는 n * factorial(n - 1)을 반환하십시오. main은 작성하지 마십시오.
출력을 보려면 '실행'을 클릭하세요.
난이도 4/5 · 280코인 + 오늘 첫 완료 시 작은 보너스 추가
int power(int base, int exp)을 재귀로 완성하십시오 (exp >= 0이 주어졌다고 가정): ⟨base⟩를 ⟨0⟩제곱한 값은 1이며, 그렇지 않으면 base * power(base, exp - 1)입니다. **main**을 작성하지 마십시오.
출력을 보려면 '실행'을 클릭하세요.
난이도 4/5 · 280코인 + 오늘 첫 완료 시 작은 보너스 추가
int array_sum(const int a[], int i, int n)를 재귀로 완성하여 a[i]부터 a[n-1]까지의 합을 반환하도록 하십시오. 기본 조건: i >= n일 때 0를 반환합니다. main를 작성하지 마십시오.
출력을 보려면 '실행'을 클릭하세요.