What if you can take a large complex problem and solve it by solving a slightly smaller or simpler problem.
Imagine that you know how to 1. compute the solution to a slightly smaller size problem. And 2. relate that sub-solution to the ultimate solution to the larger problem at hand. This is the essence of the concept of recursion in computer programs. Recursion is best illustrated with concrete examples, here are two:
Example 1 Fibonacci Sequence
You may remember the Fibonacci sequence from school. It's a series of numbers where each number is the sum of the previous two numbers.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55
Those are the first 10 Fibonacci numbers. Imagine writing a function fib that returns the nth Fibonacci number. So for n = 10 it would return 55, which is 34 + 21. It would be defined like this from the definition:
fib(n) = fib(n-1) + fib(n-2)
Notice that on the right hand side we're calling the same function that we're trying to define. That is a recursive function definition. Defining a recursive function involves two things — calling the same function with a smaller input and defining a base case. The above show the recursive function calls. This intuitively makes sense from the definition of Fibonacci sequence. What is the base case?
The base case is a way for the function to be able to return a value without calling itself. Because we need a way to end the chain of function calls. In this case the base case can be defined as "just return 1 for n = 1 or n =2 ". When defining the base case, we don't make any recursive function calls.
In the illustration above, our goal is to compute the 5th Fibonacci number. We know intuitively that we can add the 4th and 3rd fib numbers and get the answer. How would a computer program do it recursively?
The orange arrow represents the base case. The green number is the answer that can be added and 'rolled up' to get the answer to the previous function call. You can see that in order to compute the 5th fib number we end up calling the fib function 8 times. Here's a function definition:
function fib(n) {
if (n <= 2) return 1;
return ( fib(n-1) + fib(n-2) );
}
Example 2: Tower of Hanoi
Play this Tower of Hanoi game if possible to get a feel for the rules. You'll also experience why the game gets challenging quickly as you increase the number of disks.
The objective for Tower of Hanoi is to move all of the disks from source peg A to target peg B while using peg C as a temporary storing place. There are two basic rules: you can only move one disk at a time and you cannot place a larger disk on top of a smaller disk at any time.
So let's do a thought experiment: image a tower with 3 disks. You can move it easily, you can imagine all of the steps ahead of time, and you can visualize the moves. Would you believe that the process of moving 3 disks can be extrapolated to move 10 disks, or 25 disks or 50 or a 100!
However most of us cannot imagine the moves ahead of time or hold them all in our head at the same time. The number of moves for 3 disks is 7. For 4 disks it's 15, and for 5 disks it's 31. It makes sense that we can't imagine the steps beyond 3 disks. It has been shown that our brains can only hold 4 to 7 distinct things in our short term memory. In this case the number of moves increases exponentially with the number of disks.
Applying the concept of recursion to Tower of Hanoi we can get to a logical place where we're confident that we can solve the game for any number n (given sufficient time and patience!). Here's how we can intuitively think about the solution: in order to move n disks from Peg A to Peg B, we have to know how to
Move n-1 disks from Peg A to Peg C, the temporary peg.
Then move the last disk (the largest disk) from Peg A to Peg B.
Then use the same process used in step 1 to move the n-1 disks currently on Peg C over to Peg B, the target peg.
You end up with all n disks on Peg B, which was the goal.
You can see that at the essence of this solution is the concept of recursion. So what about the base case? The base case is n = 1 disk. Well that's easy right, we just pick it up and move it. So you may be thinking "are you saying if I know how to move one disk, I know how to move 100 disks?" Yes, that's exactly right. This may not feel intuitively satisfying but it's true. In order to move 100 disks, you need to know how to move 99 disks. But to move 99 disks, you only need to know how to move 98 disks...in order to move 3 disks you only need to know how to move 2 disks and for 2 disks we need only know how to move 1 disk. Aha! and we know how to do that, that is our base case.
[Aside - so we know how to move 100 disks, but that doesn't imply that it's easy or low effort. As we saw earlier the number of moves increase quickly. For 100 disks, it would take 2100 - 1 moves, which is a 31 digits long decimal number!]
Now you know the essence of The Thing called Recursion in programming. You can see that it's a very powerful concept. We cannot imagine or hold all of the steps for a solution in our head but we can easily write a computer program to solve problems this way.
Top comments (0)