走进不一样的斐波那契数列

本文介绍了递归的原理及其斐波那契数列的四种实现方式。

所有源码均已上传至github：链接

递归

递归算是算法中比较难的点了。递归的应用非常广泛。呢什么样的问题可以用递归来解决呢？需要以下三个条件：

一个问题的解可以分解为几个子问题的解
这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
存在递归终止条件

经典案例：

比较经典的例子就是最知名的斐波那契数列了。本文也以斐波那契数列为例，先简单介绍一下，斐波那契数列（Fibonacci sequence），又称黄金分割数列（这个名字高大上）。

指的是这样一个数列：1、1、2、3、5、8、13、21、34、……

在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用。大致就是这样。

在写递归之前要注意这么几个问题：

递归的定义：简单理解就是函数自己调用自己，将问题不断分割成更小的子问题
递归的缺陷：递归到一定程度，会发生"栈溢出"，因为函数调用会使用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。
递归的"时间复杂度"：递归总次数*每次递归的次数
递归的"空间复杂度"：递归的深度*每次递归空间的大小（注意："每次递归空间的大小"是个常数，可以基本忽略不计）
递归的"深度"：树的高度（递归的过程是一个"二叉树"）

斐波那契数列的四种实现方式（两种递归，两种常规）

递归

时间复杂度：O(2^N)

空间复杂度：O(N)

这是最简单的递归，只有两行代码，是不是很简单呢？

	public int recursion(int num) {
		if (num < 3) return 1;
		return recursion(num - 1) + recursion(num - 2);
	}

但是这种实现的缺陷是重复计算的次数太多了，效率极其低下：

F(3) = F(1) + F(2);

F(4) = F(2) + F(3);

F(5) = F(3) + F(4);

F(6) = F(5) + F(6);

当计算到F(6)的时候，F(3)就已经重复了3次,因此改造一下：

	public int recursion(int num) {
		// 一定要先给出递归跳出条件
		if (num < 3)
			return 1;
		// resCache是一个HashMap，key是num，value是res
		if (resCache.containsKey(num)) {
			return resCache.get(num);
		}
		int res = recursion(num - 1) + recursion(num - 2);
		resCache.put(num, res);
		return res;
	}

ps：加一个hashMap来做缓存，避免重复计算

尾递归

时间复杂度：O(N-2)约等于0(N)

空间复杂度：O(N-2)约等于0(N)（编译器如果优化的话是O（1））

先简单了解一下什么是尾递归。

定义：在一个程序中，执行的最后一条语句是对自己的调用，而且没有别的运算
尾递归的实现：是在编译器优化的条件下实现的

小知识（编译器优化）：

递归的第一次调用时会开辟一份空间，此后的递归调用不会再开辟空间，而是在刚才开辟的空间上做一些修改，实现此次递归，例如求F(10)，编译器会给F(10)的调用开辟栈帧，调用F(9)的时候不会再重新开辟栈帧，而是在刚开辟的栈帧上做一些修改，因为递归的每一次调用都是一样的流程，只是会有一些数据不同，所以不会再开辟空间。

	public int tailRecursion(int num, int first, int second) {
		if (num < 3)
			return 1;
		if (num == 3)
			return first + second;
		return tailRecursion(num - 1, second, first + second);
	}

下面两种是非递归的实现，就比较简单了，在此不做阐述。

常规实现

	public int commonRcursion(int num) {
		if(num < 3) return 1;
		int first = 1;
		int second = 1;
		int res = 0;
		for (int i = 1; i < num - 1; i++) {
			res = first + second;
			first = second;
			second = res;
		}
		return res;
	}

基于数组的实现

	public int arrayRecursion(int num) {
		if(num < 3) return 1;
		int[] arrays = new int[num + 1];
		arrays[1] = 1;
		arrays[2] = 1;
		for (int i = 3; i <= num; i++) {
			arrays[i] = arrays[i - 1] + arrays[i - 2];
		}
		return arrays[num];
	}