Recursion

Recursion is an idea that seems very hard to ‘get’. Thinking about it doesn’t come naturally to most, myself included. While I can’t help you get to an ‘ah-ha!’ moment, I do have a mental framework for how to very quickly build a certain class of recursive function.

First, what’s recursion? It’s anything that repeats itself in a self-similar way. For programming, this can be generalized to the idea of it being a function that calls itself repeatedly to do its task. A simple C++ example for calculating a factorial is this:

int factorial ( int x ) {
if ( x == 1 ) return 1;
return ( x * ( factorial( x - 1) );
}

You’ll notice in the return statement, the factorial function calls itself again; that is a really simple example of recursion. This calculation could also be done iteratively, that is to say, using a loop or goto instead. I could also recode it to use a specialized variant of recursion known as tail recursion, which can be more efficient, but for now, I’m going to stick to keeping it simple.

So, the first step that should be asked when making a recursive function, is if recursion is really necessary? While recursion can make for some neatly compact code and looks very clever, there are trade-offs associated. One of them is, in fact, cleverness. Coding to be clever can often backfire when you or somebody else has to go back and try to understand what the hell it was you were trying to do. Another tradeoff can be in performance. When a function calls itself, it is making a new copy of itself to do so. Every new recursive call is putting more and more data on the stack. A simple iteration loop avoids this problem.

So, we’ve decided to plow on ahead anyway, and make a recursive function. My first step is to start with the final step, or the simplest step of the recursion. What is the very smallest version of the problem I am dealing with?

For the factorial problem, it’s the factorial of 1. You don’t need to even do any multiplication for that; just return 1. For making a list or a tree, it’s adding a node to the empty list or tree. For the fibonacci sequence, I actually have two ‘simplest’ conditions, the first two numbers in the sequence, 1 and 1. So I start with that.

Now, I go to the next most complicated step, and think about what’s needed. For the factorial, I now need to do some multiplication. What’s factorial of 2? That’s 2 * 1 = 2, or the more complicated case ( 2 ) multiplied by my ‘end’ simplest case of 1. You can see how this is accomplished in the code above. For making a list or tree, well, I need to traverse the list. So I check that the next node in line, using whatever sorting method ( or none at all ) I fancy. If the next node is null, or the next node is the one -just before- where I need to do an insertion, do the insertion; otherwise, call the function again, but this time with the address of the next node in line. For the fibonacci sequence, it’s a little more complicated, but not much. Since the fibonacci sequence is the sum of the two previous numbers in the sequence, I just need to make my return statement something like return ( fib( n-2 ) + ( fib n-1 ) );

And that’s it. Make sure my code does what I want it to, and call it done. It’s really that simple. The hardest code is for the list, and that’s because you’ll need to make sure you’re linking the nodes correctly. Otherwise, the algorithm for a linked list is, largely, ‘if null, make a node; if not, call this function again with the address of the next node’. Sooner or later, one of the function calls will hit the null node, and then it’ll just make a node there.

So there you have it. I hope this was helpful.