파이썬 재귀 함수 작성 방법: 개념부터 예제까지

재귀(Recursion)는 함수가 자기 자신을 본문 안에서 한 번 이상 호출하는 프로그래밍 기법입니다. 일반적으로 함수는 자신을 호출한 결과의 반환값을 그대로 반환하며, 이런 방식으로 정의된 함수를 '재귀 함수(recursive function)'라고 부릅니다.

재귀 함수의 종료 조건

재귀 함수가 프로그램에서 정상적으로 동작하려면 반드시 종료되어야 합니다. 재귀 호출이 일어날 때마다 해결해야 할 문제의 크기가 점점 작아지고, 더 이상 추가적인 재귀 없이도 답을 구할 수 있는 기저 사례(base case)에 도달해야 합니다. 만약 호출 과정에서 기저 사례가 충족되지 않으면 재귀는 무한 루프에 빠져 프로그램이 멈추거나 오류가 발생할 수 있습니다.

예제: n개 자연수의 합 구하기

다음 코드는 파이썬 재귀 함수를 사용하여 처음 n개의 자연수 합을 구하는 예제입니다.

def sum_n(n):
    if n == 0:
        return 0
    else:
        return n + sum_n(n-1)

이 함수의 동작 원리는 간단합니다. 예를 들어 sum_n(5)를 호출하면 다음과 같이 계산됩니다.

5 + sum_n(4) → 5 + 4 + sum_n(3) → ... → 5 + 4 + 3 + 2 + 1 + 0 = 15

n이 0이 되면 재귀 호출이 멈추고, 각 단계의 값들이 거꾸로 더해지면서 최종 합계가 반환됩니다.

아래 코드는 첫 100개 자연수의 합과 첫 500개 자연수의 합을 출력합니다.

print(sum_n(100))
print(sum_n(500))

실행 결과

5050
125250

주의 사항

파이썬은 무한 재귀로 인한 메모리 고갈을 방지하기 위해 기본적으로 재귀 호출 깊이를 약 1,000회로 제한합니다. 따라서 매우 큰 n 값을 입력하면 RecursionError가 발생할 수 있으며, 이 경우 sys.setrecursionlimit()으로 제한을 조정하거나 반복문 기반의 알고리즘으로 전환하는 것이 좋습니다.