如何使用堆栈模拟递归？

Question

我听说任何递归算法都可以使用栈来表达。最近我在一个可用调用栈大小极小的环境中编写程序。

我需要进行一些深度递归，因此我想知道如何重新设计任何递归算法以使用显式栈。

例如，假设我有一个像这样的递归函数：

function f(n, i) {
  if n <= i return n
  if n % i = 0 return f(n / i, i)
  return f(n, i + 1)
}

我能用堆栈来编写它吗？是否有一个简单的过程可以将任何递归函数转换为基于堆栈的函数？

- Peter Olson

---

可能是重复的问题：如何从递归转换为迭代？ - Marcin

Answer 1

如果你理解函数调用如何影响进程栈，你就能知道如何自己实现它。

当你调用一个函数时，一些数据被写入堆栈中，包括参数。函数读取这些参数，对其进行处理，并将结果放在堆栈上。你也可以做同样的事情。特别是你的示例不需要使用堆栈，所以如果我将其转换为使用堆栈的示例，可能会看起来有点傻，因此我将给出斐波那契数列的示例：

fib(n)
    if n < 2 return n
    return fib(n-1) + fib(n-2)

function fib(n, i)
    stack.empty()
    stack.push(<is_arg, n>)
    while (!stack.size() > 2 || stack.top().is_arg)
        <isarg, argn> = stack.pop()
        if (isarg)
            if (argn < 2)
                stack.push(<is_result, argn>)
            else
                stack.push(<is_arg, argn-1>)
                stack.push(<is_arg, argn-2>)
        else
            <isarg_prev, argn_prev> = stack.pop()
            if (isarg_prev)
                stack.push(<is_result, argn>)
                stack.push(<is_arg, argn_prev>)
            else
                stack.push(<is_result, argn+argn_prev>)
     return stack.top().argn

Explanation：每次从栈中取出一个项目时，您需要检查它是否需要扩展。如果是这样，请将适当的参数推送到堆栈上；如果不是，则让其与先前的结果合并。在斐波那契数列的情况下，一旦计算了 fib(n-2)（并且可在堆栈顶部获得），则会检索 n-1（在堆栈顶部之后的一个）。然后，在其下面推送fib(n-2)的结果，然后展开并计算fib(n-1)。如果堆栈的前两个元素都是结果，那么您只需将它们相加并推送到堆栈上即可。

如果您想看看您自己的函数会是什么样子，这里是它：

function f(n, i)
    stack.empty()
    stack.push(n)
    stack.push(i)
    while (!stack.is_empty())
        argi = stack.pop()
        argn = stack.pop()
        if argn <= argi
            result = argn
        else if n % i = 0
            stack.push(n / i)
            stack.push(i)
        else
            stack.push(n)
            stack.push(i + 1)
    return result

- Shahbaz

---

代码： if (isarg_prev) stack.push() stack.push() stack.push()应该改为： if (isarg_prev) stack.push() stack.push() - Srđan Stipić

@user903597 很好的发现。 - Shahbaz

Answer 2

你可以按照以下方式将你的代码转换为使用堆栈:

您可以将您的代码转换成使用堆栈，如下所示：

stack.push(n)
stack.push(i)
while(stack.notEmpty)
    i = stack.pop()
    n = stack.pop()
    if (n <= i) {
        return n
    } else if (n % i = 0) {
        stack.push(n / i) 
        stack.push(i)
    } else {
        stack.push(n) 
        stack.push(i+1)
    }
}

注意：我没有测试过这段代码，因此可能存在错误，但是可以给你提供一个思路。

- sch

---

这大致就是我要发布的内容（以及观察到问题措辞不当；递归总是在调用栈中明确使用堆栈），但我认为值得指出的是，在这种情况下，堆栈永远不会超过两个项目，因此您可以免费获得尾递归观察。 - Tommy

是的，在这里不需要使用堆栈，一个简单的while循环就足够了，但我仍然使用了堆栈，因为OP明确要求使用堆栈。 - sch

Answer 3

你的这个例子是尾递归的，因此只要有一个良好的优化编译器，它就不会消耗任何堆栈深度，因为它等效于一个简单的循环。明确一点：这个例子根本不需要使用栈。

- Marcin

---

这并没有真正帮助我。它指出了我选择了一个糟糕的例子，但它并没有真正展示如何使用堆栈进行递归。无论如何，我正在使用的编程语言Javascript的大多数解释器甚至都没有尾调用优化。 - Peter Olson

同时，该示例实际上并非尾递归，因为其没有直接返回对自身的调用结果。通过添加额外参数，它可以转换为尾递归实现，但目前还没有这样做。 - user149341

@duskwuff 是的，它确实字面上返回对其自身调用的结果。你在说什么？ - Marcin

示例已被编辑。原始返回值为 f(n * 2) + 1 或 f(n + 1) - 3。 - user149341

@PeterOlson 我非常确定这会帮助你认识到有时候你不需要使用堆栈。 - Marcin

@duskwuff 不，在原始版本中没有：http://stackoverflow.com/revisions/9831666/1 - Marcin

Answer 4

你的示例和斐波那契函数都可以在不使用堆栈的情况下进行迭代重写。

这里有一个需要使用堆栈的例子，阿克曼函数：

def ack(m, n):
    assert m >= 0 and n >= 0
    if m == 0: return n + 1
    if n == 0: return ack(m - 1, 1)
    return ack(m - 1, ack(m, n - 1))

消除递归：

def ack_iter(m, n):
    stack = []
    push = stack.append
    pop = stack.pop
    RETURN_VALUE, CALL_FUNCTION, NESTED = -1, -2, -3

    push(m) # push function arguments
    push(n)
    push(CALL_FUNCTION) # push address
    while stack: # not empty
        address = pop()
        if address is CALL_FUNCTION:
            n = pop()  # pop function arguments
            m = pop()
            if m == 0: # return n + 1
                push(n+1) # push returned value
                push(RETURN_VALUE)
            elif n == 0: # return ack(m - 1, 1)
                push(m-1)
                push(1)
                push(CALL_FUNCTION)
            else: # begin: return ack(m - 1, ack(m, n - 1))
                push(m-1) # save local value
                push(NESTED) # save address to return
                push(m)
                push(n-1)
                push(CALL_FUNCTION)
        elif address is NESTED: # end: return ack(m - 1, ack(m, n - 1))
            # old (m - 1) is already on the stack
            push(value) # use returned value from the most recent call
            push(CALL_FUNCTION)
        elif address is RETURN_VALUE:
            value = pop() # pop returned value
        else:
            assert 0, (address, stack)
    return value

这里不需要在堆栈上放置CALL_FUNCTION、RETURN_VALUE标签和value。

示例

print(ack(2, 4)) # -> 11
print(ack_iter(2, 4))
assert all(ack(m, n) == ack_iter(m, n) for m in range(4) for n in range(6))
print(ack_iter(3, 4)) # -> 125

- jfs