快速斐波纳契递归

Question

我试图回忆一下Fibonacci递归的算法.下列:

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递归Fibonacci序列 - 初始参数越大,将进行越多无用的调用).

可能有类似"循环参数移位"的东西,其中调用前一个斐波那契值将检索值而不是再次计算它.

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

这类问题是线性递归类型,它们通过快速矩阵求幂得到最快的解决.这是博客文章,简明扼要地描述了这种方法.

Answer 3

您可以通过使用memoization来执行非常快速的递归Fibonacci版本(意思是:存储以前的结果以避免重新计算它们).例如,这是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)