31.2 재귀호출로 팩토리얼 구하기

이번에는 재귀호출을 사용하여 팩토리얼을 구현해보겠습니다. 팩토리얼은 1부터 n까지 양의 정수를 차례대로 곱한 값이며 !(느낌표) 기호로 표기합니다. 예를 들어 5!은 5 * 4 * 3 * 2 * 1이며 결과는 120입니다.

다음 내용을 IDLE의 소스 코드 편집 창에 입력한 뒤 실행해보세요.

factorial.py

def factorial(n):
    if n == 1:      # n이 1일 때
        return 1    # 1을 반환하고 재귀호출을 끝냄
    return n * factorial(n - 1)    # n과 factorial 함수에 n - 1을 넣어서 반환된 값을 곱함
 
print(factorial(5))

실행 결과

120

먼저 factorial 함수를 만들 때 매개변수 n을 지정해줍니다. 팩토리얼은 1부터 n까지의 곱을 구하는 문제인데 여기서는 n부터 역순으로 1씩 감소하면서 재귀호출을 하고 n이 1이 되었을 때 재귀호출을 중단합니다.

def factorial(n):
    if n == 1:      # n이 1일 때
        return 1    # 1을 반환하고 재귀호출을 끝냄

factorial 함수의 핵심은 반환값 부분입니다. 계산 결과가 즉시 구해지는 것이 아니라 재귀호출로 n - 1을 계속 전달하다가 n이 1일 때 비로소 1을 반환하면서 n과 곱하고 다시 결괏값을 반환합니다. 그 뒤 n과 반환된 결괏값을 곱하여 다시 반환하는 과정을 반복합니다.

    return n * factorial(n - 1)    # n과 factorial 함수에 n - 1을 넣어서 반환된 값을 곱함

factorial(5)를 호출해서 n이 1이 될 때까지 재귀호출하면 다음과 같은 모양이 됩니다.

그림 31-3 factorial 함수의 호출

이제 if n == 1:을 만나서 factorial 함수가 1을 반환합니다. 그 뒤 1과 2를 곱해서 2를 반환하고, 3과 2를 곱해서 6을 반환하고, 4와 6을 곱해서 24를 반환하고, 5와 24를 곱해서 120을 반환하게 됩니다.

그림 31-4 factorial 함수의 반환

factorial 함수의 계산 과정을 그림 하나로 표현하면 다음과 같은 모양이 됩니다.

그림 31-5 factorial 함수의 호출 순서와 계산 과정

지금까지 함수의 재귀호출에 대해 배웠습니다. 재귀호출로 'Hello, world!'를 출력하는 부분은 크게 어렵지 않았지만 팩토리얼을 구할 때는 반환값과 매개변수로 계산하는 부분이 좀 어려웠습니다. 초보자들은 재귀호출 함수를 읽을 수 있을 정도만 되어도 제대로 공부한 것입니다. 알고리즘을 재귀호출로 만드는 일은 많은 공부와 연습이 필요합니다. 따라서 하루 아침에 습득할 수 있는 내용이 아니므로 당장 이해가 되지 않는다고 해서 걱정할 필요는 없습니다.