재귀함수의 첫 번째 예로 팩토리얼 함수를 어떻게 구하는지 알아봅시다. n의 팩토리얼은 n! n! 이라고 표시합니다. 이는 1부터 n까지의 정수를 곱하는 단순한 연산입니다. 예를 들어 5!는 1, dot, 2, dot, 3, dot, 4, dot, 5, 즉 120입니다. (주의사항: 팩토리얼 함수를 언급할 때 나오는 모든 느낌표는 강조의 뜻이 아니라 팩토리얼 함수를 의미합니다)
팩토리얼 함수를 다루는 이유가 궁금하시죠? 이 함수는 사물의 순서를 정할 때 얼마나 많은 방법이 있는지, 또 어떤 것들을 조합할 때 얼마나 다양한 방법이 있는지 구할 때 매우 유용합니다. 예를 들어 n개의 물건을 배열하는 방법은 몇 개나 될까요? 첫 번째 물건을 배열하는 방법은 n가지입니다. 이런 각각의 n개의 선택에 대해, 두 번째 항목은 n, minus, 1 개의 선택을 할 수 있습니다. 그러므로 첫 번째와 두 번째 물건을 차례대로 배열하는 방법은 n, dot, left parenthesis, n, minus, 1, right parenthesis가지입니다. 이제 두 물건의 선택에 대해 세 번째 물건을 배열하는 방법은 n, minus, 2가지이므로 세 개의 물건을 순서대로 배열하는 방법은 n, dot, left parenthesis, n, minus, 1, right parenthesis, dot, left parenthesis, n, minus, 2, right parenthesis 가지입니다. 이와 같은 식으로 선택지가 2 가지, 그리고 마지막으로 한 가지만 남을 때까지 계속합니다. 모두 합하면 n 개를 배열하는 방법은 n(n1)(n2)21 n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1 가지입니다. 이는 간단히 n! n! (n 팩토리얼) 로 표현할 수 있습니다. 그렇지만 1에서 n까지 하나씩 증가하면서 곱하는 것이 아니라 n 부터 1까지 하나씩 감소하면서 곱합니다.
팩토리얼 함수가 유용한 또 다른 예는 여러 개 중에서 몇 개만 선택하는 경우의 수를 셀 때입니다. 예를 들어 여행을 갈 때 가져갈 티셔츠를 고른다고 합시다. 티셔츠가 n개 있지만 그 중 k개만 가져갈 수 있다고 합시다. n장의 티셔츠 중 k개의 티셔츠를 고를 수 있는 가지수는 얼마나 될까요? (여기서 증명하지는 않겠지만) 해답은 n!/(k!(nk)!) n! / (k! \cdot (n-k)!) 입니다. 이렇듯이 팩토리얼 함수는 매우 유용합니다. 여기를 클릭하면 순열과 조합에 대해 더 자세히 배울 수 있지만, 팩토리얼 알고리즘을 구현하기 위해 이것들을 공부할 필요는 없습니다.
팩토리얼 함수는 모든 양의 정수와 0에 대해 정의됩니다. 0! 의 값은 무엇이어야 할까요 ? 이는 1보다 크거나 같고 0보다 작거나 같은 모든 정수들의 곱입니다. 그렇지만 그런 정수는 존재하지 않습니다. 그러므로 0! 은 곱셈의 항등원인 1과 같다고 정의합니다. (0! 0! =1이라고 정의하는 것은 n 가지 중 k 개를 고르는 문제를 위한 공식에 적합합니다. n 개 중에서 n 개를 고르는 방법이 얼마나 있는지 알고 싶다고 합시다. 쉽죠. 왜냐하면 한 가지밖에 없으니까요. n 개 모두를 골라야 합니다. 그럼 이제 우리의 공식을 이용하면 n!/(n!(nn)!) n! / (n! \cdot (n-n)!) 은 1이 되어야 합니다. 그런데 (nn)! (n-n)! 은 0!입니다. 이제 n!/(n!0!) n! / (n! \cdot 0!) 는 1이 되어야 한다는 것을 알게 되었습니다. n! n! 을 분자와 분수에서 모두 약분하면 1/(0!) 1/(0!) 이 1이 되어야 한다는 것을 알 수 있습니다. 실제로 0! = 1이기 때문입니다.)
이제 n! n! 에 대해 알아볼 수 있는 방법이 생겼습니다. n, equals, 0일 때는 1입니다. n이 양수일 때는 12(n1)n 1 \cdot 2 \cdots (n-1) \cdot n 과 같습니다.

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