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

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 2

Generally the technique to avoid stack overflow is for recursive functions is called trampoline technique which is widely adopted by Java devs.

However, for C# there is a little helper method here that turns your recursive function to iterative without requiring to change logic or make the code in-comprehensible. C# is such a nice language that amazing stuff is possible with it.

It works by wrapping parts of the method by a helper method. For example the following recursive function:

int Sum(int index, int[] array)
{
 //This is the termination condition
 if (int >= array.Length)
 //This is the returning value when termination condition is true
 return 0;

//This is the recursive call
 var sumofrest = Sum(index+1, array);

//This is the work to do with the current item and the
 //result of recursive call
 return array[index]+sumofrest;
}

Turns into:

int Sum(int[] ar)
{
 return RecursionHelper<int>.CreateSingular(i => i >= ar.Length, i => 0)
 .RecursiveCall((i, rv) => i + 1)
 .Do((i, rv) => ar[i] + rv)
 .Execute(0);
}

Answer 3

Another simple and complete example of turning the recursive function into iterative one using the stack.

#include <iostream>
#include <stack>
using namespace std;

int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }

struct Par
{
    int a, b;
    Par() : Par(0, 0) {}
    Par(int _a, int _b) : a(_a), b(_b) {}
};

int GCDIter(int a, int b)
{
    stack<Par> rcstack;

    if (b == 0)
        return a;
    rcstack.push(Par(b, a % b));

    Par p;
    while (!rcstack.empty()) 
    {
        p = rcstack.top();
        rcstack.pop();
        if (p.b == 0)
            continue;
        rcstack.push(Par(p.b, p.a % p.b));
    }

    return p.a;
}

int main()
{
    //cout << GCD(24, 36) << endl;
    cout << GCDIter(81, 36) << endl;

    cin.get();
    return 0;
}

Answer 4

A rough description of how a system takes any recursive function and executes it using a stack:

This intended to show the idea without details. Consider this function that would print out nodes of a graph:

function show(node)
0. if isleaf(node):
1.  print node.name
2. else:
3.  show(node.left)
4.  show(node)
5.  show(node.right)

For example graph: A->B A->C show(A) would print B, A, C

Function calls mean save the local state and the continuation point so you can come back, and then jump the the function you want to call.

For example, suppose show(A) begins to run. The function call on line 3. show(B) means - Add item to the stack meaning "you'll need to continue at line 2 with local variable state node=A" - Goto line 0 with node=B.

To execute code, the system runs through the instructions. When a function call is encountered, the system pushes information it needs to come back to where it was, runs the function code, and when the function completes, pops the information about where it needs to go to continue.

Answer 5

Thinking of things that actually need a stack:

If we consider the pattern of recursion as:

if(task can be done directly) {
    return result of doing task directly
} else {
    split task into two or more parts
    solve for each part (possibly by recursing)
    return result constructed by combining these solutions
}

For example, the classic Tower of Hanoi

if(the number of discs to move is 1) {
    just move it
} else {
    move n-1 discs to the spare peg
    move the remaining disc to the target peg
    move n-1 discs from the spare peg to the target peg, using the current peg as a spare
}

This can be translated into a loop working on an explicit stack, by restating it as:

place seed task on stack
while stack is not empty 
   take a task off the stack
   if(task can be done directly) {
      Do it
   } else {
      Split task into two or more parts
      Place task to consolidate results on stack
      Place each task on stack
   }
}

For Tower of Hanoi this becomes:

stack.push(new Task(size, from, to, spare));
while(! stack.isEmpty()) {
    task = stack.pop();
    if(task.size() = 1) {
        just move it
    } else {
        stack.push(new Task(task.size() -1, task.spare(), task,to(), task,from()));
        stack.push(new Task(1, task.from(), task.to(), task.spare()));
        stack.push(new Task(task.size() -1, task.from(), task.spare(), task.to()));
    }
}

There is considerable flexibility here as to how you define your stack. You can make your stack a list of Command objects that do sophisticated things. Or you can go the opposite direction and make it a list of simpler types (e.g. a "task" might be 4 elements on a stack of int, rather than one element on a stack of Task).

All this means is that the memory for the stack is in the heap rather than in the Java execution stack, but this can be useful in that you have more control over it.

Answer 6

This link provides some explanation and proposes the idea of keeping "location" to be able to get to the exact place between several recursive calls:

However, all these examples describe scenarios in which a recursive call is made a fixed amount of times. Things get trickier when you have something like:

function rec(...) {
  for/while loop {
    var x = rec(...)
    // make a side effect involving return value x
  }
}