Recursion: base case and recursive case
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · 이 페이지는 최신 브라우저(SharedArrayBuffer 지원)가 필요합니다. Chrome, Edge, Firefox 또는 Safari를 최신 버전으로 업데이트해 주세요.
English
A function that calls itself
- Recursion is when a function calls itself to solve a smaller version of the same problem.
- It needs two parts: a base case that stops, and a recursive case that shrinks the problem.
- Without a base case, it would call itself forever and crash.
한국어
자신을 호출하는 함수
- **재귀(recursion)**는 함수가 같은 문제의 더 작은 버전을 해결하기 위해 자신自身을 호출하는 것입니다.
- 두 부분이 필요합니다: 멈추게 하는 **기저 경우(base case)**와 문제를 축소시키는 재귀 경우(recursive case).
- 기저 경우가 없으면 무한히 자신自身을 호출하여 충돌(crash)할 것입니다.
English
The base case
- The base case is the smallest problem you can answer directly, with no more calls.
- For factorial,
0!and1!are both1— that is the base case. - Always handle the base case first, so the recursion has somewhere to stop.
한국어
기저 경우
- 기저 경우는 더 이상 호출 없이 직접 답할 수 있는 가장 작은 문제입니다.
- 계승(factorial)의 경우,
0!과1!은 모두1입니다 — 이것이 기저 경우입니다. - 항상 기저 경우를 먼저 처리하십시오, 그래야 재귀가 멈출 수 있는 지점이 생깁니다.
English
The recursive case
- The recursive case solves the problem using the answer to a smaller one.
n! = n × (n - 1)!, sofactorial(n)returnsn * factorial(n - 1).- Each call must move closer to the base case, or it will never stop.
한국어
재귀 경우
- 재귀 경우는 더 작은 문제의 답을 사용하여 문제를 해결합니다.
n! = n × (n - 1)!, 따라서factorial(n)은n * factorial(n - 1)를 반환합니다.- 매번 호출이 기저 경우에 더 가까워져야 합니다, 그렇지 않으면 절대 멈추지 않습니다.
#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;
}
English
Recursion over an array
- You can recurse along an array by passing an index that moves forward each call.
- The base case is "the index has reached the end" (return
0for a sum). - The recursive case is
a[i] + sum(a, i + 1, n)— this item plus the sum of the rest.
한국어
배열에 대한 재귀
- 배열을 따라 재귀할 수 있는데, 각 호출마다 앞으로 이동하는 **인덱스(index)**를 전달하면 됩니다.
- 기저 경우는 "인덱스가 끝에 도달했다"입니다 (합계 합산의 경우
0을 반환). - 재귀 경우는
a[i] + sum(a, i + 1, n)— 현재 항목 plus 나머지들의 합입니다.
English
Common mistakes
- Recursion needs a base case, or the call stack overflows.
- Each call must move closer to the base case.
한국어
흔한 실수
- 재귀에는 기저 경우가 필요합니다, 그렇지 않으면 호출 스택 오버플로우가 발생합니다.
- 각 호출은 반드시 기본 경우에 가까워져야 합니다.
English
Now you try
- Write the base case first, then the recursive case that calls itself on a smaller input.
- Keep test values small so the numbers stay inside an
int. - Do not write a
main— the checker provides one.
한국어
이제 직접 해보기
- 먼저 기저 경우를 작성한 뒤, 더 작은 입력에 대해 자신自身를 호출하는 재귀 경우를 작성하십시오.
- 테스트 값은 작게 유지하여 숫자가
int범위 안에 머물게 하십시오. main을 작성하지 마세요; 검증程序가 제공해 줍니다.
Explore · 탐색하기
Recursion returns up
Calls split to a base case, then values return up.
Complete int factorial(int n) using recursion: return 1 for n <= 1 (the base case), otherwise n * factorial(n - 1). Do not write a main.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Complete int power(int base, int exp) using recursion (assume exp >= 0): base to the power 0 is 1, otherwise base * power(base, exp - 1). Do not write a main.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Complete int array_sum(const int a[], int i, int n) using recursion: it returns the sum of a[i] up to a[n-1]. Base case: i >= n returns 0. Do not write a main.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.