재귀 기초
Coddy C 여정의 Fundamentals 섹션에 포함된 레슨 — 63개 중 50번째.
재귀(Recursion)는 함수가 자기 자신을 호출하여 문제를 해결하는 기술입니다. 이는 큰 문제를 더 작고 유사한 문제들로 나누어 해결하는 것과 같습니다.
팩토리얼을 계산하는 간단한 재귀 함수를 살펴보겠습니다:
int factorial(int n) {
// 기저 사례: 0 또는 1의 팩토리얼은 1입니다
if (n <= 1) {
return 1;
}
// 재귀 사례: n! = n * (n-1)!
return n * factorial(n - 1);
}모든 재귀 함수는 다음을 필요로 합니다:
- 재귀를 중단하기 위한 기본 케이스(base case)
- 기본 케이스를 향해 나아가는 재귀 케이스(recursive case)
예를 들어, factorial(3)을 계산하면 다음과 같습니다:
- factorial(3)이 factorial(2)를 호출합니다
- factorial(2)가 factorial(1)을 호출합니다
- factorial(1)이 1을 반환합니다 (기본 케이스)
- factorial(2)는 2 * 1 = 2를 반환합니다
- factorial(3)는 3 * 2 = 6을 반환합니다
챌린지
쉬움재귀를 사용하여 1부터 n까지의 합을 계산하는 sumToN 함수를 만드세요.
예를 들어:
- sumToN(3)은 6 (1 + 2 + 3)을 반환해야 합니다
- sumToN(5)는 15 (1 + 2 + 3 + 4 + 5)를 반환해야 합니다
함수는 다음을 수행해야 합니다:
- n이 1일 때 기저 사례(base case)를 사용합니다 (1을 반환)
- 그렇지 않으면, n에 1부터 (n-1)까지의 합을 더한 값을 반환합니다
치트 시트
재귀는 문제를 더 작고 유사한 문제로 나누어 해결하기 위해 함수가 자기 자신을 호출하는 기술입니다.
모든 재귀 함수에는 다음이 필요합니다:
- 재귀를 중단하기 위한 기본 케이스(base case)
- 기본 케이스를 향해 나아가는 재귀 케이스(recursive case)
예시 - 팩토리얼 함수:
int factorial(int n) {
// 기본 케이스: 0 또는 1의 팩토리얼은 1입니다
if (n <= 1) {
return 1;
}
// 재귀 케이스: n! = n * (n-1)!
return n * factorial(n - 1);
}factorial(3)이 실행되는 방식:
- factorial(3)이 factorial(2)를 호출합니다
- factorial(2)가 factorial(1)을 호출합니다
- factorial(1)이 1을 반환합니다 (기본 케이스)
- factorial(2)가 2 * 1 = 2를 반환합니다
- factorial(3)이 3 * 2 = 6을 반환합니다
직접 해보기
#include <stdio.h>
// 여기에 sumToN 함수를 작성하세요
// main() 함수를 변경하지 마세요
int main() {
int n;
scanf("%d", &n);
printf("%d", sumToN(n));
return 0;
}
실력 점검이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.