时间戳

首页 > 解决方案 > 使用堆栈将递归算法转换为迭代

algorithm - 使用堆栈将递归算法转换为迭代

问题描述

我的教授在课堂上给我们做了这个练习，并要求准确地模仿带有堆栈的递归调用。这是递归算法：

def algo(T, h):
    ret = -1
    s = 0
    d = 0

    if T != None:
        if T.left != None:
            s = algo(T.left, h + 1)
        if T.right != None:
            d = algo(T.right, h + 1)

        if s == 0 and d == 0:
            ret = h
        else:
            ret = s + d

    return ret

这是我解决这个练习的尝试（我使用了两个堆栈，一个用于保存 T，另一个用于保存“s”）

def algo_it(T, h):
    ret = -1
    s = 0
    d = 0

    curr = T
    next = None
    last = None

    stack_T = Stack()
    stack_S = Stack()

    while curr != None or not stack_T.empty():
        if curr != None:
            # First time entering the function
            ret = -1
            s = 0
            d = 0

            if curr.left != None:
                # Left recursive call
                h = h + 1
                next = curr.left

                # Save current T because it will be popped when going up
                # on recursion tree
                stack_T.push(curr)
            elif curr.right != None:
                # Right recursive call
                h = h + 1
                next = curr.right

                stack_T.push(curr)
            else:
                # Force going up on recursion tree
                next = None
        else:
            # Coming up from recursion tree
            curr = stack_T.top()

            if last != curr.right and curr.right != None:
                # We're here from the 1st recursive call (left)
                # We have to go in right recursive call now
                h = h + 1
                next = curr.right

                # We are returning from left, so ret = s = algo(T.left, h + 1)
                s = ret
                stack_S.push(s)

                ret = -1
                d = 0
            else:
                stack_T.pop()

                if curr.right != None:
                    s = stack_S.pop()
                    d = ret
                else:
                    s = ret
                    d = 0

                if s == 0 and d == 0:
                    ret = h
                else:
                    ret = s + d

        last = curr
        curr = next

    return ret

该算法失败，因为stack_S.pop()我在堆栈为空时弹出，所以我得到运行时错误。我接近获得解决方案了吗？

我非常感谢您的所有帮助！

标签： algorithmrecursioniteration

解决方案

当您模仿递归调用时，您只是在推入您知道应该返回的堆栈。但是您并没有推动上下文来知道将响应推送到哪个上下文。

我建议你分多个步骤来解决这个问题。

  1. 将所有函数局部变量（T、h、ret和）转换为递归函数之外的堆栈，使用显式弹出/推送而不是声明它们，并期望它们在函数结束时消失s。d（提示：留在堆栈上，并在您操作或ret时弹出它。）这可能需要为第一个递归调用创建一个辅助函数。stack_sstack_d
  2. 在您的函数中为您第一次调用它的位置以及您可以返回的每个位置添加标签。
  3. 转换为迭代如下。为函数调用添加堆栈。它将包含一个标签，说明在函数中的位置。您无需进行递归调用，而是更改函数堆栈的顶部以说明在此调用中返回的位置，然后推入一个新的堆栈以启动一个新函数，然后进入下一个循环迭代。（退出循环的条件是函数栈为空，你的答案会在ret栈顶。）

这是一个有点漫长但机械的过程。它应该让您了解计算机通常为您做了多少。:-)

推荐阅读