algorithm - 带堆栈的斐波那契递归

Question

我已经问过了a question关于这一点，但我仍然感到困惑。我想在没有递归的情况下将递归函数转换为基于堆栈的函数。以斐波那契函数为例:

algorithm Fibonacci(x):
  i = 0
  i += Fibonacci(x-1)
  i += Fibonacci(x-2)
  return i

(是的，我知道我没有提出基本情况，而且斐波那契的递归效率真的很低)

这将如何使用显式堆栈实现？例如，如果我将堆栈作为 while 循环，我必须跳出循环才能计算第一次递归，而且我无法在第一次递归后返回到行并继续进行第二次递归.

Answer 1

在伪 python 中

def fib(x):
  tot = 0
  stack = [x]
  while stack:
     a = stack.pop()
     if a in [0,1]:
        tot += 1
     else:
         stack.push(a - 1)
         stack.push(a - 2)
   return tot

如果您不想要外部计数器，那么您将需要推送元组来跟踪累计总和以及这是 a - 1 还是 a - 2 .

可能值得您花时间显式写出调用堆栈(手动，在纸上)，以便为您的代码运行 say fib(3)(尽管首先修复您的代码，以便它处理边界条件)。一旦你这样做了，应该清楚如何在没有堆栈的情况下做到这一点。

编辑:

下面我们来分析下斐波那契算法的运行

def fib(x):
    if (x == 0) or (x == 1):
       return 1
    else:
        temp1 = fib(x - 1)
        temp2 = fib(x - 2)
        return temp1 + temp2

(是的，我知道这甚至不是低效算法的有效实现，我已经声明了比必要更多的临时对象。)

现在当我们使用堆栈进行函数调用时，我们需要在堆栈上存储两种东西。

1. 在哪里返回结果。
2. 局部变量空间。

在我们的例子中，我们有三个可能返回的地方。

1. 一些外部来电者
2. 分配给 temp1
3. 分配给 temp2

我们还需要三个局部变量 x、temp1 和 temp2 的空间。让我们检查 fib(3)

当我们最初调用 fib 时，我们告诉堆栈我们要返回到我们出发的地方，x = 3，并且 temp1 和 temp2 未初始化。

接下来我们压入我们想要分配给 temp1 的堆栈，x = 2 并且 temp1 和 temp2 是未初始化的。我们再次调用，我们有一堆

(assign temp1, x = 1, -, -)
(assign temp1, x = 2, -, -)
(out         , x = 3, -, -)

我们现在返回 1 并进行第二次调用并得到

(assign temp2, x = 0, -, -)
(assign temp1, x = 2, temp1 = 1, -)
(out         , x = 3, -, -)

现在再次返回 1

(assign temp1, x = 2, temp1 = 1, temp2 = 1)
(out         , x = 3, -, -)

所以这会返回 2，我们得到

(out         , x = 3, temp1 =2, -)

所以我们现在递归到

(assign temp2, x = 1, -, -)
(out         , x = 3, temp1 =2, -)

从中我们可以看到出路。