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

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 具有相同的 "problem" 吗，因为它确实遵循相同的精确递归关系？

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);
}

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

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

Optimizing the Fibonacci sequence recursive function by making it a wrapper