함수에서 재귀호출 사용하기

1. 재귀 호출이란?

재귀 호출이란 함수 내부에서 자기 자신을 다시 호출하는 방식입니다. 반복적인 구조를 가진 문제를 간결하게 표현할 수 있다는 장점이 있습니다.

아래는 팩토리얼(n!)을 재귀 호출로 구현한 예시입니다.

# n! 을 재귀 호출로 계산하는 함수
def factorial(n):
    if n == 1:        # 종료 조건
        return 1
    return n * factorial(n - 1)   # 자기 자신을 호출

print(factorial(5))  # 120

factorial(5)가 호출되면 내부적으로 다음과 같이 전개됩니다.

1. factorial(5) → 5 * factorial(4)
2. factorial(4) → 4 * factorial(3)
3. factorial(3) → 3 * factorial(2)
4. factorial(2) → 2 * factorial(1)
5. factorial(1) → 1 (종료 조건 도달)

이후 역순으로 값이 반환되며 최종적으로 5 * 4 * 3 * 2 * 1 = 120이 계산됩니다.

2. 종료 조건은 필수

재귀 호출을 사용할 때 반드시 종료 조건(base case)을 만들어줘야 합니다. 종료 조건이 없으면 함수가 무한히 자기 자신을 호출하다가 RecursionError가 발생합니다.

# ❌ 종료 조건 없음 → RecursionError 발생
def infinite():
    return infinite()

infinite()
# RecursionError: maximum recursion depth exceeded

# ✅ 종료 조건 있음 → 정상 동작
def countdown(n):
    if n == 0:        # 종료 조건
        print("끝!")
        return
    print(n)
    countdown(n - 1)  # 재귀 호출

countdown(3)
# 3
# 2
# 1
# 끝!

3. 재귀 호출 vs 반복문

재귀 호출은 반복문(for, while)으로도 동일하게 구현할 수 있습니다. 상황에 따라 적합한 방식을 선택하는 것이 중요합니다.