快速Fibonacci递归

Question

我在试着调用斐波那契递归的算法。以下内容：

public int fibonacci(int n)  {
  if(n == 0)
    return 0;
  else if(n == 1)
    return 1;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

不是我要找的，因为它太贪婪了。这将呈指数级增长(看看Java recursive Fibonacci sequence就知道了--初始参数越大，发出的无用调用就越多)。

可能有一些类似于“循环参数移位”的东西，调用之前的斐波那契数值会检索到值，而不是再次计算它。

Answer 1

可能是这样的：

int fib(int term, int val = 1, int prev = 0)
{
 if(term == 0) return prev;
 return fib(term - 1, val+prev, val);
}

这个函数是尾递归的。这意味着它可以被优化并非常有效地执行。实际上，它被优化成一个简单的循环。

Answer 2

这类问题是线性递归类型的，通过快速矩阵求幂可以最快地解决它们。下面是简要描述这种方法的blogpost。

Answer 3

你可以通过使用memoization (意思是:存储以前的结果以避免重新计算它们)来做一个非常快速的递归斐波那契算法。例如，以下是Python中的概念证明，其中使用字典来保存先前的结果：

results = { 0:0, 1:1 }

def memofib(n):
    if n not in results:
        results[n] = memofib(n-1) + memofib(n-2)
    return results[n]

对于通常会阻塞“正常”递归版本的输入值，它会快速返回。请记住，int数据类型不足以容纳大的结果，建议使用任意精度的整数。

完全不同的选择-重写这个迭代版本...

def iterfib(n):
    a, b = 0, 1
    for i in xrange(n):
        a, b = b, a + b
    return a

..。作为尾递归函数，在我的代码中称为loop：

def tailfib(n):
    return loop(n, 0, 1)

def loop(i, a, b):
    if i == 0:
        return a
    return loop(i-1, b, a+b)