algorithm - 通过包装器优化斐波那契数列递归函数

Question

斐波那契数列的递归定义在效率方面存在问题。定义如下:

private fib(int n) {
    if(n < 2) return n;
    else return fib(n - 1) + fib(n-2);
}

假设我们调用 fib(5)。这对 fib(4) 进行了 1 次调用，对 fib(3) 进行了两次调用，对 fib(2) 进行了三次调用，对 fib(1) 进行了五次调用，对 fib(0) 进行了三次调用。

在他的书中

Programming Abstractions in Java by Eric Roberts

Roberts 提到我们可以通过认识到斐波那契数列只是 additiveSequence(int n, int t0, int t1) 方法的一个特例来解决这个效率问题。基本上，斐波那契数列只是一个严格以0和1开头的加法数列。有无数个数列符合斐波那契所表达的递归关系。

作者解决效率问题如下:

private int fib(int n) {
    return additiveSequence(n, 0, 1);
}

所以我的问题是，通过使 fib 序列成为更通用的 additiveSequence 方法的包装器，我们真的提高了效率吗？ additiveSequence 的实现在效率方面不会有与 fib 完全相同的“问题”，因为它确实遵循相同的精确递归关系吗？

Answer 1

这是加法序列计算的示例实现，其中 t_i = t_i-1 + t_i-2:

int additiveSequence(int n, int t0, int t1) {
  if(n==0) return t0;
  if(n==1) return t1;
  return additiveSequence(n-1, t1, t0+t1);
}

此方法返回系列中的第 n 个 值。通过一些示例，您应该能够说服自己每个 t_i 只会计算一次。将其与您天真地实现的 fib 方法进行比较，您就会明白为什么这种方法要快得多。

斐波那契数列就是这种加法数列，起始条件为t₀ = 0，t₁ = 1。没有什么特别之处，除了事实上，显而易见的编码方式是一种糟糕的方式。据推测，作者的观点是实现会在处理时间上产生巨大差异。然而，它似乎没有得到清楚的解释。