양수 값인 n에 대해 n! n! 를 작성해 봅시다. 이전에 했던 것처럼 n에서 시작해서 1이 될 때까지 계속 숫자를 곱하는 것입니다: n! n! = n(n1)21 n \cdot (n-1) \cdots 2 \cdot 1 그런데 (n1)! (n-1)! 를 구하는 또 다른 방법으로 (n1)21 (n-1) \cdots 2 \cdot 1 이므로 n!=n(n1)! n! = n \cdot (n-1)! 라고도 할 수 있습니다. 방금 어떻게 했죠? n! n! (n1)! (n-1)! 의 곱으로 표현했습니다. (n1)! (n-1)! 를 계산한 후 (n1)! (n-1)! 의 결과와 n을 곱해서 n! n! 을 계산할 수 있다는 것입니다. n의 팩토리얼 함수는 먼저 n, minus, 1 팩토리얼 함수를 계산해서 구할 수 있는데, (n1)! (n-1)! 를 계산하는 것은 n! n! 을 계산하는 하위 문제에 해당합니다.
예를 들어 5!를 계산해 봅시다.
  • You can compute 5! as 54! 5 \cdot 4! .
  • Now you need to solve the subproblem of computing 4!, which you can compute as 4, dot, 3!.
  • Now you need to solve the subproblem of computing 3!, which is 32! 3 \cdot 2! .
  • Now 2!, which is 21! 2 \cdot 1! .
  • Now you need to compute 1!. You could say that 1! equals 1, because it's the product of all the integers from 1 through 1. Or you can apply the formula that 1!=10! 1! = 1 \cdot 0! . Let's do it by applying the formula.
  • We defined 0! to equal 1.
  • Now you can compute 1!=10!=1 1! = 1 \cdot 0! = 1 .
  • Having computed 1!=1 1! = 1 , you can compute 2!=21!=2 2! = 2 \cdot 1! = 2 .
  • Having computed 2!=2 2! = 2 , you can compute 3!=32!=6 3! = 3 \cdot 2! = 6 .
  • Having computed 3!=6 3! = 6 , you can compute 4!=43!=24 4! = 4 \cdot 3! = 24 .
  • Finally, having computed 4!=24 4! = 24 , you can finish up by computing 5!=54!=120 5! = 5 \cdot 4! = 120 .
So now we have another way of thinking about how to compute the value of n! n! , for all nonnegative integers n:
  • If n, equals, 0, then declare that n!=1 n! = 1 .
  • Otherwise, n must be positive. Solve the subproblem of computing (n1)! (n-1)! , multiply this result by n, and declare n! n! equal to the result of this product.
n! n! 을 이런 식으로 계산하면 즉석에서 답을 구할 수 있는 첫 번째 조건을 탈출 조건이라고 부르고, 다른 값에 대한 같은 함수를 계산하는 두 번째 케이스를 재귀 조건이라고 합니다.

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