재귀를 활용한 팩토리얼

양수 값인 $n$‍에 대해 $n!$‍를 작성해 봅시다. 이전에 했던 것처럼 $n$‍에서 시작해서 1이 될 때까지 계속 숫자를 곱하는 것입니다: $n!$‍ = $n\cdot (n-1)\cdots 2\cdot 1$‍ 그런데 $(n-1)!$‍를 구하는 또 다른 방법으로 $(n-1)\cdots 2\cdot 1$‍이므로 $n!=n\cdot (n-1)!$‍라고도 할 수 있습니다. 방금 어떻게 했죠? $n!$‍을 $(n-1)!$‍의 곱으로 표현했습니다. $(n-1)!$‍를 계산한 후 $(n-1)!$‍의 결과와 $n$‍을 곱해서 $n!$‍을 계산할 수 있다는 것입니다. $n$‍의 팩토리얼 함수는 먼저 $n-1$‍ 팩토리얼 함수를 계산해서 구할 수 있는데, $(n-1)!$‍를 계산하는 것은 $n!$‍을 계산하는 하위 문제에 해당합니다.

예를 들어 5!를 계산해 봅시다.

이제 모든 음이 아닌 정수 $n$‍에 대하여 $n!$‍을 계산하는 또 다른 방법을 알게 되었습니다.

$n!$‍을 이런 식으로 계산하면 즉석에서 답을 구할 수 있는 첫 번째 조건을 탈출 조건이라고 부르고, 다른 값에 대한 같은 함수를 계산하는 두 번째 케이스를 재귀 조건이라고 합니다.

위 자료는 다트머스 대학교 컴퓨터공학과의 토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.