01.斐波那契数列

目录介绍

• 01.题目要求
• 02.问题分析
• 03.实例代码
• 04.为何递归效率低
• 05.递归迭代效率比较
• 06.递归优化

01.题目要求

• 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39

02.问题分析

2.1 什么是斐波那契数列？

• 1，1，2，3，5，8，13，21......斐波那契数列从第三项开始，每一项都等于前两项之和。斐波那契数列是由数学家 Leonardoda Fibonacci 以兔子繁殖为例子而提出的，所以也叫做“兔子数列”。

2.2 解题思路

• 可以肯定的是这一题通过递归的方式是肯定能做出来，但是这样会有一个很大的问题，那就是递归大量的重复计算会导致内存溢出。另外可以使用迭代法，用fn1和fn2保存计算过程中的结果，并复用起来。下面我会把两个方法示例代码都给出来并给出两个方法的运行时间对比。

03.实例代码

3.1 代码如下所示

• 采用迭代法：

  int Fibonacci(int number) {
  	if (number <= 0) {
  		return 0;
  	}
  	if (number == 1 || number == 2) {
  		return 1;
  	}
  	int first = 1, second = 1, third = 0;
  	for (int i = 3; i <= number; i++) {
  		third = first + second;
  		first = second;
  		second = third;
  	}
  	return third;
  }

• 采用递归：f(n) = f(n-1) + f(n-2)

  public int Fibonacci(int n) {
      if (n <= 0) {
      	return 0;
      }
      if (n == 1||n==2) {
      	return 1;
      }
      return Fibonacci(n - 2) + Fibonacci(n - 1);
  }

3.2 执行时间对比

• 假设n为40我们分别使用迭代法和递归法计算，计算结果如下：
  • 1.迭代法：耗费时间1ms
  • 2.递归法：耗费时间272ms

04.为何递归效率低

• 如果简单分析一下程序的执行流，就会发现问题在哪，以计算Fibonacci(5)为例：
  • 
    image
• 从上图可以看出，在计算Fib(5)的过程中，Fib(1)计算了两次、Fib(2)计算了3次，Fib(3)计算了两次，本来只需要5次计算就可以完成的任务却计算了9次。这个问题随着规模的增加会愈发凸显，以至于Fib(1000)已经无法再可接受的时间内算出。
• 当时使用的是简单的用定义来求 fib(n)，也就是使用公式 fib(n) = fib(n-1) + fib(n-2)。这样的想法是很容易想到的，可是仔细分析一下我们发现，当调用fib(n-1)的时候，还要调用fib(n-2)，也就是说fib(n-2)调用了两次，同样的道理，调用f(n-2)时f(n-3)也调用了两次，而这些冗余的调用是完全没有必要的。可以计算这个算法的复杂度是指数级的。

05.递归迭代效率比较

• 递归调用实际上是函数自己在调用自己，而函数的调用开销是很大的，系统要为每次函数调用分配存储空间，并将调用点压栈予以记录。而在函数调用结束后，还要释放空间，弹栈恢复断点。所以说，函数调用不仅浪费空间，还浪费时间。它的很多时间浪费在对函数调用的处理上。

06.递归优化

• 第一种方式，采用迭代法，这种方式是最直观的。