파이썬 재귀 함수로 팩토리얼(계승)을 구하는 방법

재귀(recursion)는 함수가 자기 자신을 다시 호출하는 프로그래밍 기법입니다. 파이썬에서는 이 기법을 활용하면 팩토리얼(계승)처럼 반복 구조를 가진 문제를 매우 간결한 코드로 해결할 수 있습니다.

팩토리얼은 1부터 n까지의 모든 양의 정수를 곱한 값으로, 보통 n!로 표기합니다. 예를 들어 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720입니다.

재귀 함수 예제

다음 코드는 n = 6과 n = 15에 대한 팩토리얼을 계산합니다.

def factorial(n):
    if n == 1:
        return 1
    else:
        res = n * factorial(n-1)
    return res
print ("factorial(6) = %d" %factorial(6))
print ("factorial(15) = %d" %factorial(15))

출력 결과

위 코드를 실행하면 다음과 같은 결과를 얻습니다.

C:/Users/TutorialsPoint1/~.py
factorial(6) = 720
factorial(15) = 1307674368000

동작 원리

factorial(n) 함수는 먼저 종료 조건(base case)인 n == 1을 확인합니다. n이 1이면 더 이상 재귀 호출 없이 1을 반환하여 재귀를 멈춥니다. 그렇지 않으면 n * factorial(n-1)을 계산하면서 자기 자신을 호출하고, 인자가 하나씩 줄어들어 결국 종료 조건에 도달하게 됩니다.

예를 들어 factorial(6)의 호출 과정은 다음과 같이 전개됩니다.

factorial(6)
= 6 * factorial(5)
= 6 * 5 * factorial(4)
= 6 * 5 * 4 * factorial(3)
= 6 * 5 * 4 * 3 * factorial(2)
= 6 * 5 * 4 * 3 * 2 * factorial(1)
= 6 * 5 * 4 * 3 * 2 * 1
= 720

주의 사항

재귀 함수에는 반드시 종료 조건이 있어야 합니다. 종료 조건이 없으면 함수가 무한히 자신을 호출하다가 파이썬의 최대 재귀 깊이(기본값 약 1000)를 초과하여 RecursionError가 발생합니다. 또한 n = 0의 경우도 처리하려면 종료 조건을 if n <= 1: return 1 형태로 수정하면 됩니다.