Way to go from recursion to iteration

Question

I've used recursion quite a lot on my many years of programming to solve simple problems, but I'm fully aware that sometimes you need iteration due to memory/speed problems.

So, sometime in the very far past I went to try and find if there existed any "pattern" or text-book way of transforming a common recursion approach to iteration and found nothing. Or at least nothing that I can remember it would help.

• Are there general rules?
• Is there a "pattern"?

Answer 1

Even using stack will not convert a recursive algorithm into iterative. Normal recursion is function based recursion and if we use stack then it becomes stack based recursion. But its still recursion.

For recursive algorithms, space complexity is O(N) and time complexity is O(N). For iterative algorithms, space complexity is O(1) and time complexity is O(N).

But if we use stack things in terms of complexity remains same. I think only tail recursion can be converted into iteration.

Answer 2

There is a general way of converting recursive traversal to iterator by using a lazy iterator which concatenates multiple iterator suppliers (lambda expression which returns an iterator). See my Converting Recursive Traversal to Iterator.

Answer 3

Really, the most common way to do it is to keep your own stack. Here's a recursive quicksort function in C:

void quicksort(int* array, int left, int right)
{
    if(left >= right)
        return;

    int index = partition(array, left, right);
    quicksort(array, left, index - 1);
    quicksort(array, index + 1, right);
}

Here's how we could make it iterative by keeping our own stack:

void quicksort(int *array, int left, int right)
{
    int stack[1024];
    int i=0;

    stack[i++] = left;
    stack[i++] = right;

    while (i > 0)
    {
        right = stack[--i];
        left = stack[--i];

        if (left >= right)
             continue;

        int index = partition(array, left, right);
        stack[i++] = left;
        stack[i++] = index - 1;
        stack[i++] = index + 1;
        stack[i++] = right;
    }
}

Obviously, this example doesn't check stack boundaries... and really you could size the stack based on the worst case given left and and right values. But you get the idea.

Answer 4

I just upvoted the answer suggesting to use an explicit stack that I think is the right solution and is of general applicability.

I mean that you can use it to transform any recursive function in an iterative function. Just check which values are saved across recursive calls, those are the ones that have to be local to the recursive function, and replace the calls with a cycle where you'll push them on a stack. When the stack is empty the recursive function would have been terminated.

I can't resist to say that the proof that every recursive function is equivalent to an iterative function on a different data type, it's one of my dearest memory of my University times. That was the course (and the professor) that really made me understand what computer programming was about.

Answer 5

Usually, I replace a recursive algorithm by an iterative algorithm by pushing the parameters that would normally be passed to the recursive function onto a stack. In fact, you are replacing the program stack by one of your own.

Stack<Object> stack;
stack.push(first_object);
while( !stack.isEmpty() ) {
   // Do something
   my_object = stack.pop();

  // Push other objects on the stack.

}

Note: if you have more than one recursive call inside and you want to preserve the order of the calls, you have to add them in the reverse order to the stack:

foo(first);
foo(second);

has to be replaced by

stack.push(second);
stack.push(first);

Edit: The article Stacks and Recursion Elimination (or Article Backup link) goes into more details on this subject.

Answer 6

Search google for "Continuation passing style." There is a general procedure for converting to a tail recursive style; there is also a general procedure for turning tail recursive functions into loops.