[Algorithm] 재귀(Recursion) 알고리즘

재귀란?

재귀(Recursion)는 함수가 자기 자신을 호출하는 방식으로 문제를 해결하는 알고리즘 기법이다. 보통 하나의 큰 문제를 동일한 구조를 가진 더 작은 하위 문제로 나누어 해결하는 방식으로, 수학적 귀납법과 유사한 방식으로 작동한다.

재귀는 반복문처럼 루프를 돌며 문제를 해결할 수 있지만, 특히 트리 구조, 분할 정복, 백트래킹 등의 알고리즘에서는 반복문보다 재귀가 더 자연스럽고 간결한 표현되는 경우가 많다.

 

알고리즘 구조

재귀 함수는 보통 두 가지 핵심 요소로 구성된다:

1. 기저 조건(Base Case)
   더 이상 재귀를 진행하지 않고 함수를 종료시키는 조건이다. 반드시 필요하며, 없을 경우 무한히 자기 자신을 호출하게 되어 스택 오버플로우(Stack Overflow) 가 발생한다.
2. 재귀 호출(Recursive Call)
   문제를 더 작은 문제로 나누고, 그 하위 문제를 해결하기 위해 자기 자신을 호출하는 부분이다. 보통 이 재귀 호출을 통해 점점 기저 조건에 가까워지게 만든다.

예를 들어, 자연수 n에 대한 팩토리얼(factorial)은 다음과 같이 정의된다.

• 0! = 1
• n! = n × (n-1)!

이 정의를 그대로 코드로 표현하면 다음과 같다:

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

 

여기서 함수 factorial(5)를 호출하면 다음과 같은 흐름으로 실행된다:

factorial(5)
→ 5 * factorial(4)
→ 5 * 4 * factorial(3)
→ 5 * 4 * 3 * factorial(2)
→ 5 * 4 * 3 * 2 * factorial(1)
→ 5 * 4 * 3 * 2 * 1 * factorial(0)
→ 5 * 4 * 3 * 2 * 1 * 1 = 120

 

재귀는 이렇게 호출이 깊어지면서 결과 계산을 지연시키다가, 기저 조건에 도달하면 스택을 역방향으로 풀며 계산을 완성한다. 이처럼 재귀는 스택 구조와 밀접하게 연결되어 있으며, 함수 호출이 후입선출(LIFO) 방식으로 작동하는 점이 핵심이다.

 

 

특징과 장단점

재귀는 복잡한 반복 구조를 간결하게 표현할 수 있다는 점에서 매우 유용하다. 특히 문제의 정의 자체가 재귀적인 경우, 반복문보다 훨씬 직관적이고 깔끔한 구현이 가능하다.

하지만 단점도 분명하다. 각 함수 호출마다 스택 메모리가 사용되기 때문에, 호출 깊이가 깊어지면 스택 오버플로우(Stack Overflow) 에러가 발생할 수 있다. 파이썬에서는 기본적으로 재귀 깊이가 1000번을 넘기면 RecursionError가 발생한다.

또한, 중복 호출이 있는 경우에는 성능이 급격히 저하될 수 있다. 대표적으로 피보나치 수열을 단순 재귀로 구현할 경우, 같은 값이 여러 번 계산되어 비효율적이다. 이런 경우 메모이제이션(Memoization) 이나 동적 계획법(DP) 을 통해 중복 계산을 줄여야 한다.

# 메모이제이션을 활용한 피보나치 예시
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

 

재귀 문제를 더 잘 풀기 위한 사고 전략

재귀는 단순히 함수가 자기 자신을 호출하는 기술이 아니라, 문제를 어떻게 쪼갤지, 그리고 그 쪼갠 문제를 어떻게 다시 합쳐서 원래 문제를 풀지에 대한 전략적인 사고가 필요하다는 걸 문제를 풀수록 더 실감하게 된다.

직접 재귀 문제를 여러 개 풀어보면서, 처음에 막혔던 부분이 뚫렸던 순간들이 있었다. 그때 '재귀는 이렇게 생각해야 하는 거구나' 하고 느꼈던 몇 가지를 아래에 정리해본다.

 

1. 문제를 “내가 푸는 게 아니라 다음 호출에게 넘긴다”는 관점으로 본다

재귀는 내가 전체를 직접 다 해결하는 방식이 아니라, 내가 일부만 처리하고 나머지는 '나보다 한 단계 작은 문제'에게 위임하는 방식이다. 이 감각을 키우면 대부분의 재귀 문제는 자연스럽게 풀린다.

 

예시: 리스트 뒤집기

def reverse(arr):
    if len(arr) <= 1:
        return arr
    return reverse(arr[1:]) + [arr[0]]

 

이 함수는 "나머지는 다음 함수가 알아서 뒤집고, 나는 맨 앞 원소만 뒤에 붙이겠다"는 구조를 갖는다.

 

2. 호출 흐름을 직접 따라가 보자 (트리 구조)

재귀 함수는 내부적으로 호출 트리(Call Tree) 를 형성한다.
예를 들어 fib(4)를 호출하면 다음과 같은 구조가 만들어진다:

fib(4)
├── fib(3)
│   ├── fib(2)
│   │   ├── fib(1)
│   │   └── fib(0)
│   └── fib(1)
└── fib(2)
    ├── fib(1)
    └── fib(0)

 

이런 호출 트리를 직접 그려보거나, print로 흐름을 찍어보는 것만으로도 큰 도움이 된다. 특히 DFS, 백트래킹 같은 문제를 풀 때는 재귀 호출 흐름을 시각화할 수 있는 능력이 문제 해결력을 크게 높여준다.

 

3. 재귀가 적합한 문제 유형을 구별하자

다음과 같은 구조를 가진 문제들은 재귀가 매우 잘 어울린다:

• 트리 구조: 이진 트리 탐색, 전위/중위/후위 순회
• 분기 구조: 모든 경우를 탐색해야 하는 순열/조합 문제
• 분할 정복: 문제를 쪼개서 푸는 병합 정렬, 퀵 정렬, 하노이의 탑
• 문제 정의 자체가 재귀적인 경우: 팩토리얼, 피보나치, 하노이의 탑 등

반대로 아래와 같은 문제는 반복문이 더 적합하다:

• 누적합, 슬라이딩 윈도우, 정해진 횟수만큼 순회하는 문제
• 메모리 사용량이 적고 성능이 중요한 상황

 

4. 처음 마주친 재귀 문제는 이렇게 접근하자

• 기저 조건을 먼저 세운다
  • 언제 재귀를 멈출지를 가장 먼저 생각한다
• 작은 입력부터 직접 풀어본다
  • 예: 입력이 0, 1, 2일 때 어떤 일이 벌어지는지 손으로 계산해 보자
• print로 호출 흐름을 찍어본다
  • 재귀는 눈으로 보기 전까지는 구조 파악이 어렵다
• 중복 호출 여부를 확인한다
  • 성능이 떨어진다면 메모이제이션이나 반복문 방식으로 전환