Recursion is essentially the idea of solving a complex problem by breaking it down into simple ones. The initial problem is broken into a base case and a recursive case. The base case is the single unit from which we can derive the rest of our answer. Consider an example where we’re asked to compute the factorial of 5, or 5!
5! equals 5*4*3*2*1 = 120. To compute this using recursion, we need to identify a base case. In this example, we can set the base case to 0! = 1. To solve this recursively, we must construct a recursive case which approaches the base case as it reduces the problem down to its simplest form. We can do this as follows:
n! = n * (n-1)!
In the case of 5!, n equals 5, so let’s plug it into our recursive function:
5! = 5 * (4!)
If we examine 4!, the following is true:
4! = 4 * (3!)
We still haven’t reached the base case where 0! = 1, which is an actual value we can return, as opposed to the iterative reduction of the problem in terms of the previous one. The rest of the computation proceeds as follows:
5! = 5 * (4!)
= 5 * 4 * (3!)
= 5 * 4 * 3 * (2!)
= 5 * 4 * 3 * 2 * (1!)
= 5 * 4 * 3 * 2 * 1 * 0!
Now we have reached the base case. We know that 0! equals 1. This allows us to walk back up the stack as follows:
5! = 5 * 4 * 3 * 2 * 1
5! = 5 * 4 * 3 * 2
5! = 5 * 4 * 6
5! = 5 * 24
5! = 120
And that’s our answer. The key to recursion is finding a base case which you can approach from your initial problem. From there, it’s just a matter of letting the computer race down to the base case before returning with the answer.
