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이 될 때까지 재귀호출하면 다음과 같은 모양이 됩니다.
이제 if n == 1:을 만나서 factorial 함수가 1을 반환합니다. 그 뒤 1과 2를 곱해서 2를 반환하고, 3과 2를 곱해서 6을 반환하고, 4와 6을 곱해서 24를 반환하고, 5와 24를 곱해서 120을 반환하게 됩니다.
factorial 함수의 계산 과정을 그림 하나로 표현하면 다음과 같은 모양이 됩니다.
지금까지 함수의 재귀호출에 대해 배웠습니다. 재귀호출로 'Hello, world!'를 출력하는 부분은 크게 어렵지 않았지만 팩토리얼을 구할 때는 반환값과 매개변수로 계산하는 부분이 좀 어려웠습니다. 초보자들은 재귀호출 함수를 읽을 수 있을 정도만 되어도 제대로 공부한 것입니다. 알고리즘을 재귀호출로 만드는 일은 많은 공부와 연습이 필요합니다. 따라서 하루 아침에 습득할 수 있는 내용이 아니므로 당장 이해가 되지 않는다고 해서 걱정할 필요는 없습니다.