Sep 15, 2006 by Sinclair Schuller
Recursion, as a construct, is quite beautiful. It offers an elegant means of acheiving an algorithmic goal and is used in everything from mathematics to text processing and data structure manipulation. The problem is, using it in practice through today’s popular languages (such as my favorite, C#) can prove to be a disaster. At a minimum, standard recursion proves to be inefficient. Worst case scenario, it’ll consume all of your available memory. So how can you reap the benefits of recursive elegance but avoid the side-effects? Convert your recursive methods to use an emulated stack and iterative recursion. This is something you’ll generally learn in early first level CS courses, but nonethless, it seems to not exist in many people’s engineering vocabularies.Before I get into how to do that, let’s look at why these side-effects happen. Below is a snippet of classic ‘Factorial’ code written in C#:
public static long Factorial(long number)
{
//Breaks the recursion by checking to see if we’ve reached some
//terminal condition. In this case, you want to prevent ‘number’
//from ever being 0. If it was zero, this method would always
//return 0.
if(number == 1)
{
return 1;
}
//Here we make the actual recursive call.
return number * Factorial(number – 1);
}
While this “Get’s it done” it will experience performance and memory footprint side-effects (to the point of overflowing the call stack.) Each time a recursive method calls itself, a return pointer is stored on the call stack (I’m not counting on any sort of tail-end optimizations) and a memory register allows the program to recall the parameters and variables that were being used during each instance of the call. If enough recursive calls are made, all of these variables (and return pointers) end up consuming your memory and exploding your call stack. This creates a limitation on the parameter range your recursive method can work with. For example, although you could make a call like ‘Factorial(10000)’, putting aside the limitation of long, odds are it’ll blow the stack. Second, the function call and frame pause associated with the recursive call will prove to be a performance bottleneck that become more pronounced as the call stack gets larger. These issues arise with even the simplest recursive methods. More complex ones (such as tree navigation) may break quicker. Now on to iterative recursion.
Call-stack emulation is not a new concept. It basically emulates the recursive process using a looping construct and a state stack, but avoids the problems associated with making function calls and extends the life of your available memory. As a result, you end up with psuedo-recursive methods that run faster and that can execute on wider parameter ranges. The problem is, many people have difficulty in converting a standard recursive method to an iterative one. Before we get into the conversion process, below is the same Factorial method, rewritten. Afterwards, we’ll pick it apart:
public static long Factorial(long number)
{
//This stack acts as a memory register for what would normally
//be the parameters of a recursive method. The first thing we
//push is the first parameter value.
Stack<long> numStack = new Stack<long>();
numStack.Push(number); long factorial = 1;
while(numStack.Count > 0)
{
long currNum = numStack.Pop();
factorial = factorial * currNum; if(currNum != 1)
{
numStack.Push(currNum – 1);
}
} return factorial;
}
Looks a tad different, no? So how did we get from version1 (crappy) to version 2 (not so crappy)? There are a few rules of thumb that make conversion easier (tweak them to fit your need, of course). First, parameters. Normally, when you make a recursive call, your parameters from previous calls are “remembered” through the use of stack frames. In iteration, we have to build something to remember previous parameters ourselves. As a result, we use our own Stack object. So:
Rule 1: Have either 1 stack for each parameter type in your method or a stack that can store a more complex object that contains all of your parameters. For example, the new Factorial method has a Stack<long> because we have one long parameter. If my method took a long and a string, then I would have either had two stacks, one for the long parameter and one for the string parameter or I would have had one object that stored both and pushed that on the stack.
We use this Stack object to push the parameters of each iteration. Second, you need a place to store the result. This is an instance of the data type being returned.
Rule 2: Have a way of storing your result, which is what is being calculated/arrived at recursively.
Granted, this is applicable only if you are in fact returning something. In the Factorial scenario, we have long factorial = 1 as our storage “device”. Our next rule is:
Rule 3: Have a loop of some sort that loops until the stack is empty.
Looping until the Stack is empty is equivalent to saying “Stop unwinding stack frames when there are none left.” Although the quoted statement is a triviality, we need to explicitly define this since we are emulating the trivial notion. The body of the loop is basically the same as the scope defined by your method body in a standard recursive function, so treat it that way! Do your “work” in there. First, pop a variables(s) off of your stack(s). These are like using the parameters of the current stack frame in traditional recursion. Use these parameters and your algorithm to manipulate your result variable. Last rule:
Rule 4: Map your control condition and recursive calls.
Your control condition (in our case if(number == 1)) in the original function generally stays intact. Your recursive call(s) now maps to stack pushes, however. For each recursive call, you will generally have one stack push. Rather than using the control condition to determine when to stop recursively calling, you now use it to determine when to stop pushing on the stack. In our iterative version, we simply push the current popped variable minus 1 (ala the original recursive method) ontot the stack. The next iteration, it will be popped off and used as the current variable.
You now have a far better version of your recursive method. One thing to note: this example is trivial in the sense that your stack never grows past one because of the nature factorial, which can be calculated using a standard loop. The stack is simply used to to illustrate the state-based requirement of emulating parameter passing in a recursive call. If you implement iterative recursion for something like navigating a tree, you’ll see your stack grow past a count of one.
Thats it! Hopefully, more people take the iterative approach and help in making software better. If you need any help understanding, feel free to comment;)
Update: After a couple of comments, I realize I shouldn’t have used Factorial, which you can calculate quite simply with an iterative loop anyway. Keep in mind that the goal of this post was to provide a lowest common denominator example. The above process works for basic recursive needs.
read more
