# Recursive factorial

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

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

• You can computeÂ $5!$Â asÂ $5â‹…4!$.

• Now you need to solve the subproblem of computingÂ $4!$, which you can compute asÂ $4â‹…3!$.

• Now you need to solve the subproblem of computingÂ $3!$, which isÂ $3â‹…2!$.

• NowÂ $2!$, which isÂ $2â‹…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! = 1â‹…0!$. Let's do it by applying the formula.

• We definedÂ $0!$Â to equalÂ $1$.

• Now you can computeÂ $1! = 1â‹…0!=1$.

• Having computedÂ $1! = 1$, you can computeÂ $2! = 2â‹…1! = 2$.

• Having computedÂ $2! = 2$, you can computeÂ $3! = 3â‹…2! = 6$.

• Having computedÂ $3! = 6$, you can computeÂ $4! = 4â‹…3! = 24$.

• Finally, having computedÂ $4! = 24$, you can finish up by computingÂ $5! = 5â‹…4! = 120$.

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

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

• Otherwise,Â $n$Â must be positive. Solve the subproblem of computingÂ $(nâˆ’1)!$, multiply this result byÂ $n$, and declareÂ $n!$Â equal to the result of this product.

When we're computingÂ $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.