computer-science non-recursive - Way to go from recursion to iteration

c# with (17)

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"?

Recursion is nothing but the process of calling of one function from the other only this process is done by calling of a function by itself. As we know when one function calls the other function the first function saves its state(its variables) and then passes the control to the called function. The called function can be called by using the same name of variables ex fun1(a) can call fun2(a). When we do recursive call nothing new happens. One function calls itself by passing the same type and similar in name variables(but obviously the values stored in variables are different,only the name remains same.)to itself. But before every call the function saves its state and this process of saving continues. The SAVING IS DONE ON A STACK.

NOW THE STACK COMES INTO PLAY.

So if you write an iterative program and save the state on a stack each time and then pop out the values from stack when needed, you have successfully converted a recursive program into an iterative one!

The proof is simple and analytical.

In recursion the computer maintains a stack and in iterative version you will have to manually maintain the stack.

Think over it, just convert a depth first search(on graphs) recursive program into a dfs iterative program.

All the best!

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
}
}
``````

For Tower of Hanoi this becomes:

``````stack.push(new Task(size, from, to, spare));
while(! stack.isEmpty()) {
just move it
} else {
}
}
``````

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.

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;
}
``````

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.

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;
return acc;
}
``````

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

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.

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.

Just killing time... A recursive function

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

can be converted to

``````void foo(Node* node)
{
if(node == NULL)
return;

// Do something with node...

stack.push(node->right);
stack.push(node->left);

while(!stack.empty()) {
node1 = stack.pop();
if(node1 == NULL)
continue;
// Do something with node1...
stack.push(node1->right);
stack.push(node1->left);
}

}
``````

A question that had been closed as a duplicate of this one had a very specific data structure:

The node had the following structure:

``````typedef struct {
int32_t type;
int32_t valueint;
double  valuedouble;
struct  cNODE *next;
struct  cNODE *prev;
struct  cNODE *child;
} cNODE;
``````

The recursive deletion function looked like:

``````void cNODE_Delete(cNODE *c) {
cNODE*next;
while (c) {
next=c->next;
if (c->child) {
cNODE_Delete(c->child)
}
free(c);
c=next;
}
}
``````

In general, it is not always possible to avoid a stack for recursive functions that invoke itself more than one time (or even once). However, for this particular structure, it is possible. The idea is to flatten all the nodes into a single list. This is accomplished by putting the current node's `child` at the end of the top row's list.

``````void cNODE_Delete (cNODE *c) {
cNODE *tmp, *last = c;
while (c) {
while (last->next) {
last = last->next;   /* find last */
}
if ((tmp = c->child)) {
c->child = NULL;     /* append child to last */
last->next = tmp;
tmp->prev = last;
}
tmp = c->next;           /* remove current */
free(c);
c = tmp;
}
}
``````

This technique can be applied to any data linked structure that can be reduce to a DAG with a deterministic topological ordering. The current nodes children are rearranged so that the last child adopts all of the other children. Then the current node can be deleted and traversal can then iterate to the remaining child.

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.

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.

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;
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.

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.

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.

It seems nobody has addressed where the recursive function calls itself more than once in the body, and handles returning to a specific point in the recursion (i.e. not primitive-recursive). It is said that every recursion can be turned into iteration, so it appears that this should be possible.

I just came up with a C# example of how to do this. Suppose you have the following recursive function, which acts like a postorder traversal, and that AbcTreeNode is a 3-ary tree with pointers a, b, c.

``````public static void AbcRecursiveTraversal(this AbcTreeNode x, List<int> list) {
if (x != null) {
AbcRecursiveTraversal(x.a, list);
AbcRecursiveTraversal(x.b, list);
AbcRecursiveTraversal(x.c, list);
}
}
``````

The iterative solution:

``````        int? address = null;
AbcTreeNode x = null;
x = root;
stack.Push(x);
stack.Push(null)

while (stack.Count > 0) {
bool @return = x == null;

if (@return == false) {

case A://
stack.Push(x);
stack.Push(B);
x = x.a;
break;
case B:
stack.Push(x);
stack.Push(C);
x = x.b;
break;
case C:
stack.Push(x);
stack.Push(null);
x = x.c;
break;
case null:
@return = true;
break;
}

}

if (@return == true) {
x = (AbcTreeNode)stack.Pop();
}

}
``````

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.

Depends. If you know you're going to need both the key and the value of every entry, then go through the `entrySet`. If you just need the values, then there's the `values()` method. And if you just need the keys, then use `keyset()`.

A bad practice would be to iterate through all of the keys, and then within the loop, always do `map.get(key)` to get the value. If you're doing that, then the first option I wrote is for you. 