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

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)

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

根据这个线程:Can every recursion be converted into iteration? - 看起来应该是可能的，唯一的异常(exception)似乎是 Ackermann 函数。

如果有人对如何查看 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)

请注意，我使用的转换依赖于函数末尾的所有递归调用；如果不是这种情况，代码会更复杂。