通过使Fibonacci序列递归函数成为包装器来优化它

Question

在效率方面，fibonacci序列的递归定义存在问题。其定义如下：

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

假设我们调用fib（5）。这对fib（4）进行了1次调用，对fib的2次调用（3）进行了3次调用（2）进行了5次调用（1）并对fib进行了3个调用（0）。

在他的书

Eric Roberts 的Java编程摘要

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

作者解决效率问题如下：

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

所以我的问题是，通过使fib序列成为更通用的additionSequence方法的包装器，我们真的在提高效率吗？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。它没有什么特别的地方，除了明显的编码方式很糟糕之外。据推测，作者的观点是，实现在处理时间上产生了巨大的差异。然而，这一点似乎没有得到明确解释。