Recursive factorial

For positive values of nn, let's write n!n! as we did before, as a product of numbers starting from nn and going down to 1:n!=n(n1)211: n! = n⋅(n−1)⋯2⋅1. But notice that (n1)2(n−1)⋯211 is another way of writing (n1)!(n−1)!, and so we can say that n!=n(n1)!n! = n⋅(n−1)!. Did you see what we just did? We wrote n!n! as a product in which one of the factors is (n1)!(n−1)!. We said that you can compute n!n! by computing (n1)!(n−1)! and then multiplying the result of computing (n1)!(n−1)! by nn. You can compute the factorial function on n by first computing the factorial function on n1n−1. We say that computing (n1)!(n-1)! is a subproblem that we solve to compute n!n!.

Let's look at an example: computing 5!5!.

  • You can compute 5!5! as 54!5⋅4!.

  • Now you need to solve the subproblem of computing 4!4!, which you can compute as 43!4⋅3!.

  • Now you need to solve the subproblem of computing 3!3!, which is 32!3⋅2!.

  • Now 2!2!, which is 21!2⋅1!.

  • Now you need to compute 1!1!. You could say that 1!1! equals 11, because it's the product of all the integers from 11 through 11. Or you can apply the formula that 1!=10!1! = 1⋅0!. Let's do it by applying the formula.

  • We defined 0!0! to equal 11.

  • Now you can compute 1!=10!=11! = 1⋅0!=1.

  • Having computed 1!=11! = 1, you can compute 2!=21!=22! = 2⋅1! = 2.

  • Having computed 2!=22! = 2, you can compute 3!=32!=63! = 3⋅2! = 6.

  • Having computed 3!=63! = 6, you can compute 4!=43!=244! = 4⋅3! = 24.

  • Finally, having computed 4!=244! = 24, you can finish up by computing 5!=54!=1205! = 5⋅4! = 120.

So now we have another way of thinking about how to compute the value of n!n!, for all non-negative integers nn:

  • If n=0n = 0, then declare that n!=1n! = 1.

  • Otherwise, nn must be positive. Solve the subproblem of computing (n1)!(n−1)!, multiply this result by nn, and declare n!n! equal to the result of this product.

When we're computing n!n! in this way, we call the first case, where we immediately know the answer, the base case, and we call the second case, where we have to compute the same function but on a different value, the recursive case.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy