02.斐波那契数列.md

目录介绍

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

好消息

• 博客笔记大汇总【15年10月到至今】，包括Java基础及深入知识点，Android技术博客，Python学习笔记等等，还包括平时开发中遇到的bug汇总，当然也在工作之余收集了大量的面试题，长期更新维护并且修正，持续完善……开源的文件是markdown格式的！同时也开源了生活博客，从12年起，积累共计N篇[近100万字，陆续搬到网上]，转载请注明出处，谢谢！所有博客陆续更新到GitHub上！
• 链接地址：https://github.com/yangchong211/YCBlogs
• 如果觉得好，可以star一下，谢谢！当然也欢迎提出建议，万事起于忽微，量变引起质变！

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)为例：
  • 
• 从上图可以看出，在计算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.递归优化

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

7.其他内容

01.关于博客汇总链接

• 1.技术博客汇总
• 2.开源项目汇总
• 3.生活博客汇总
• 4.喜马拉雅音频汇总
• 5.其他汇总

02.关于我的博客

• 我的个人站点：
• github：https://github.com/yangchong211
• 知乎：https://www.zhihu.com/people/yczbj/activities
• 简书：http://www.jianshu.com/u/b7b2c6ed9284
• csdn：http://my.csdn.net/m0_37700275
• 喜马拉雅听书：http://www.ximalaya.com/zhubo/71989305/
• 开源中国：https://my.oschina.net/zbj1618/blog
• 泡在网上的日子：http://www.jcodecraeer.com/member/content_list.php?channelid=1
• 邮箱：[email protected]
• 阿里云博客：https://yq.aliyun.com/users/article?spm=5176.100- 239.headeruserinfo.3.dT4bcV
• segmentfault头条：https://segmentfault.com/u/xiangjianyu/articles
• 掘金：https://juejin.im/user/5939433efe88c2006afa0c6e