斐波那契数列的三种写法（递归，循环，改进后的递归）

斐波那契数列

我们将F(n) = 1，1，2，3，5，8，13…(F(n-1)+F(n-2))这样的数列称为斐波那契数列

实现

1. 普通递归

int f1(int n)
{
	if(n <= 2)
		return 1;
	else
		return f1(n-1) + f1(n-2);
}

我们不难发现递归可以让我们的代码量很少，但是其时间复杂度较大，普通递归的时间复杂度为O(2^n)。这意味着什么呢，我们顺便了解一下算法复杂度的概念
  算法复杂度分为时间复杂度和空间复杂度。其作用： 时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。（算法的复杂性体运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度。）
我们一般衡量代码的质量主要看时间复杂度。接下来我们分析一下上面代码的递归过程如下图。

2.循环

int f2(int n)
{
	int t,first = 1,second = 1;
	if(n == 1 || n == 2)
		return 1;
	for( ; n>=3; n--)
	{
		t = first+second;
		first = second;
		second = t;
	}
	return t;
}

时间复杂度O(n)，空间复杂度O(1)

3.改进后的递归

算法是博大精深的，我们不仅要会写代码更要写好代码，接下来我们对普通递归进行优化，我们仔细观察就会发现递归和循环之间是有某种联系的，递归有些像逆循环，掌握这个思想后我们来实现改进后的递归函数。

int f3(int first, int second, int n)
{
	if(n == 1 || n == 2)
		return 1;
	else if (n == 3)
		return first + second;
	else
		return f3(second, first + second, n - 1);
 
}

代码中实现递归调用的时候和上面循环方法的赋值是相同的，例如第一次递归调用的时候将second赋值给first，first+second赋值给second。该方法时间复杂度O(n)，空间复杂度O(1)

总结

  我们发现递归的代码量很少，但是普通递归的时间复杂度很大，在我们进行优化后，便可以得到代码量又少，算法复杂度交低的代码了。
  根据效率从高到低的时间复杂度排序为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、 立方阶O(n^3)、 k次方阶O(n^k)、 指数阶O(2^n)。