재귀 함수

재귀 함수(recursion)는 어떤 문제를 해결할 때 그 문제와 동일한 구조를 가진 더 작은 문제로 쪼갠 뒤, 그 작은 문제를 다시 자기 자신에게 맡기는 방식이다. 이 개념을 처음 들으면 어렵게 느껴지지만, 사실 상자 속에 상자가 계속 들어 있는 구조처럼, 큰 문제 안에 작은 문제가 반복적으로 등장하는 상황을 떠올리면 금방 이해된다. 예를 들어 팩토리얼 n!을 계산할 때 n! = n × (n-1)! 이라는 규칙을 이용하면, 더 이상 쪼갤 수 없는 순간인 1!에 도달할 때까지 같은 형태의 문제를 반복하게 되는데 이것이 재귀의 가장 대표적인 형태다. 실제 코드로 표현하면 다음과 같이 매우 간단하다.

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

이처럼 재귀는 트리 탐색, 그래프 탐색, 하노이 탑, 분할정복 알고리즘, 조합·순열 생성처럼 문제를 작은 조각으로 나누는 과정이 명확할 때 효과적이다. 하지만 장점만 있는 것은 아니다. 재귀는 호출될 때마다 스택 프레임을 새로 쌓기 때문에 메모리 사용량이 증가하고, 재귀 호출 깊이가 커지면 파이썬의 경우 기본 제한을 넘어서 RecursionError가 발생할 수도 있다. 또한 종료 조건을 잘못 설정하면 함수가 끝없이 호출되므로 항상 base case를 가장 먼저 점검해야 한다.

시간 복잡도 측면에서 보면, 재귀 함수의 비용은 “얼마나 많은 재귀가 호출되는지”와 “각 호출에서 어떤 작업을 수행하는지”에 의해 결정된다. 예를 들어 factorial처럼 한 번 호출할 때마다 딱 한 번만 자기 자신을 다시 호출하는 구조는 깊이가 n이므로 O(N) 시간이 든다. 하지만 하노이 탑처럼 매 번 재귀 호출이 두 번씩 발생하는 구조는 T(n) = 2T(n-1) + 1 형태가 되고, 이는 결국 O(2^N)까지 치솟는다. 반대로 이진 탐색을 재귀로 구현하면 매 호출마다 탐색 범위가 절반씩 줄어들어 O(logN) 시간이 걸리는 방식이 된다. 즉, 재귀는 겉보기에는 단순해 보이지만, 문제가 분기되는 구조인지, 단일 경로인지, 분할정복인지에 따라 성능이 크게 달라지기 때문에 재귀 호출 패턴을 항상 주의 깊게 살펴야 한다.

정리하면 재귀 함수는 “큰 문제를 더 작은 문제로 쪼개고, 그 작은 문제를 자기 자신이 다시 해결한다”는 구조를 가진 도구이며, 트리나 분할정복처럼 구조적으로 반복되는 문제를 해결할 때 코드가 매우 자연스럽고 간결해진다. 하지만 스택 사용량 증가, 깊이 제한, 종료 조건 실수 등 주의해야 할 점도 있으므로 장단점을 모두 이해한 상태에서 사용하는 것이 좋다.