6. 재귀함수

재귀함수

빠른 설명

재귀함수는 함수가 자기 자신을 호출하는 방식이다. 큰 문제를 같은 형태의 작은 문제로 줄일 수 있을 때 사용한다.

언제 쓰는가

• 트리 탐색
• DFS
• 분할 정복
• 백트래킹
• 점화식 계산

핵심 조건

• 종료 조건이 있어야 한다.
• 호출할 때마다 문제가 작아져야 한다.
• 너무 깊어지면 스택 오버플로우가 날 수 있다.

참고자료

• Wikipedia - Recursion
• GeeksforGeeks - Recursion
• Python - sys.setrecursionlimit

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
long long factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}
 
int main() {
    cout << factorial(5) << '\n';
}

Python 코드

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)
 
print(factorial(5))