是否可以将此递归解决方案（打印括号）转换为迭代版本？

Question

我需要打印打印有效标签“<”的不同变体和“>”给定标签应该出现的次数，下面是 python 中使用递归的解决方案。

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)

我很难真正理解这一点，并想尝试将其转换为迭代版本，但我没有取得任何成功。

根据此线程： 每个递归都可以转换为迭代吗？ -看起来应该是可能的，唯一的例外似乎是阿克曼函数。

如果有人对如何查看 Eclipse 中维护的“堆栈”有任何提示 - 我们也将不胜感激。

附言。这不是一个家庭作业问题 - 我只是想更好地理解递归到迭代的转换。

由 Matthieu M 编辑。 更好可视化的输出示例：

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

Answer 1

我试图保持与您的代码基本相同的结构，但使用显式堆栈而不是对 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)

请注意，我使用的转换依赖于位于末尾的所有递归调用功能；如果不是这样的话，代码会更复杂。

Answer 2

您询问如何在没有堆栈的情况下执行此操作。

该算法遍历整个解决方案空间，因此它比原始版本做了更多的工作，但它基本上是相同的概念：

• 每个字符串在语法中都有一个可能的后缀树
• ，因为只有两个标记，它是一个
• 二叉树树的深度始终为 c*2，因此...
• 必须有 2**(c*2) 条路径穿过树

由于每条路径都是二进制决策序列，因此路径对应于整数的二进制表示0 到 2**(c*2)-1 之间。

所以：只需循环这些数字，看看二进制表示是否对应于平衡字符串。 :)

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

一般来说，递归会创建一个调用树，根是原始调用，叶子是不递归的调用。

一种退化情况是每个调用仅执行一个其他调用，在这种情况下，树退化为一个简单列表。然后，只需使用堆栈即可实现到迭代的转换，如 @Jeremiah 所示。

在更一般的情况下，就像这里一样，当每个调用执行多个（严格）多个调用时。您获得了一棵真正的树，因此有多种方法可以遍历它。

如果您使用队列而不是堆栈，那么您将执行广度优先遍历。 @Jeremiah 提出了一个我不知道名字的遍历。典型的“递归”顺序通常是深度优先遍历。

典型递归的主要优点是堆栈的长度不会增长那么多，因此您通常应该以深度优先为目标......如果复杂性不会压垮您:)

我建议首先编写深度优先遍历一棵树，一旦完成，使其适应您的算法应该相当简单。

编辑：因为我有一些时间，所以我编写了Python树遍历，这是典型的示例：

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))

请注意，由于需要记住我们当前正在访问的子项的索引，因此堆栈管理稍微复杂一些。

算法的适应遵循深度优先顺序：

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))

我刚刚意识到存储索引有点“太”复杂，因为我从来没有回来过。因此，简单的解决方案包括删除我不再需要的列表元素，将列表视为队列（事实上，堆栈就足够了）！

这适用于最小变换。

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)

Answer 4

是的。

def genBrackets(c):
    stack = [(c, c, '')]
    while stack:
        right, left, currentString = stack.pop()
        if left > right or right == -1 or left == -1:
            pass
        elif right == left and right == 0:
            print currentString
        else:
            stack.append((right, left-1, currentString + '<'))
            stack.append((right-1, left, currentString + '>'))

输出顺序不同，但结果应该是一样的。