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

Strive to make your recursive call Tail Recursion (recursion where the last statement is the recursive call). Once you have that, converting it to iteration is generally pretty easy.

Answer 2

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.

Answer 3

One pattern to look for is a recursion call at the end of the function (so called tail-recursion). This can easily be replaced with a while. For example, the function foo:

void foo(Node* node)
{
    if(node == NULL)
       return;
    // Do something with node...
    foo(node->left);
    foo(node->right);
}

ends with a call to foo. This can be replaced with:

void foo(Node* node)
{
    while(node != NULL)
    {
        // Do something with node...
        foo(node->left);
        node = node->right;
     }
}

which eliminates the second recursive call.

Answer 4

Well, in general, recursion can be mimicked as iteration by simply using a storage variable. Note that recursion and iteraction are generally equivalent; one can almost always be converted to the other. A tail-recursive function is very easily converted to an iterative one. Just make the accumulator variable a local one, and iterate instead of recurse. Here's an example in C++ (C were it not for the use of a default argument):

// tail-recursive
int factorial (int n, int acc = 1)
{
  if (n == 1)
    return acc;
  else
    return factorial(n - 1, acc * n);
}

// iterative
int factorial (int n)
{
  int acc = 1;
  for (; n > 1; --n)
    acc *= n;
}

Knowing me, I probably made a mistake in the code, but the idea is there.

Answer 5

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 6

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.

}

Edit: The article Stacks and Recursion Elimination goes into more details on this subject.

Answer 7

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.