尾递归斐波那契数列

Question

我如何实现一个没有循环，时间复杂度为O(n)的递归斐波那契函数？

- Mat.S

---

你知道如何获取第三个斐波那契数吗？第四个？第五个？ - Ignacio Vazquez-Abrams

"必须调用一个递归的辅助函数" - 为什么？迭代方法更容易。我想他们想要将迭代版本的循环转化成递归形式。 - user2357112

@Mat.S: "不允许线性" 是什么意思？ - user2357112

@user2357112 抱歉，这只是规格说明。我不能使用任何循环，但它仍然必须是线性的。 - Mat.S

返回两个斐波那契数。 - user2357112

Answer 1

通常我不会支持像这样发布作业问题的答案，但是迄今为止发布的所有内容似乎都过于复杂化了。正如上面的评论所说，您只需像迭代方式一样使用递归来解决问题即可。

以下是迭代解决方案：

def fib(n):
  a, b = 0, 1
  while n > 0:
    a, b = b, a+b
    n -= 1
  return a

这里是一个等效的递归解决方案：

def fib(n):
  def fib_help(a, b, n):
    return fib_help(b, a+b, n-1) if n > 0 else a
  return fib_help(0, 1, n)

注意，在这两种情况下，我们实际上计算到 F_n+1，但将 F_n 作为结果返回。这与您收到的“提示”非常相符。

我希望你会花时间比较这两个解决方案并确信它们是等效的。理解如何将迭代解决方案转换为等效的递归解决方案（反之亦然）是一项很好的技能。

- DaoWen

---

尾递归形式，嗯？这是另一种很好的方法。在Scheme或其他函数式语言中非常有用，仅从视角上了解它也很好。在Python中并不总是最实用的转换方式，但提示意图的解决方案也不是。 - user2357112

如果将a和b作为默认参数传递给def fib(n, a=0, b=1):，则不需要使用fib_help函数。翻译后的代码是：return fib(n-1, b, a+b) if n > 0 else a。 - gens

Answer 2

如果有人正在寻找JavaScript解决方案：

function _fib(n, left, right) {
  switch (n) {
    case 0: return 0
    case 1: return right
    default: return _fib(n - 1, right, left + right)
  }
}

function fib(n) {
  return _fib(n, 0, 1)
}

在尾调用优化的情况下，以O(n)时间和O(1)空间运行。

- bcherny

---

case 0: return left - Olivier Boissé

Answer 3

查找第n个斐波那契数列数字的Scala代码。 了解尾递归的更多信息请参见http://nerds.logdown.com/posts/1406258-n-th-fibonacci-number。

object Main {
     def main(args: Array[String]) {
        println(fib(9));
        println(fib(8));
        println(fib(7));
        println(fib(6));
        println(fib(5));
        println(fib(4));
        println(fib(3));
        println(fib(2));
        println(fib(1));
        println(fib(0));
      }
      def fib(n: Int): Int = {
        def fib(n: Int, p :Int, c: Int): Int ={
          if (n == 0) return -1; // undefined
          if (n == 1) return p;
          fib(n-1, c, p + c)
        }
        fib(n, 0, 1);
      }
    }

- Deepak Kumar

Answer 4

为了以线性时间解决这个问题，您必须使用一种名为记忆化的动态编程技术。

使用记忆化的Fibonacci伪代码算法如下：

memoryMap[n]

func fib(int n)
    if (n is in memoryMap) then
        return memoryMap[n]
    if (n <= 1) then
        memoryMap[n] = n
    else
        memoryMap[n] = fib(n-1) + fib(n-2)

    return memoryMap[n]

为了解释清楚，您在每次调用 fib(x) 后都需要将结果存储在内存映射中。对于每个后续调用，查找 fib(x) 中的结果都是免费的：也就是说，在内存中查找结果只需要 O(1) 的时间成本。

- 831

---

这是一种方法，也是我首先想到的方法，但并不是预期的解决方案。这是一个好事还是坏事，这是一个观点问题，但如果OP使用这个方法，我建议OP也找出并提交预期的解决方案。 - user2357112

再次阅读后，很明显正确的解决方案是尾递归。但另一方面，这仍然没有太多意义，因为Python甚至不支持尾递归消除。 - 831

即使没有尾递归，这也是有意义的，因为它只使用了 n 个递归调用，应该适合 fib 的堆栈。将其与朴素递归 fib(n) = fib(n-1) + fib(n-2) if n >1 else n 进行比较。 - kap

我认为这种记忆化是一件很自然的事情，为了避免多次计算同一个结果，你可以把这些计算结果保存在某个地方，在未来需要时可以查找。对我来说，称其为“动态规划”似乎给一些非常简单的东西增加了很多复杂性。不使用变异或赋值的版本会更有趣。 - Zelphir Kaltstahl