재귀(recursion)는 함수가 자기 자신을 다시 부르는 것입니다. 문제를 같은 꼴의 더 작은 문제로 줄여 부르다가, 더 줄일 수 없는 기저 조건(base case)에서 바로 값을 돌려주고, 돌아오며 남은 계산을 마칩니다. 부를 때마다 프레임이 새로 쌓이고 나중에 부른 것부터 끝나므로, 쌓였다 걷히는 차례를 따라가야 결과를 쓸 수 있습니다. 아래 그림은 fact(3)의 프레임이 쌓였다 하나씩 걷히며, 돌려준 값이 부른 프레임으로 전해지는 모습입니다.
1기저 조건과 재귀 호출
그림의 코드에 결과를 찍는 11번 줄을 더했습니다.
#include <stdio.h>
int fact(int n) {
if (n == 1) {
return 1;
}
return n * fact(n - 1);
}
int main(void) {
int r = fact(3);
printf("%d\n", r);
return 0;
}6- 4~6번 줄이 기저 조건입니다(C 과목은 끝 조건이라 부릅니다). n이 1이면 더 부르지 않고 1을 돌려줍니다.
- 7번 줄은 n − 1로 줄여 자기를 부릅니다. 곱셈
n *은 부른 fact가 돌아온 뒤에 합니다.
손으로 따라갈 때는 호출을 한 줄씩 적습니다. 프레임마다 n이 따로 있습니다.
| 호출 | n | 돌려준 값 |
|---|---|---|
| fact(3) | 3 | 3 × fact(2) = 3 × 2 = 6 |
| fact(2) | 2 | 2 × fact(1) = 2 × 1 = 2 |
| fact(1) | 1 | 1(기저 조건) |
표를 위에서 아래로 부르고, 돌려준 값은 아래에서 위로 채웁니다. 나중에 쌓인 것이 먼저 끝나는 이 차례가 스택과 큐의 스택이라, 재귀 호출은 스택으로 처리됩니다. 기저 조건이 없으면 프레임이 끝없이 쌓여 스택이 넘칩니다(stack overflow).
2호출 앞의 줄과 뒤의 줄
재귀 호출 뒤에 남은 줄은 그 호출이 다 끝나고 돌아온 뒤에 실행됩니다.
#include <stdio.h>
void f(int n) {
if (n == 0) {
return;
}
printf("%d", n);
f(n - 1);
printf("%d", n);
}
int main(void) {
f(3);
printf("\n");
return 0;
}3211237번 줄은 호출 앞이라 부르러 내려가며 3 2 1을 찍고, 9번 줄은 호출 뒤라 돌아오며 1 2 3을 찍습니다. 돌려줄 값이 없는 함수는 return;으로 끝냅니다.
출력 줄이 두 재귀 호출의 앞·사이·뒤 어디 있느냐로 이진 트리 순회와 수식 표기의 전위·중위·후위가 갈립니다.
3피보나치 — 호출 나무
자기를 두 번 부르는 재귀는 호출이 나무처럼 갈라집니다.
int fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) +
fib(n - 2);
}fib(4)는 fib가 모두 9번 불린 끝에 3을 돌려줍니다. fib(2)를 두 번 계산하듯 같은 호출이 되풀이되어, n이 커지면 호출 수가 빠르게 늘어납니다.
예제
돌려준 값과 출력이 함께 있는 재귀
#include <stdio.h>
int f(int n) {
if (n == 1) {
return 1;
}
int r = n + f(n - 1);
printf("%d ", r);
return r;
}
int main(void) {
printf("%d\n", f(4));
return 0;
}무엇이 찍힐까요? 답을 정한 뒤 펼쳐 보세요.
실행 결과 보기
3 6 10 10| 호출 | r | 찍는 것 |
|---|---|---|
| f(1) | — | 없음(1을 돌려줌) |
| f(2) | 2 + 1 = 3 | 3 |
| f(3) | 3 + 3 = 6 | 6 |
| f(4) | 4 + 6 = 10 | 10 |
printf는 f가 돌아와 r이 정해진 뒤에 찍어, 찍는 호출 가운데 가장 나중에 부른 f(2)가 먼저 찍힙니다.
12번 줄의 printf는 괄호 안 f(4)가 다 끝난 뒤에야 돌려받은 10을 찍어 맨 끝에 섭니다.
같은 코드를 Java·Python으로
| C | Java | Python | |
|---|---|---|---|
| 기저 조건 | if (n == 1) { 안에 return 1; | C와 같음 | if n == 1: 다음 줄에 return 1 |
| 트리를 돌 때 기저 조건 | 노드가 NULL이면 돌아감 | 노드가 null이면 돌아감 | if n is None: return |
| 기저 조건이 없으면 | 보통 스택이 넘쳐 비정상 종료(C 표준은 정하지 않음) | StackOverflowError로 멈춤 | RecursionError로 멈춤 |
시험 포인트
- 필기: 재귀 함수의 결과와 호출 횟수를 묻습니다. 기저 조건에서 돌려준 값이 부른 차례의 거꾸로 전해지며 남은 계산이 마무리됩니다. 재귀 호출은 스택으로 처리되고, 기저 조건이 없으면 스택이 넘칩니다. 피보나치처럼 두 번 부르면 같은 호출이 되풀이됩니다.
- 실기: 출력을 그대로 씁니다(재귀 출제 주제). 호출 앞의 출력은 부르러 가며, 호출 뒤의 출력은 돌아오며 찍힙니다.
printf("%d", f(4))처럼 바깥에서 찍는 값은 f 안의 출력이 다 나온 뒤에 찍힙니다.
확인 문제
1. 3절의 fib로 fib(5)를 부르면 fib는 모두 몇 번 불리나요? 처음 부른 fib(5)도 셉니다.
- ① 5번
- ② 9번
- ③ 15번
- ④ 32번
정답
③입니다. 한 호출은 자신 1번에 두 재귀 호출의 횟수를 더합니다. fib(1)·fib(0)은 1번, fib(2)는 3번, fib(3)은 5번, fib(4)는 9번이라 fib(5)는 1 + 9 + 5 = 15번입니다.
- ① fib(5)가 돌려주는 값 5와 섞었습니다.
- ② fib(4)를 부를 때의 횟수입니다.
- ④ 늘 두 번씩 부른다고 2⁵로 셌습니다. n이 1 이하인 호출은 더 부르지 않습니다.
2. 1절 코드의 5번 줄을 return 2;로 바꿨습니다. 출력을 그대로 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.
정답
받는 답:
12
기저 조건이 돌려주는 값이 2가 되어 fact(2)는 2 × 2 = 4, fact(3)은 3 × 4 = 12를 돌려줍니다.
- 틀리는 꼴
6: 기저 조건 값은 곱셈에 들어가지 않는다고 봤습니다. 돌려준 2가 위 프레임의 곱셈에 그대로 쓰입니다. - 틀리는 꼴
2: 기저 조건이 돌려준 값이 그대로 main까지 온다고 봤습니다. 위 프레임마다 남은 곱셈을 하고 돌려줍니다.
3. g(5)를 부를 때의 호출을 표로 따라갔습니다. (가)~(다)를 채우고 g(5)가 돌려주는 값을 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.
| 호출 | n | 돌려준 값 |
|---|---|---|
| g(5) | 5 | g(3) + 5 = (다) |
| g(3) | 3 | g(1) + 3 = (나) |
| g(1) | 1 | g(−1) + 1 = (가) |
| g(−1) | −1 | 0(기저 조건) |
int g(int n) {
if (n <= 0) {
return 0;
}
return g(n - 2) + n;
}정답
받는 답: (가) 1 · (나) 4 · (다) 9, g(5)는 9를 돌려줍니다.
n이 2씩 줄어 5·3·1·−1로 부르고, −1은 0 이하라 기저 조건에서 0을 돌려줍니다. 아래부터 1, 4, 9로 채웁니다.
- 틀리는 꼴 15: 1부터 5까지 모두 더했습니다. n − 2로 줄여 2·4는 부르지 않습니다.
- 틀리는 꼴 8: g(1)에서 멈춘다고 봤습니다. 1은 0 이하가 아니라 g(−1)을 한 번 더 부르고, 그 1을 더합니다.
4. 다음 Python 코드의 출력을 그대로 쓰세요. print(…, end='')는 찍은 뒤 줄을 바꾸지 않습니다. 답을 끝까지 쓴 뒤 정답을 펼치세요.
def f(n):
if n == 0:
return 0
print(n, end='')
s = n + f(n - 1)
print(n, end='')
return s
print(f(2))정답
받는 답:
21123f(2)가 2를 찍고 f(1)을 부르면, f(1)이 1을 찍고 f(0)을 부릅니다. f(0)이 0을 돌려주면 f(1)이 1을 찍고 1을, f(2)가 2를 찍고 3을 돌려줍니다.
바깥 print는 f(2)가 다 끝난 뒤에 3을 찍습니다. 앞의 네 글자가 줄을 바꾸지 않아 3이 같은 줄 끝에 붙습니다.
- 틀리는 꼴 첫 줄
3, 다음 줄2112: 바깥 print가 먼저 찍는다고 봤습니다. 괄호 안 f(2)부터 다 실행됩니다. - 틀리는 꼴 첫 줄
2112, 다음 줄3: 바깥 print가 새 줄에 찍는다고 봤습니다. 앞의 네 글자가 줄을 바꾸지 않아 3이 같은 줄에 붙습니다. - 틀리는 꼴
22113: 6번 줄도 호출 전에 실행된다고 봤습니다. 6번 줄은 f(n − 1)이 돌아온 뒤에 실행됩니다.
5. 자기를 두 번 부르는 함수입니다. 출력을 그대로 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.
#include <stdio.h>
void h(int n) {
if (n == 0) {
return;
}
h(n - 1);
printf("%d", n);
h(n - 1);
}
int main(void) {
h(3);
printf("\n");
return 0;
}정답
받는 답:
1213121printf가 두 호출 사이에 있어, n을 찍기 전에 h(n − 1)을 다 마치고, 찍은 뒤 h(n − 1)을 한 번 더 합니다. h(1)은 1, h(2)는 h(1) · 2 · h(1)이라 121, h(3)은 121 · 3 · 121입니다.
- 틀리는 꼴
3211211: printf가 두 호출 앞에 있는 것처럼 읽었습니다. 찍기 전에 왼쪽 호출부터 끝까지 내려갑니다. - 틀리는 꼴
1121123: printf가 두 호출 뒤에 있는 것처럼 읽었습니다. 둘째 호출은 n을 찍은 뒤에 합니다. - 틀리는 꼴
123: 호출을 하나만 따라갔습니다. 9번 줄도 같은 일을 한 번 더 합니다.
6. 1부터 n까지의 합을 돌려주는 재귀 함수입니다. n은 1 이상입니다. 빈칸 (가)·(나)에 들어갈 코드를 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.
int sum(int n) {
if ( (가) ) {
return 1;
}
return (나);
}정답
받는 답: (가) n == 1 · (나) n + sum(n - 1)
(가)는 더 부르지 않고 1을 돌려줄 기저 조건이고, (나)는 n을 하나 줄인 합에 n을 더합니다. (가)에 n <= 1을 써도 같습니다.
- 틀리는 꼴 (나)에
sum(n - 1): 돌아온 합에 n을 더하지 않아, 늘 기저 조건의 1이 돌아옵니다. - 틀리는 꼴 (나)에
n + sum(n): 줄이지 않고 같은 n으로 다시 불러 기저 조건에 닿지 못합니다. 프레임이 끝없이 쌓입니다.
처음이라면: C 언어 과목(준비 중)의 '재귀: 프레임이 쌓였다 풀린다' 레슨에서 같은 규칙을 처음부터 천천히 봅니다.