재귀
마지막 업데이트
재귀는 같은 문제의 더 작은 버전에 대해 함수가 자기 자신을 호출하는 것으로, 곧바로 답할 수 있을 만큼 작은 경우에 도달할 때까지 이어집니다. 그렇게 곧바로 답할 수 있는 경우가 기저 조건이며, 모든 재귀 함수에는 기저 조건이 반드시 하나 필요합니다. fib(n)은 fib(n - 1)과 fib(n - 2)로 계속 갈라지다가 fib(1) 또는 fib(0)에 도달하고, 이 둘은 자기 값을 그대로 반환합니다. 위 시각화가 바로 이 과정을 실행합니다. 재생을 눌러 호출이 트리 모양으로 뻗어 나가 잎에서 기저 조건에 닿고, 값이 위로 되돌아오며 각 단계에서 합쳐지는 모습을 확인하세요.
애니메이션이 보여 주는 두 번째는 호출 스택, 즉 시작되었지만 아직 반환되지 않은 모든 호출입니다. 스택은 호출이 깊어질수록 자라나 재귀 깊이에서 최대가 되고, 결과가 돌아오면서 풀립니다. 깊은 재귀가 스택 오버플로를 일으킬 수 있는 반면 반복문은 스택을 전혀 키우지 않는 이유가 여기에 있습니다. 이와 똑같은 호출 구조가 깊이 우선 탐색, 병합 정렬, 그리고 이진 트리의 대부분 연산을 움직입니다.
시간 및 공간 복잡도
위에서 보여 준 단순 재귀 피보나치와, 이를 개선하는 두 가지 표준적인 방법입니다:
| 방식 | 시간 | 공간 | 비고 |
|---|---|---|---|
| 단순 재귀 | O(2^n) | O(n) | 호출 트리가 매 단계마다 두 배로 늘어난다. 공간은 트리 전체가 아니라 가장 깊은 스택만큼이다. |
| 메모이제이션 적용 | O(n) | O(n) | 각 fib(k)를 한 번만 계산해 캐시한다. 반복되는 부분 트리는 조회로 대체된다. |
| 반복문 | O(n) | O(1) | 굴려 쓰는 변수 두 개가 스택을 완전히 대신한다. |
| 일반적인 재귀 전반 | 호출 횟수 × 호출당 작업량 | O(max depth) | 스택은 시작되었지만 아직 반환되지 않은 호출마다 프레임을 하나씩 담는다. |
단계별 과정
| 단계 | 무슨 일이 일어나는가 |
|---|---|
| 1 | 첫 호출 fib(n)이 호출 스택에 올라간다. |
| 2 | 이 호출은 fib(n - 1)이 필요하므로 그 호출도 스택에 올라가고, 부모는 기다린다. |
| 3 | n <= 1인지 묻는 호출이 나올 때까지 호출이 계속 중첩된다. 기저 조건은 더 깊은 호출 없이 즉시 답한다. |
| 4 | 기저 조건의 값이 부모에게 반환되고, 부모는 이제 두 번째 호출 fib(n - 2)를 시작할 수 있다. |
| 5 | 두 자식이 모두 반환하면 부모는 둘을 더해 자신도 반환하고, 그 프레임은 스택에서 빠진다. |
| 6 | 반환이 트리를 따라 위로 반복되다가, 첫 호출의 프레임이 최종 답과 함께 빠져나가고 스택이 비워진다. |
풀이 예제
애니메이션이 재생하는 그대로, fib(4)를 정확한 호출 순서로 계산하면:
| 호출 | 그 시점의 스택 | 반환값 |
|---|---|---|
fib(4) | fib(4) | 자식을 기다림 |
fib(3) | fib(4) > fib(3) | 자식을 기다림 |
fib(2) | fib(4) > fib(3) > fib(2) | 자식을 기다림 |
fib(1) | fib(4) > fib(3) > fib(2) > fib(1) | 1 (기저 조건) |
fib(0) | fib(4) > fib(3) > fib(2) > fib(0) | 0 (기저 조건) |
fib(2) 합치기 | fib(4) > fib(3) > fib(2) | 1 + 0 = 1 |
fib(1) | fib(4) > fib(3) > fib(1) | 1 (기저 조건) |
fib(3) 합치기 | fib(4) > fib(3) | 1 + 1 = 2 |
fib(2) 다시 | fib(4) > fib(2) | 1, 처음부터 다시 계산 |
fib(4) 합치기 | fib(4) | 2 + 1 = 3 |
재귀를 사용해야 할 때
| 사용해야 할 때 | 피해야 할 때 |
|---|---|
| 문제가 자기 유사할 때: 트리, 중첩 구조, 분할 정복 | 같은 일을 스택 프레임 없이 단순한 반복문으로 표현할 수 있을 때 |
깊이가 병합 정렬의 O(log n)처럼 제한적이고 완만할 때 | 입력이 아주 클 때 깊이가 입력 크기까지 도달해 스택 오버플로 위험이 있을 때 |
| 백트래킹에서 어디부터 다시 시작할지 스택이 기억해 주어야 할 때 | 같은 부분 문제가 반복되는데 그 결과를 캐시하지 않을 때 |
| 재귀 버전이 읽고 검증하기에 확실히 더 쉬울 때 | 호출 오버헤드가 측정될 만큼 영향을 주는 핫 루프 안에 있을 때 |
Recursion 코드
Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 Recursion 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.
Python로 구현한 Recursion 코드
Python
1calls = 02
3def fib(n, depth=0):4 global calls5 calls += 16 # Print the call with its depth so the recursion is visible7 print(" " * depth + f"fib({n})")8 if n <= 1:9 return n10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1)11
12
13print("fib(5) =", fib(5))14print("calls made:", calls)JavaScript로 구현한 Recursion 코드
JavaScript
1let calls = 0;2
3function fib(n, depth = 0) {4 calls += 1;5 // Print the call with its depth so the recursion is visible6 console.log(' '.repeat(depth) + `fib(${n})`);7 if (n <= 1) return n;8 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);9}10
11console.log('fib(5) =', fib(5));12console.log('calls made:', calls);Java로 구현한 Recursion 코드
Java
1public class Main {2 static int calls = 0;3
4 static int fib(int n, int depth) {5 calls++;6 // Print the call with its depth so the recursion is visible7 System.out.println(" ".repeat(depth) + "fib(" + n + ")");8 if (n <= 1) return n;9 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);10 }11
12 public static void main(String[] args) {13 System.out.println("fib(5) = " + fib(5, 0));14 System.out.println("calls made: " + calls);15 }16}C++로 구현한 Recursion 코드
C++
1#include <iostream>2#include <string>3
4int calls = 0;5
6int fib(int n, int depth) {7 calls++;8 // Print the call with its depth so the recursion is visible9 std::cout << std::string(depth * 2, ' ') << "fib(" << n << ")\n";10 if (n <= 1) return n;11 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);12}13
14int main() {15 int result = fib(5, 0);16 std::cout << "fib(5) = " << result << "\n";17 std::cout << "calls made: " << calls << "\n";18 return 0;19}C로 구현한 Recursion 코드
C
1#include <stdio.h>2
3int calls = 0;4
5int fib(int n, int depth) {6 calls++;7 /* Print the call with its depth so the recursion is visible */8 printf("%*sfib(%d)\n", depth * 2, "", n);9 if (n <= 1) return n;10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);11}12
13int main(void) {14 printf("fib(5) = %d\n", fib(5, 0));15 printf("calls made: %d\n", calls);16 return 0;17}재귀 FAQ
재귀에서 기저 조건이란 무엇인가요?
또 다른 재귀 호출 없이 답할 수 있을 만큼 작은 입력을 말합니다.
fib(n)에서는 n <= 1이 기저 조건이며, n을 그대로 반환합니다. 도달 가능한 기저 조건이 없으면 호출이 멈추지 않아 스택이 계속 자라고, 프로그램은 스택 오버플로로 중단됩니다.호출 스택은 무엇이며 왜 중요한가요?
런타임은 시작되었지만 아직 반환되지 않은 호출마다 프레임을 하나씩 유지하며, 그 안에 인자와 지역 변수를 담습니다. 재귀 깊이가 곧 스택 높이이므로,
n 단계 깊이로 들어가는 재귀는 각 호출이 하는 일이 거의 없어도 O(n) 메모리를 씁니다. 애니메이션 아래의 칩 줄이 바로 이 스택이 자라고 풀리는 모습을 보여 줍니다.재귀 피보나치는 왜 지수 시간이 걸리나요?
같은 부분 문제를 몇 번이고 다시 계산하기 때문입니다. 위 풀이 예제에서
fib(2)는 fib(4) 안에서 두 번 계산되고, 이런 중복이 거의 매 단계마다 두 배로 늘어 O(2^n)번의 호출이 됩니다. 처음 계산할 때 결과를 캐시하는 기법, 즉 메모이제이션을 쓰면 이 트리는 O(n)으로 줄어듭니다.재귀가 반복보다 더 나은가요?
어느 쪽도 항상 낫지는 않습니다. 모든 재귀는 명시적 스택을 쓰는 반복문으로 바꿀 수 있고, 모든 반복문도 재귀로 바꿀 수 있습니다. 트리 순회나 깊이 우선 탐색처럼 자기 유사한 문제에서는 재귀가 가독성에서 앞서고, 선형으로 훑는 작업에서는 메모리와 호출 비용 면에서 반복이 앞섭니다.
재귀 함수에서 스택 오버플로는 왜 발생하나요?
기저 조건이 없거나 도달할 수 없어 호출이 멈추지 않는 경우이거나, 재귀 자체는 올바른데 깊이가 런타임의 스택 한계에 비해 너무 큰 경우입니다. 후자는 원소가 수백만 개인 입력에서 원소마다 한 번씩 재귀하는 상황이 그렇습니다. 해결책은 기저 조건에 반드시 도달하도록 보장하거나, 깊이를 제한하거나, 반복으로 바꾸는 것입니다.
관련 자료
더 많은 시각화
