Is it possible to convert this recursive solution (to print brackets) to an iterative version?

Question

I need to print the different variations of printing valid tags "<" and ">" given the number of times the tags should appear and below is the solution in python using recursion.

def genBrackets(c):
    def genBracketsHelper(r,l,currentString):
        if l > r or r == -1 or l == -1:
            return
        if r == l and r == 0:
            print currentString
        genBracketsHelper(r,l-1, currentString + '<')
        genBracketsHelper(r-1,l, currentString + '>')
        return
    genBracketsHelper(c, c, '')

#display options with 4 tags     
genBrackets(4)

I am having a hard time really understanding this and want to try to convert this into a iterative version but I haven't had any success.

As per this thread: Can every recursion be converted into iteration? - it looks like it should be possible and the only exception appears to be the Ackermann function.

If anyone has any tips on how to see the "stack" maintained in Eclipse - that would also be appreciated.

PS. This is not a homework question - I am just trying to understand recursion-to-iteration conversion better.

Edit by Matthieu M. an example of output for better visualization:

>>> genBrackets(3)
<<<>>>
<<><>>
<<>><>
<><<>>
<><><>

Answer 1

I tried to keep basically the same structure as your code, but using an explicit stack rather than function calls to genBracketsHelper:

def genBrackets(c=1):
    # genBracketsStack is a list of tuples, each of which
    # represents the arguments to a call of genBracketsHelper
    # Push the initial call onto the stack:
    genBracketsStack = [(c, c, '')]
    # This loop replaces genBracketsHelper itself
    while genBracketsStack != []:
        # Get the current arguments (now from the stack)
        (r, l, currentString) = genBracketsStack.pop()
        # Basically same logic as before
        if l > r or r == -1 or l == -1:
            continue # Acts like return
        if r == l and r == 0:
            print currentString
        # Recursive calls are now pushes onto the stack
        genBracketsStack.append((r-1,l, currentString + '>'))
        genBracketsStack.append((r,l-1, currentString + '<'))
        # This is kept explicit since you had an explicit return before
        continue

genBrackets(4)

Note that the conversion I am using relies on all of the recursive calls being at the end of the function; the code would be more complicated if that wasn't the case.

Answer 2

You asked about doing this without a stack.

This algorithm walks the entire solution space, so it does a bit more work than the original versions, but it's basically the same concept:

• each string has a tree of possible suffixes in your grammar
• since there are only two tokens, it's a binary tree
• the depth of the tree will always be c*2, so...
• there must be 2**(c*2) paths through the tree

Since each path is a sequence of binary decisions, the paths correspond to the binary representations of the integers between 0 and 2**(c*2)-1.

So: just loop through those numbers and see if the binary representation corresponds to a balanced string. :)

def isValid(string):
    """
    True if and only if the string is balanced.
    """
    count = { '<': 0, '>':0 }
    for char in string:
        count[char] += 1
        if count['>'] > count['<']:
            return False # premature closure

    if count['<'] != count['>']:
        return False # unbalanced
    else:
        return True


def genBrackets(c):
    """
    Generate every possible combination and test each one.
    """
    for i in range(0, 2**(c*2)):
        candidate = bin(i)[2:].zfill(8).replace('0','<').replace('1','>')
        if isValid(candidate):
            print candidate

Answer 3

In general, a recursion creates a Tree of calls, the root being the original call, and the leaves being the calls that do not recurse.

A degenerate case is when a each call only perform one other call, in this case the tree degenerates into a simple list. The transformation into an iteration is then simply achieved by using a stack, as demonstrated by @Jeremiah.

In the more general case, as here, when each call perform more (strictly) than one call. You obtain a real tree, and there are, therefore, several ways to traverse it.

If you use a queue, instead of a stack, you are performing a breadth-first traversal. @Jeremiah presented a traversal for which I know no name. The typical "recursion" order is normally a depth-first traversal.

The main advantage of the typical recursion is that the length of the stack does not grow as much, so you should aim for depth-first in general... if the complexity does not overwhelm you :)

I suggest beginning by writing a depth first traversal of a tree, once this is done adapting it to your algorithm should be fairly simple.

EDIT: Since I had some time, I wrote the Python Tree Traversal, it's the canonical example:

class Node:
  def __init__(self, el, children):
    self.element = el
    self.children = children

  def __repr__(self):
    return 'Node(' + str(self.element) + ', ' + str(self.children) + ')'

def depthFirstRec(node):
  print node.element

  for c in node.children: depthFirstRec(c)

def depthFirstIter(node):
  stack = [([node,], 0), ]

  while stack != []:
    children, index = stack.pop()

    if index >= len(children): continue
    node = children[index]

    print node.element

    stack.append((children, index+1))
    stack.append((node.children, 0))

Note that the stack management is slightly complicated by the need to remember the index of the child we were currently visiting.

And the adaptation of the algorithm following the depth-first order:

def generateBrackets(c):
  # stack is a list of pairs children/index
  stack = [([(c,c,''),], 0), ]

  while stack != []:
    children, index = stack.pop()

    if index >= len(children): continue  # no more child to visit at this level
    stack.append((children, index+1))    # register next child at this level

    l, r, current = children[index]

    if r == 0 and l == 0: print current

    # create the list of children of this node
    # (bypass if we are already unbalanced)
    if l > r: continue

    newChildren = []
    if l != 0: newChildren.append((l-1, r, current + '<'))
    if r != 0: newChildren.append((l, r-1, current + '>'))
    stack.append((newChildren, 0))

I just realized that storing the index is a bit "too" complicated, since I never visit back. The simple solution thus consists in removing the list elements I don't need any longer, treating the list as a queue (in fact, a stack could be sufficient)!

This applies with minimum transformation.

def generateBrackets2(c):
  # stack is a list of queues of children
  stack = [[(c,c,''),], ]

  while stack != []:
    children = stack.pop()

    if children == []: continue  # no more child to visit at this level
    stack.append(children[1:])   # register next child at this level

    l, r, current = children[0]

    if r == 0 and l == 0: print current

    # create the list of children of this node
    # (bypass if we are already unbalanced)
    if l > r: continue

    newChildren = []
    if l != 0: newChildren.append((l-1, r, current + '<'))
    if r != 0: newChildren.append((l, r-1, current + '>'))
    stack.append(newChildren)