python - 一般如何将递归程序转换为迭代程序？

Question

例如，将 BST 的预序遍历和中序遍历从递归转换为迭代是相对直接的。但后订单更难。

下面是原始的递归 BST 遍历函数:

Python 3

def traverse_rec(node):  # traversal of sub-tree at node.
    # pre-order work here:
    # print(node.val, end=' ')
    if node.lft:
        traverse_rec(node.lft)

    # in-order work here:
    print(node.val, end=' ')

    # post-order work here:
    # print(node.val, end=' ')
    if node.rt:
        traverse(node.rt),

我发现了一些递归函数的迭代版本(前序、中序、后序 BST 遍历)，例如 here ，但我正在寻找 what the computer does with it's call stack 之后的迭代实现这样我就可以轻松地转换后序 BST 遍历，并且更一般地将递归代码转换为迭代代码。因此，每次调用函数时都应将“帧”推送到帧堆栈上，该“帧”记录函数返回时继续执行的位置，以及调用函数所需的任何可能被被调用函数更改的变量。函数返回时，帧会从帧堆栈中弹出。

Answer 1

这是我使用frame_stack的递归到迭代翻译:

def traverse_iter(node):
    # Iterative bst traversal. A (node, state) tuple is pushed onto frame_stack where a recursive call would occur.
    # state defines where to pick up the processing on return (on pop).
    # state: 0: Did not just return into this frame.
    #        1: Just returned from left child.
    #        2: Just returned from right child.
    # Only states 1 and 2 get pushed onto the frame_stack.
    # Generally, state would include any variables that are needed on return that get changed on the frame change
    # in addition to the program counter (pc).
    # Here, each node has all the data (val) needed, and state 1 or 2 acts as a pc to determine where to pick up
    # on return.
    frame_stack = []
    state = 0  # Didn't just return from a child(function call).
    while True:
        if node is None:    
            if frame_stack:  # Returning up recursion tree:
                node, state = frame_stack.pop()
            else:            # or completed traversal.
                break

        if state == 0:
            # Execute pre-order work here.
            #print(node.val, end=' ')
            if node.lft:  # Emmulate recursive call into left child.
                frame_stack.append((node, 1))
                node = node.lft
                continue

        if state == 0 or state == 1:
            # Execute in-order work here
            print(node.val, end=' ')

            if node.rt:
                frame_stack.append((node, 2))
                node = node.rt
                state = 0       # State to descend into child.
                continue

        # Returning from a right child or there was none:
        # Execute post-order work here.
        # print(node.val, end=' ')
        node = None     # finished with this node (and all below it).

一旦我“明白了”，我发现开发和理解上述内容相当简单，而且我使用的模式似乎通常可以扩展到任何递归到迭代翻译，因为它基于计算机的行为。我基本上将递归函数调用转换为变量的更新，这些变量被更改为新函数(此处的节点到子节点)，并将它们的原始值与 pc(此处的状态)一起推送到帧堆栈(此处的节点)；根据需要添加最少的支持逻辑。

我想知道是否有人可以提供一个示例，其中帧有效负载需要比(节点，状态)更多的内容才能从我们停止的函数返回中获取，或者简化我的 BST 遍历(同时保持其预、中、和后订单一般)。