파이썬 재귀 마스터하기: 함수가 스스로를 호출하는 방법

파이썬 재귀 마스터하기

파이썬 함수가 스스로를 호출하는 재귀의 메커니즘과 안전하고 효율적인 재귀 코드 작성 모범 사례를 알아봅니다.

재귀란?

재귀는 문제를 동일한 문제의 더 작은 인스턴스로 정의하는 기법입니다.

서로 마주 보는 두 평행 거울의 고전적 예시: 각 이미지는 다른 이미지의 재귀적 반사입니다.

파이썬 재귀 함수

파이썬에서 함수는 다른 함수를 호출할 수 있고, 자기 자신도 호출할 수 있습니다. 이런 구조를 재귀 함수라 합니다.

아래 이미지는 recurse라는 간단한 재귀 함수의 호출 스택을 보여줍니다:

고전적 예제: 양의 정수 x까지의 곱을 반환하는 팩토리얼 함수의 재귀 구현.

재귀 함수 예제

def factorial(x):
    """양의 정수의 팩토리얼을 재귀적으로 계산."""
    if x == 1:
        return 1
    return x * factorial(x - 1)
num = 3
print("The factorial of", num, "is", factorial(num))

출력

The factorial of 3 is 6

여기서 factorial()은 기본 케이스 x == 1에 도달할 때까지 자기 자신을 호출하는 재귀 함수입니다.

양의 정수로 호출되면 함수는 감소된 값으로 반복 호출:

factorial(3) # 1번째 호출, 3
3 * factorial(2) # 2번째 호출, 2
3 * 2 * factorial(1) # 3번째 호출, 1
3 * 2 * 1 # 3번째 반환
3 * 2 # 2번째 반환
6 # 1번째 반환

이 단계별 과정을 시각화한 이미지:

입력 값이 기본 조건(여기선 x == 1)에 도달하면 재귀 종료. 모든 재귀 함수는 이런 중단 기준이 있어야 하며, 없으면 무한히 계속되어 콜 스택 고갈.

파이썬은 무한 재귀로 인터프리터 크래시 방지를 위해 최대 재귀 깊이(기본 1000)를 강제. 초과 시 RecursionError 발생:

def recursor():
    recursor()
recursor()

출력

Traceback (most recent call last):
File "<string>", line 3, in <module>
File "<string>", line 2, in a
File "<string>", line 2, in a
File "<string>", line 2, in a
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

sys.setrecursionlimit()로 재귀 한도 조절 가능하지만 스택 오버플로 방지 위해 신중히 사용.

재귀의 장점

1. 재귀적 해법은 종종 더 간결하고 읽기 쉽다, 특히 본질적으로 재귀적인 문제에서.
2. 복잡한 작업을 더 단순한 하위 문제로 우아하게 분해 가능.
3. 수열 생성(피보나치, 순열 등)은 중첩 루프보다 재귀로 직관적.

재귀의 단점

1. 초보자에게 재귀 로직은 따라가기 어렵고 추론하기 힘들 수 있음.
2. 각 재귀 호출은 스택 공간 소비; 깊은 재귀는 메모리 집약적이고 반복 대안보다 느릴 수 있음.
3. 계층적 호출 스택 때문에 디버깅이 까다로움.

실전에서는 코드가 더 명확하고 유지보수하기 쉬우며 입력 크기가 적당할 때 재귀 선택. 매우 큰 입력이면 반복 접근이나 꼬리 재귀 최적화(지원 시) 고려.