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)
