replacing arbitrary recursion using a stack?

Question

It seems obvious that a recursion is realized using stacks. But how indeed a general recursion realized using a stack? For example, if we have a custom function that is recursive, can we rewrite the code using just a stack and iteration?

Here is one example (I was giving the wrong example in another post):

def recursiveCall(node):
    if node==None:
        return (0,True)
    (left,lstatus) = recursiveCall(node.left)
    (right,rstatus) = recursiveCall(node.right)
    if lstatus==True and rstatus==True:
        if abs(left-right)<=1:
            return (max(left,right)+1,True)
        else:
            return (0,False)
    else:
        return (0,False)

or an easier one :

def recursiveInorder(node):
    if node==None:
        return 
    recursiveInorder(node.left)
    print(node.val)
    recursiveInorder(node.right)

how do you realize this recursion using stacks? Note, I am not asking for an iteration solution to the above two examples. I believe there must be. But I suppose those iteration solutions are not trying to reproduce the recursion mechanism using a stack. What I wanted is to see, if ever possible, those recursions can be completely replaced by custom coded stack-mechanism (basically making the implicit recursion mechanism embedded in the compiler or whatsoever explicit) .

I think one needs to find a way to track and restore program status, local variables etc? thx.

node class is defined as:

class node:
   def __init__(self,x):
      self.val=x
      self.left=None
      self.right=None

This may be interesting: [Can every recursion be converted into iteration?](http://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration) — Christian Tapia, Jan 05 '15 at 20:37
Christian Thx.. But i can not read much of the language used in the post. and probably i do need to see a real example. — bozeng, Jan 05 '15 at 20:38
A call to the recursive function is essentially a push onto a stack. A return from the recursive call is a pop from the stack. Program continues running while stack is not empty. — mrk, Jan 05 '15 at 21:05
But I think you need to push something else into the stack as well. Also . How about two branch? How do I know where to restore? In the inorder example, you restore in the middle — bozeng, Jan 05 '15 at 21:11
If you have stack overflow on Python because of too deep recursion, and your program is relatively simple one, a friendly advice: try rewriting it in C/C++ or Java/Scala. It will most probably take you less time than trying to circumvent that limitation in Python. — Ashalynd, Jan 05 '15 at 21:49
@Ashalynd Thx.. But i just wanted to know how hard is it to write your own stack? or it is so hard and nasty that no one in the industry is doing it.. — bozeng, Jan 05 '15 at 21:57

Janne Karila · Answer 1 · 2015-01-07T08:20:46.887

Basically, when simulating a recursive call, you need to push on the stack local variables and the point where execution should resume after returning.

I'll indicate the relevant points of execution by numbered comments here. Think of them as goto labels.

def recursiveInorder(node):
    #0
    if node==None:
        return 
    recursiveInorder(node.left)
    #1
    print(node.val)
    recursiveInorder(node.right)
    #2
    return

Now, we can use an if-elif statement to simulate goto statements:

def in_order(node):
    stack = [(None, None)] #sentinel
    goto = 0
    while stack:
        if goto == 0:
            if node is None:
                #return
                (node, goto) = stack.pop()
            else:
                #push state and recurse left
                stack.append((node, goto+1))
                (node, goto) = (node.left, 0)
        elif goto == 1:
            print(node.val)
            #push state and recurse right
            stack.append((node, goto+1))
            (node, goto) = (node.right, 0)
        else: 
            #return
            (node, goto) = stack.pop()

In the end, (None, None) will be popped but the values are never used because the while loop ends.

The above code is the result of a straightforward conversion. Next, we can apply various optimizations to simplify it.

The last else branch is not doing useful work. We can remove it if we also remove the push that would take us there.

def in_order(node):
    stack = [(None, None)] #sentinel
    goto = 0
    while stack:
        if goto == 0:
            if node is None:
                #return
                (node, goto) = stack.pop()
            else:
                #push state and recurse left
                stack.append((node, goto+1))
                (node, goto) = (node.left, 0)
        else:
            print(node.val)
            #recurse right
            (node, goto) = (node.right, 0)

Now the goto value that is pushed the stack is always 1. We only need to push node on the stack and assign goto = 1 when popping from stack.

def in_order(node):
    stack = [None] #sentinel
    goto = 0
    while stack:
        if goto == 0:
            if node is None:
                #return
                (node, goto) = (stack.pop(), 1)
            else:
                #push state and recurse left
                stack.append(node)
                (node, goto) = (node.left, 0)
        else:
            print(node.val)
            #recurse right
            (node, goto) = (node.right, 0)

If we change the inner if into a while loop...

def in_order(node):
    stack = [None] #sentinel
    goto = 0
    while stack:
        if goto == 0:
            while node is not None:
                #push state and recurse left
                stack.append(node)
                node = node.left
            #return
            (node, goto) = (stack.pop(), 1)
        else:
            print(node.val)
            #recurse right
            (node, goto) = (node.right, 0)

...we see that after each branch of the if statement, we want to go to the other branch, until in the end we pop the sentinel value. We can eliminate goto and the if statement, if we add a check for empty stack in the middle. If we place the check before the pop, we don't need the sentinel on stack any more.

def in_order(node):
    stack = []
    while True:
        while node is not None:
            stack.append(node)
            node = node.left
        if stack:
            node = stack.pop()
            print(node.val)
            node = node.right
        else:
            return

Now the code looks clean and simple.

replacing arbitrary recursion using a stack?

1 Answers1