尾递归斐波那契

Question

我该如何实现一个递归的斐波那契函数，而且不使用循环，运行时间是O(n)？

Answer 1

如果有人在找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)，并且使用了尾调用优化。

Answer 2

这是用Scala编写的代码，用来找出第n个斐波那契数。
如果你想了解更多关于尾递归的知识，可以查看这个链接：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);
      }
    }

Answer 3

通常我不太喜欢回答这种作业问题，但目前为止大家的回答似乎都把事情搞得太复杂了。正如上面的评论所说，你只需要用递归的方法来解决这个问题，就像用迭代的方法一样。

这是一个迭代的解决方案：

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。这和你得到的“提示”很契合。

我希望你能花时间对比这两种解决方案，自己确认它们是等价的。理解如何将一个迭代的解决方案转换为一个等效的递归解决方案（或者反过来）是一个很好的技能。

尾递归斐波那契

4 个回答

撰写回答