python - 替换使用堆栈的任意递归？

很明显递归是使用堆栈实现的。但是，如何使用堆栈实现一般递归呢？例如，如果我们有一个递归的自定义函数，我们可以只用堆栈和迭代来重写代码吗？
下面是一个例子（我在另一篇文章中给出了错误的例子）：

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)

或者更简单的：

def recursiveInorder(node):
    if node==None:
        return
    recursiveInorder(node.left)
    print(node.val)
    recursiveInorder(node.right)

如何使用堆栈实现这种递归？注意，我并不是要求对以上两个例子进行迭代求解。我相信一定有。但我认为这些迭代解决方案并没有试图使用堆栈来重现递归机制。我想看到的是，如果可能的话，这些递归可以完全被自定义编码的堆栈机制所代替（基本上是使隐式递归机制嵌入到编译器中或任何显式的机制）。
我认为需要找到一种方法来跟踪和恢复程序状态，局部变量等？
谢谢。
节点类定义为：

class node:
   def __init__(self,x):
      self.val=x
      self.left=None
      self.right=None

最佳答案

基本上，在模拟递归调用时，需要推送堆栈局部变量和返回后应恢复执行的点。
我将在这里用编号的注释指出相关的执行点。把它们想象成goto标签。

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

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

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)
        elif goto == 1:
            print(node.val)
            #push state and recurse right
            stack.append((node, goto+1))
            (node, goto) = (node.right, 0)
        else:
            #return
            (node, goto) = stack.pop()

最后，(None, None)将被弹出，但由于while循环结束，这些值永远不会被使用。
以上代码是直接转换的结果。接下来，我们可以应用各种优化来简化它。
最后一个分支没有做有用的工作。如果我们也移除了将带我们去那里的推力，我们可以移除它。

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)

现在堆栈中的else值始终为1。我们只需要在堆栈上推goto并在从堆栈弹出时指定node。

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)

如果我们把内部的循环变成一个循环。。。

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)

……我们看到，在goto = 1语句的每个分支之后，我们希望转到另一个分支，直到最后弹出sentinel值。如果在中间添加一个空栈的检查，则可以消除if和while语句。如果我们把支票放在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

现在代码看起来简洁明了。

关于python - 替换使用堆栈的任意递归？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27787461/