使用堆栈替换任意递归？

Question

显然，递归是用堆栈实现的。但是一般递归是如何使用堆栈实现的呢？例如，如果我们有一个递归的自定义函数，我们可以只用堆栈和迭代重写代码吗？在

以下是一个例子（我在另一篇文章中给出了一个错误的例子）：

def recursiveCall(node):
    if node==None:
        return (0,True)
    (left,lstatus) = recursiveCall(node.left)
    (right,rstatus) = recursiveCall(node.right)
    if lstatus==True and rstatus==True:
        if abs(left-right)<=1:
            return (max(left,right)+1,True)
        else:
            return (0,False)
    else:
        return (0,False)

或者更简单一点：

^{pr2}$

如何使用堆栈实现这种递归？注意，我并不是在要求以上两个例子的迭代解决方案。我相信一定有。但我想这些迭代解决方案并不是要使用堆栈来重现递归机制。我想要的是，如果可能的话，这些递归可以完全被自定义编码的堆栈机制所取代（基本上使隐式递归机制嵌入到编译器中或任何显式的）。在

我认为我们需要找到一种方法来跟踪和恢复程序状态、局部变量等？ 谢谢。在

---

节点类定义为：

^{3}$

Answer 1

基本上，在模拟递归调用时，需要在堆栈上推送局部变量和返回后应继续执行的点。在

我将在这里用编号的注释指出相关的执行点。把它们看作goto标签。在

def recursiveInorder(node):
    #0
    if node==None:
        return 
    recursiveInorder(node.left)
    #1
    print(node.val)
    recursiveInorder(node.right)
    #2
    return

现在，我们可以使用if-elif语句来模拟goto语句：

^{pr2}$

最后，(None, None)将弹出，但由于while循环结束，因此从未使用这些值。在

---

上面的代码是直接转换的结果。接下来，我们可以应用各种优化来简化它。

最后一个else分支没有做有用的工作。我们可以把它移除，如果我们也移除将把我们带到那里的推力。在

def in_order(node):
    stack = [(None, None)] #sentinel
    goto = 0
    while stack:
        if goto == 0:
            if node is None:
                #return
                (node, goto) = stack.pop()
            else:
                #push state and recurse left
                stack.append((node, goto+1))
                (node, goto) = (node.left, 0)
        else:
            print(node.val)
            #recurse right
            (node, goto) = (node.right, 0)

现在，压入堆栈的goto值总是1。我们只需要在堆栈上推送node，并在从堆栈弹出时分配goto = 1。在

def in_order(node):
    stack = [None] #sentinel
    goto = 0
    while stack:
        if goto == 0:
            if node is None:
                #return
                (node, goto) = (stack.pop(), 1)
            else:
                #push state and recurse left
                stack.append(node)
                (node, goto) = (node.left, 0)
        else:
            print(node.val)
            #recurse right
            (node, goto) = (node.right, 0)

如果我们将内部if更改为while循环。。。在

def in_order(node):
    stack = [None] #sentinel
    goto = 0
    while stack:
        if goto == 0:
            while node is not None:
                #push state and recurse left
                stack.append(node)
                node = node.left
            #return
            (node, goto) = (stack.pop(), 1)
        else:
            print(node.val)
            #recurse right
            (node, goto) = (node.right, 0)

…我们看到，在if语句的每个分支之后，我们要转到另一个分支，直到最后弹出sentinel值。如果在中间添加一个空栈的检查，则可以消除^ {CD1}和^ {CD10}}语句。如果我们把支票放在pop之前，我们就不需要哨兵了。在

def in_order(node):
    stack = []
    while True:
        while node is not None:
            stack.append(node)
            node = node.left
        if stack:
            node = stack.pop()
            print(node.val)
            node = node.right
        else:
            return

现在代码看起来干净简单。在