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

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)

或更简单的:

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

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语句:

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 循环结束。

---

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

最后一个 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 语句的每个分支之后，我们想要转到另一个分支，直到最后我们弹出标记值。如果我们在中间添加空堆栈检查，我们可以消除 goto 和 if 语句。如果我们将检查放在弹出之前，我们就不再需要栈上的哨兵了。

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

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