파이썬 재귀 함수를 이용해 자연수의 합 구하기

프로그래밍에서 재귀(recursion)란 함수가 자기 자신을 다시 호출하는 기법을 의미합니다. 자기 자신을 호출하는 함수를 재귀 함수(recursive function)라고 부르며, 무한 루프에 빠지는 것을 방지하기 위해 재귀 호출은 반드시 조건문 안에 위치시켜야 합니다.

재귀로 자연수의 합을 구하는 원리

자연수 n까지의 합은 다음과 같이 정의할 수 있습니다.

sum(n) = n + (n-1) + (n-2) + ... + 2 + 1

이 식을 재귀적으로 표현하면 sum(n) = n + sum(n-1)이 되고, 종료 조건(base case)은 n이 1 이하일 때 n을 그대로 반환하는 것입니다.

예제 코드

아래 프로그램은 사용자로부터 숫자를 입력받아 rsum() 함수에 인자로 전달합니다. rsum() 함수는 인자를 1씩 감소시키며 자기 자신을 재귀적으로 호출하다가, 값이 1에 도달하면 재귀 호출을 멈추고 결과를 반환합니다.

def rsum(n):
    if n <= 1:
        return n
    else:
        return n + rsum(n-1)

num = int(input("Enter a number: "))
ttl = rsum(num)
print("The sum is", ttl)

실행 결과

위 프로그램을 실행하고 10을 입력하면, 1부터 10까지 자연수의 합인 55가 출력됩니다.

Enter a number: 10
The sum is 55

동작 과정 살펴보기

입력값이 10일 때 rsum() 함수는 다음과 같은 순서로 동작합니다.

rsum(10) = 10 + rsum(9)
rsum(9) = 9 + rsum(8)
...
rsum(2) = 2 + rsum(1)
rsum(1) = 1 (종료 조건 도달)

각 호출의 결과가 거꾸로 거슬러 올라가면서 모두 더해져 최종적으로 55라는 값이 반환됩니다.

참고 사항

재귀 함수는 코드가 간결하고 직관적이라는 장점이 있지만, 입력값이 클 경우 함수 호출 스택이 깊어져 성능 저하나 스택 오버플로우가 발생할 수 있습니다. 파이썬은 기본적으로 약 1000번의 재귀 호출 깊이 제한이 있으므로, 큰 수의 합을 구할 때는 sum(range(1, n+1)) 같은 반복문 방식이나 가우스 공식 n*(n+1)//2를 사용하는 것이 효율적입니다.