재귀 함수
IT 위키
(재귀 호출에서 넘어옴)
- Recursive Function; 재귀 호출(Recursion)
- 자기 자신을 다시 호출하는 함수. 큰 문제를 같은 형태의 작은 문제로 바꿔 가며 푸는 방식이다.
재귀 함수는 반드시 두 부분을 갖는다. 하나라도 빠지면 무한 재귀가 된다.
- 기저 조건(Base case)
- 더 이상 자신을 호출하지 않고 값을 돌려주는 종료 지점
- 재귀 단계(Recursive case)
- 문제를 더 작게 만들어 자신을 다시 호출하는 부분. 호출할 때마다 기저 조건에 가까워져야 한다.
int fact(int n) {
if (n <= 1) return 1; // 기저 조건
return n * fact(n - 1); // 재귀 단계
}
- 함수를 호출할 때마다 호출 스택(call stack)에 스택 프레임이 하나씩 쌓인다. 프레임에는 매개변수, 지역 변수, 돌아갈 주소가 들어간다.
- 기저 조건에 도달하면 값을 돌려주면서 프레임이 쌓인 역순으로 걷힌다.
- 그래서 재귀는 스택의 동작과 그대로 대응한다. 반복문으로 바꿀 때 명시적인 스택을 쓰는 이유도 이것이다.
자기 호출을 처리 전에 하느냐 후에 하느냐에 따라 결과가 뒤집힌다. 시험에 자주 나오는 지점이다.
void f(int n) { if (n == 0) return; printf("%d", n); f(n-1); } // 처리 후 호출 → 3 2 1
void g(int n) { if (n == 0) return; g(n-1); printf("%d", n); } // 호출 후 처리 → 1 2 3
문자열을 뒤에서부터 훑으며 앞쪽에 결과를 붙여 나가는 형태(c + result)도 같은 원리로 역순 출력이 된다.
- 직접 재귀 : 함수가 자기 자신을 호출한다.
- 간접 재귀 : A가 B를, B가 다시 A를 호출한다.
- 꼬리 재귀(Tail recursion) : 재귀 호출이 함수의 마지막 연산인 경우. 호출 후 할 일이 없으므로 컴파일러가 반복문으로 바꿔 스택을 쓰지 않게 최적화할 수 있다.
- 다중 재귀 : 한 번에 여러 번 자신을 호출한다. 피보나치, 분할 정복이 그 예다.
- 장점
- 문제의 정의를 코드로 거의 그대로 옮길 수 있어 간결하고 읽기 쉽다.
- 트리 순회, 하노이탑, 백트래킹처럼 구조 자체가 재귀적인 문제에 자연스럽다.
- 단점
- 호출마다 스택 프레임이 쌓이므로 메모리를 더 쓰고 함수 호출 비용이 든다.
- 깊이가 너무 깊으면 스택 오버플로가 난다.
- 같은 부분 문제를 여러 번 계산하기 쉽다. 단순 재귀 피보나치가 지수 시간이 되는 이유이며, 메모이제이션이나 동적 계획법으로 해결한다.
- 모든 재귀는 반복문으로, 모든 반복문은 재귀로 바꿀 수 있다.
- 성능이 중요하면 반복문이, 코드의 명료함이 중요하면 재귀가 유리하다.
- 팩토리얼, 피보나치, 최대공약수(유클리드 호제법)
- 하노이탑
- 이진 트리 순회, 트리 탐색
- 분할 정복 알고리즘 — 퀵 정렬, 병합 정렬, 이진 탐색
- 백트래킹 — N-Queen 문제
