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

Solution 1

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.

var stack = [];
stack.push(firstObject);

// while not empty
while (stack.length) {

    // Pop off end of stack.
    obj = stack.pop();

    // Do stuff.
    // Push other objects on the stack as needed.
    ...

}

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.

Solution 2

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.

Solution 3

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);
            list.Add(x.key);//finally visit root
        }
}

The iterative solution:

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

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

            if (@return == false) {

                switch (address) {
                    case A://   
                        stack.Push(x);
                        stack.Push(B);
                        x = x.a;
                        address = A;
                        break;
                    case B:
                        stack.Push(x);
                        stack.Push(C);
                        x = x.b;
                        address = A;
                        break;
                    case C:
                        stack.Push(x);
                        stack.Push(null);
                        x = x.c;
                        address = A;
                        break;
                    case null:
                        list_iterative.Add(x.key);
                        @return = true;
                        break;
                }

            }


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


        }

Solution 4

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.

Solution 5

Well, in general, recursion can be mimicked as iteration by simply using a storage variable. Note that recursion and iteration 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.

View more solutions

Comments

[nathan]

Still looks recursive to me... :)

[csakii]

Well, yeah - but it's half as recursive. Getting rid of the other recursion is going to require using another technique...

[Liran Orevi]

Some JIT's transform tail recursion: ibm.com/developerworks/java/library/j-diag8.html

[new123456]

Plenty of interpreters (ie Scheme being the most well known) will optimize tail recursion well. I know that GCC, with a certain optimization, does tail recursion (even though C is an odd choice for such an optimization).

[Amit]

The above example is an example of recursive to iterative dfs on binary search tree :)

[Wojciech Kulik]

It's really usefull, I had to write iterative version of reccurence which ivokes itself n-times, thanks to your post I did it.

[lexicalscope]

Any ideas on how to work out the maximum stack to allocate for a particular recursion?

[Chethan]

Pushing just the parameters may not be sufficient. you need to push the local variables which are used subsequent to the point of recursive call. Also, the linked article provides a skeleton that is not suitable for implementations having recur. calls from deeper code blocks. I have tried to provide a repeatable method for converstion as an answer below.

[SamuelWarren]

If you replace your stack with a Queue son't that solve the problem of reversing the add order?

[Ponkadoodle]

I agree with your first bit, but I think I'm misunderstanding the second paragraph. Consider cloning an array through just copying the memory copy = new int[size]; for(int i=0; i<size; ++i) copy[i] = source[i]; space and time complexity are both O(N) based on the size of the data, but it's clearly an iterative algorithm.

[pete]

I worked it out on paper and they are two different things. If you reverse the order you added them it makes you traverse forward as usual, but your traversal is still depth-first search. But if you change the whole thing into a queue now you are doing breadth-first rather than depth-first traversal.

[JanX2]

This has helped me a lot, but there dis a problem: stackitem objects are allocated with a garbage value for ra. Everything still works in the most like case, but should ra by coincidence be 1 or 2 you will get incorrect behavior. The solution is to initialize ra to 0.

[Chethan]

@JanX2, stackitem must not be pushed without initializing. But yes, initializing to 0 would catch errors.

[user420667]

It might be worth mentioning that if between the two foos you add some work(), you could push that on your stack as well, but you would want to add an additional parameter like isWork.

[CCS]

This has to be the best example I have ever seen of emulating call stack recursion for situations where multiple recursive calls are being made within the method. Nice job.

[is7s]

Why aren't both return addresses set to the v.pop_back() statement instead?

[experquisite]

I just recently did this in a general way, by replacing my node visitation function (node)->() with (node)->[actions] where action is () -> [actions]. Then on the outside, you just pop an action/continuation off the stack, apply/execute it, push the actions it returned on the stack in reverse in order and repeat. Contingent/complex traversals, you just capture what would have been local stack variables in reference-counted pointers that you close over in your thunks, then subsequent thunks can be contingent on the results of previous sub-traversals etc.

[Adam Arold]

I think you can do tail recursion this way in languages which does not support it.

[mydoghasworms]

You had me at "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" and then I already upvoted. OK, now I am going to read the rest of your answer and see if my premature upvote was justified. (Because I desperately need to know the answer to that).

[T. Webster]

@mydoghasworms - Returning to this question after so long, it even took me a moment to remember what I was thinking. Hope the answer helped.

[mydoghasworms]

@T.Webster Well, it did send me down a specific path of thinking, although I still don't have my answer. For now, I am going to use a recursive function, although I would like to get away from it eventually. Thanks, however; the upvote remains :-)

[T. Webster]

@mydoghasworms thank you. I'm taking some time to pick up Python 3.x now (Microsoft is pushing cross-platform development so), and there may be an easier way to express this.

[mydoghasworms]

@T.Webster As for me, I am doing the nand2tetris course on Coursera to try and broaden my mind and hopefully find the answer I am looking for. (Because I believe it does come up at some point).

[amalloy]

@SamuelWarren If you use a queue instead of a stack you turn the depth-first traversal of the original call tree into a breadth-first traversal. eg if f(1) calls f(2) then f(3), and f(2) calls f(4), you should get 1,2,4,3, but by putting calls onto a queue you'd get 1,2,3,4 (since 1 will enqueue 3 before 2 gets a chance to enqueue 4).

[Zhu Li]

Sometimes we avoid recursion in order to avoid stackoverflow. But maintaining our own stack will also cause stackoverflow. So why do we want to implement recursion with our own stack?

[dontloo]

stack.pop() is not necessary for every iteration, sometimes you might want to push other objects on top of the current one.

[Caleth]

@lexicalscope suppose you have a recursive algorithm in O(N) = O(R*L), where L is the sum of complexity "for layer r", e.g. in this case you have O(N) work at each step doing the partitionings, the recursive depth is O(R), i.e. worst case O(N), average case O(logN) here.

[Gusev Slava]

Why it's better than internal call stack?

[Tim]

I liked the idea of this solution, but it seemed confusing to me. I wrote simplified version for binary tree in python, maybe it will help someone to understand the idea: gist.github.com/azurkin/abb258a0e1a821cbb331f2696b37c3ac

[yuqli]

@ZhuLi If we use new we can create an object on the heap instead of the stack. Unlike stack, heap does not have memory restrictions. See gribblelab.org/CBootCamp/7_Memory_Stack_vs_Heap.html

[aafulei]

@SamuelWarren If you guarantee nothing is not popped before everything is pushed, then you could convert a stack into a queue. However, in most cases (including this one), popping occurs in the process of pushing. In one word, stacks and queues are not convertible in general.

[Bernhard Barker]

If you have more than one recursive call inside your function, and you don't want to jumble up the order of statements or you use the return value, it's generally a bit more complicated than this answer makes it seem (see this answer for how to deal with that).

[Admin]

I added an answer that shows a question with both an iterative and recursive solution

[Will Ness]

@lexicalscope always push the longest part's boundaries to the stack and continue the loop to work on the shortest part of the partition. this way the stack is guaranteed to be logarithmic in the array size.

[Animesh Kumar]

Basically while using a stack, we are traversing the call stack via depth first search, and while using a queue, we are traversing the call stack via breadth first search.

[Animesh Kumar]

@Ponkadoodle Yes. Both of the iterative and recursive solutions take O(N) space and time complexities because recursion is just replacing the call stack with a program stack. But still there are reasons one would go for converting a recursion to iteration, one of them would be coverting your serially executed code into a parallel one using something like CUDA programming.

[Silicomancer]

Resolving the remaining recursion would have been the most interesting part...