斐波那契数列的三种写法

前言

　　本文预示着 Shaun 开始着手准备找工作的事了，初步计划是先把『剑指Offer』上的题先做一遍，对照着 牛客网 上的题进行测试，尽量争取先把书上的题都能 AC 。一般定义的斐波那契数列数列为：0,1,1,2,3,5,8……（对应 \(F(0)=0, F(1)=1, F(2)=1, \cdots \cdots\)），用数学公式表示即为：\(F(n)=F(n-1)+F(n-2)\)。以下代码均用 C++ 实现，且均通过牛客的测试。

循环写法

int fibonacci_loop(const unsigned int &n)
{
	int fn = 0, f1 = 0, f2 = 1;
	for (int i = 0; i < n; i++)
	{
		fn = f1 + f2;
		f2 = f1;
		f1 = fn;
	}
	return fn;
}

递归写法

int fibonacci_recursive(const unsigned int &n)
{
	if (n == 0)
	{
		return 0;
	}
	else if (n == 1 || n == 2)
	{
		return 1;
	} 
	else
	{
		return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
	}
}

　　※注：这里 Shaun 在牛客上进行测试的时候，如果把 || n == 2 去掉的话，就没法通过，可见多递归一次花费的时间并不是线性增长的。

尾递归写法

　　说来惭愧，这个概念还是在一个小学弟那里得知的，后面才逐渐了解并学会使用。

　　尾递归，简而言之就是最后会且仅会调用函数本身，递归调用函数之后没有其它的语句需要执行。就像上面的递归，它在递归调用之后还会执行加法运算，而尾递归在执行递归调用之后就没有其它的运算了。

int fibonacci_tailRecursive(unsigned int n, unsigned int f1 = 1, unsigned int fn = 0)
{
	if (n == 0)
	{
		return fn;
	}
	else
	{
		return fibonacci_tailRecursive(n - 1, fn, fn + f1);
	}
}

总结

　　循环和尾递归花费的时间和空间都差不多，都要比普通的递归要小，普通的递归优势在于便于理解，代码好写，在不强调性能的前提下，用递归写法的代码可读性可能要好些。

参考资料

[1] 递归与尾递归总结（http://www.cnblogs.com/Anker/category/436371.html）