什么是斐波那契数列？

• 斐波那契数列是这样一个数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…
• 从第 3 项开始，每一项都等于前两项之和（见下列表格）：

由此，我们可以得出一个斐波那契数列的分段函数：

于是按照分段函数，就可以得到其递归函数：

1
2int f(int n)
3{
4if (n <= 1)
5return 1;
6return f(n - 1) + f(n - 2);
7}
8

斐波那契数列的实现 - 循环

• 递归函数总是一个好的开始，但它也非常损耗性能，所以一般我们会将其改写成一个循环，从而降低代码的时间复杂度和空间复杂度。
• 首先，声明一个从 2 开始的循环，因为前两个情况我们已经返回了 。

1
2int f(int n)
3{
4if (n <= 1)
5return 1;
6+for (int i = 2; i <= n; i++)
7}
8

• 循环体内我们需要计算，所以我们需要声明 3 个变量：
  • 为待相加的前两个数。
  • 则是他们的和。

1
2int f(int n)
3{
4if (n <= 1)
5return 1;
6+int n1 = 0, n2 = 1, s = 0;
7for (int i = 2; i <= n; i++)
8}
9

• 现在我们就可以开始计算啦！计算完成之后，将 ， 来设置好下次迭代的初始值。
• 最后别忘记返回结果 哦！

1
2int f(int n)
3{
4if (n <= 1)
5return n;
6int n1 = 0, n2 = 1, s = 0;
7for (int i = 2; i <= n; i++)
8{
9+s = n1 + n2;
10+n1 = n2;
11+n2 = s;
12}
13+return s;
14}
15

• 至此，我们就通过循环完成了斐波那契数列的实现。
• 顺带一提，其时间复杂度取决于循环体的调用次数，所以为 。

斐波那契数列的实现 - 递归

• 回到最开始的递归函数，我们可以尝试分析其递归树来查看其是否能被优化。

• 我们看到许多函数例如 f(3) 被重复调用了多次。
• 所以我们可以将其值存储在一个静态数组里面，这样当我们需要调用函数之前，先检查数组里是否含有其答案，即已经调用过了；若有，则不需要调用。这样就可以节省许多的调用次数。

• 根据这个想法，我们就可以开始写函数了：

• 首先，先声明一个静态数组results[]并声明初始值为-1，这样只要判定数组的索引 n 下是否为-1，就能判断该函数是否被调用过。

1
2int f(int n)
3{
4+static int results[5] = {-1, -1, -1, -1, -1};
5-if (n <= 1) return 1;
6-return f(n - 1) + f(n - 2);
7}
8

• 其次，我们需要在每次调用之前判断是否调用过，若没有则调用该函数并赋值：
  • 对于 results[n-1] 和 results[n-2] ，我们分别检测是否已经被调用过；
  • 若没有，则调用并赋值。
  • 对于 ，我们也需要将 results[n] 赋值为 n。
  • 最后别忘了将 results[n] 赋值之后再返回！

1
2int f(int n)
3{
4static int results[5] = {-1, -1, -1, -1, -1};
5+if (n <= 1)
6+{
7+results[n] = n;
8+return n;
9+}
10+if (results[n - 2] == -1)  results[n - 2] = f(n - 2);
11+if (results[n - 1] == -1)  results[n - 1] = f(n - 1);
12+results[n] = results[n - 2] + results[n - 1];
13+return results[n];
14}
15