通过使其成为包装器来优化斐波那契数列递归函数

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

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

假设我们调用 fib(5)。这使得 1 次调用 fib(4) 、2 次调用 fib(3) 、3 次调用 fib(2) 、5 次调用 fib(1) 和 3 次调用 fib(0) 。

在他的书中

Eric Roberts 的 Java 抽象编程

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

作者解决效率问题如下：

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

所以我的问题是，通过将 fib 序列作为更通用的additiveSequence 方法的包装器，我们真的能提高效率吗？鉴于additiveSequence 的实现确实遵循相同的重复关系，那么在效率方面，additiveSequence 的实现是否不会与fib 具有相同的精确“问题”？

Here's an example implementation of an additive sequence calculation, where 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);
}

This method returns the n-th value in the series. Work through some examples and you should be able to convince yourself that each t_i will be calculated only once. Compare that with your naively implemented fib method and you can see why this approach is much faster.

The Fibonacci series is this kind of additive sequence, with the starting conditions t₀ = 0 and t₁ = 1. There's nothing particularly special about it, other than the fact that the obvious way to code it is a poor one. The author's point, presumably, is that implementation makes a huge difference in processing time. It does not appear to be clearly explained, however.