Thinking about Recursion in Stacks

Recursion is one of the most common topics in interviews. Recursive solutions usually consist of less code than an interative solution (but not always). One epiphany I had recently while reviewing common recursive problems is that recursion can be thought of in terms of stacks.

Lets say that you were asked to perform a postorder traversal on a binary tree. How would you write the code for this? The most common answer will involve recursion: Start traversing the tree from the top, first print the value of the current node, then traverse the left most node, then the right most node; if this node is a leaf, then exit the function.

def postorder(root):
    print root.value

if root.left is not None:
    postorder(root.left)

if root.right is not None:
    postorder(root.right)
    return

Now if we need to solve the same question, but without using recursion, how would you do it? (this question was actually asking how well can you visualize recursion). In a nutshell, when the program starts executing, a certain contiguous section of memory is set aside for the program called the stack. Source To better visualize what recursion is, we need to take a look at the program stack for the above method.

Everytime a new function is called, it gets added onto this stack, once this method hits a return statement, it gets popped off the stack, and we start executing the last method on the stack. A recursive function may be called many times (depending on the height of the tree and etc), this is why you see stack overflow errors since the recursive call doesn’t terminate and use up all the stack memory!

If you take a look at the program call stack, the recursive execution is basically using the execution stack to implicitly keep track of the traversal order. We can now write a method to iteratively keep track of the traversal order with an explicit stack.

def postorder(root): # using a list as a stack
stack = []

if root is not None:
stack.append(root)

    while len(stack) != 0:
        node = stack.pop()
        print node.value

        if node.right != None:
            stack.append(node.right)

        if node.left != None:
            stack.append(node.left)

    return

We create a stack using a python list, and add our root node as the first Node. Then we push onto the stack starting with the right node first. Since our stack is LIFO, we have to make sure our left node is the first on that gets popped off.

class Node:
    def **init**(self, value, left=None, right=None):
        self.value = value
        self.right = right
        self.left = left

root = Node(50)
root.right = Node(51)
root.left = Node(18, Node(9), Node(24))

Here is the quick working code visualization for this problem, start at around step 32 to avoid the tree declaration.