Thinking Recursively
One of the most important programming constructs that can be learned is recursive programming. To most, it's a mystery. To some it's a source of endless frustration. However, once recursion is mastered, many other data structures become relatively easy.
So, what exactly is recursion? Put simply, recursion is the process of taking a larger problem and breaking it down into smaller problems that are each solved in the exact same way. In recursive programming, you first establish a base case or stopping case (I prefer to call it an "escape clause"). It is this base case that prevents your program from recursively calling itself to infinity (that's not necessarily true I suppose. The computer would eventually crash due to the exhaustion of memory). Once a base case is established, recursive calls are created, and they're usually conditional (if/else).
Before we get into code, let's illustrate recursion with a simple real life example: climbing a stair case. The larger problem is getting up (or maybe down) a flight of stairs. It can be broken down into many smaller similar problems - walking up steps. Think about it: to reach the end of the stair case, you have to take a step. This process is repeated until you reach the base/stopping case. So, what's the base/stopping case? If you said, "when I reach the top/bottom of the stairs", you're starting to think recursively! Another example could be tracing your family tree. What is the larger problem to solve? What is the base case? What are the recursive steps? Think about these for a moment...
Now that you're back, let's get into some code. We'll start with a simple example: calculating the factorial of a number (known colloquially as the "hello world" of recursion). As a reminder, you calculate a factorial of a number by multiplying the number by one less than the number. You then take the number that was decremented and multiply it times one less than that number. The process is repeated until you reach zero, in which case you can no longer calculate the factorial. As an example, to calculate the factorial of 3: (3*2*1). My code is in C, though you could use any language that supports recursive function calls.
unsigned factorial(unsigned number)
{
if(number == 0)
return 1;
return number * factorial(number-1);
}
The function takes an unsigned integer as its argument. The first line in the function body is the base case. If the number is equal to zero, there is no more work to be done so a 1 is returned and the function ceases to recursively call itself. Notice this code is at the top of the function. The return call does all the work. It multiplies the current number by what appears to be a function call! In reality, it's doing what you'd expect in order to calculate a factorial, although it's probably confusing at first. Let's trace the function in order to see exactly what happens.
We'll use the number 4 as input.
1. To begin, 4 is passed into the function. It is not equal to zero so the line of code with "return" is reached and factorial() is called on "number-1" or 3.
2. The number 3 is not equal to zero, so the return line is called once again, this time with an argument of 2.
3. The number 2 is not equal to zero, so the return line is called again, this time with an argument of 1.
4. The number 1 is not equal to zero. Yep, the return line is called again and factorial is passed zero as an argument.
5. The number zero is equal to zero. A-ha! We've hit our stopping case, but where do we go from here? The next line of code with "return 1" is executed. But where do we return to? Just like any other function, we return to whatever called us. In this case, it was the previous instance of factorial() in step 4. We return there and multiply 1 times the result of what was returned from the stopping case, or 1.
6. With that, the cascade of returns ensues... We now return to step 3 and multiply 2 times 1 and return that to step 2.
7. The number 3 in step 2 is multiplied with the 2 that was returned from step 3. The result, 6, is returned to step 1.
8. The number 6 from step 2 is multiplied with 4 and returned to the function that made the original call to factorial(), likely a printf() call. That's it!
Though there are many steps in recursion, they all do very simple things. In this case a comparison is made with the argument to the factorial function to see if it's equal to zero. If it is, the function returns with no further recursive calls.
So what exactly is the benefit of all this? The first benefit is simpler code. You could write the factorial code using a for loop or while loop but you'd write more code than doing it recursively. A second benefit is that the code is simpler and easier to follow (assuming you understand recursion!). A third benefit is that more complex data structures such as trees and heaps are all but impossible without recursion. Recursion isn't beneficial everywhere though. If you're working with large amounts of data, it may well be faster to use iterative loops such as a for loop over recursion, due to the need to put data on the stack for each recursive call. It's up to you to decide.
As a parting exercise, see if you can figure out what this code does:
void write_binary(int n)
{
if (n == 0 || n == 1)
printf("%d", n);
else
{
write_binary(n/2);
printf("%d", n % 2);
}
}