1.1 斐波那契数列

斐波那契数列是一组数字，除了第一个和第二个数字外，其他数字都是前两个数字之和：

其中第一个斐波那契数的值是0，第四个斐波那契数的值是2。因此，要得到后续数列中任一斐波那契数n的值，可以使用下面的公式：

1.1.1 第一次递归尝试

前面计算斐波那契数列的公式（见图1.1）是一种伪代码形式，我们可以简单地将其转换为递归Java方法。所谓递归方法是一种重复调用自身的方法。我们使用这种机械式的转换方法来完成首次尝试，返回斐波那契数列中的给定值。

下面尝试使用参数来调用这个方法。

当尝试运行Fib1.java时，会得到如下异常：

原因在于fib1()会一直运行下去而不返回最终结果。每次调用fib1()都会导致另外两次fib1()的调用，如此反复永无止境。我们称这种情况为无限递归（见图1.2），它类似于无限循环。

1.1.2 基线条件的运用

请注意，在运行fib1()之前，Java环境不会提示它有任何问题。避免无限递归是程序员的职责，而不是由编译器来负责。出现无限递归的原因是我们从未指定基线条件。在递归函数中，基线条件是指停止递归的条件。

就斐波那契数列而言，本身就存在两个基线条件，也就是数列最开始的两个特殊数字0和1。0和1都不是由数列中前两个数字求和得来的，而是数列最开始的两个特殊值。我们尝试将它们设为基线条件。

fib2()可以成功被调用并返回正确的结果。尝试用一些小的数值来调用它。

不要尝试调用fib2(40)。运行它可能需要很长时间！这是为什么呢？每次调用fib2()都会导致另外两次递归的fib2()调用，也就是fib2(n-1)和fib2(n-2)（见图1.3）。换句话说，这种树状调用结构将呈指数级增长。例如，调用fib2(4)将会导致如下一系列的调用：

计算一下调用次数（调用打印方法就可以看到相应的过程），仅为了计算第4个元素就需要调用9次fib2()!情况会越来越糟，计算第5个元素需要15次调用，计算第10个元素需要177次调用，计算第20个元素需要21891次调用。我们可以对这种情况进行优化。

1.1.3 使用记忆化

记忆化（Memoization）[1]是一种缓存技术，即在计算任务完成时将结果保存，以便下次需要时可以直接检索出结果，而无须一而再再而三地重复计算（见图1.4）。

让我们创建一个新的斐波那契方法，它将使用Java Map来实现记忆化。

现在就可以安全地调用fib3(40)了。

现在运行fib3(20)只会调用fib3()39次，而不会像fib2(20)那样产生21891次调用。memo中预先放入了基线条件0和1，并加入了一条if语句，从而大幅降低了fib3()的计算复杂度。

1.1.4 简洁的斐波那契方法

还有一个性能更好的方法。我们可以用老式的迭代方法求解斐波那契数列。

要点是last被设置为next的前一个值，next被设置为last的前一个值加上next的前一个值。使用临时变量oldLast在交换过程中进行过渡。

使用这种方法，for循环体将运行n-1次。这是迄今为止最高效的版本。为了计算第20个斐波那契数，这里的for循环体只需运行19次，而fib2()则需要21891次递归调用。这会对实际应用程序产生重大影响！

递归是反向求解，而迭代是正向求解。有时递归是解决问题最直观的方法。例如，fib1()和fib2()的实现基本上是原始斐波那契公式的直接转换。然而，直观的递归解决方案也会带来巨大的性能成本。请记住，任何可以使用递归解决的问题也可以使用迭代来解决。

1.1.5 使用流来生成斐波那契数列

到目前为止，已实现的方法都只能输出斐波那契数列中的单个值。如果要将某个数值之前的整个数列进行输出，又该怎么做呢？使用生成器模式很容易就能把fib4()转换为Java流。当生成器执行迭代时，每次迭代都会使用返回下一个数字的lambda函数从斐波那契数列中生成一个值。

运行Fib5.java，将会打印出斐波那契数列的前41个数字。对于数列中的每个数字，Fib5都会运行generate()这个lambda函数一次，它对用来保持状态的last和next实例变量进行操作。limit()用来确保可能会无限执行下去的流在到达第41项时停止输出数字。