估计找工作的，都会碰到面试官老是问道“递归算法”，感同身受，前段时间面试的时候，就有一家问道这个问题，是非常典型的问题。在前面一篇世界上有哪些代码量很少，但很牛逼很经典的算法或项目案例？，递归应该算是比较“经典”的算法。
1.从 斐波那契数列开始说起
波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144，是指这样一个数列
递推公式如图：
递推公式
有没有直接计算的公式？当然有
public int Fibo(int n)
{
double c = Math.Sqrt(5);
return (int)((Math.Pow((1 + c) / 2, n) - Math.Pow((1 - c) / 2, n)) / c);
}
1.最常见的递归
第一项和第二项的值均为1，后面每项的值都是前两项值之和，所以我们很多人基本上都会使用递归来实现，常见的算法如下：
public int Fibo(int n)
{
if (n == 1 || n == 2)
{
return 1;
}
return Fibo(n - 2) + Fibo(n - 1);
}
但这种做法并不能完全解决问题，因为最大允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算。如果实时计算，代码过于复杂，就会影响代码的可读性。所以，如果最大深度比较小，比如 10、50，就可以用这种方法，否则这种方法并不是很实用。
ps：递归代码要警惕重复计算
除此之外，使用递归时还会出现重复计算的问题。刚才我讲的第二个递归代码的例子，如果我们把刚才我讲的第二个递归代码的例子，如果我们把整个递归过程分解一下的话，那就是这样的：
n 越大，这段代码执行效率越低通过测试一下看他的效率如何
Stopwatch sw = new Stopwatch();
sw.Start();
var result = Fibo(40);
sw.Stop();
Debug.WriteLine("n=100；result="+result+"；耗时："+sw.ElapsedMilliseconds);
n=10；result=55；耗时：2715
n=40；result=102334155；耗时：4673
如果n再稍微大一点，所消耗的时间是成指数级增长的，比如n=64的时候，所消耗的时间可能是两三年！不信的话，你可以试试！
我们会发现f(n)这个方法被调用了很多次，而且其中重复率非常之高，也就是说被重复计算了很多次，如果n稍微大一点这棵树会非常庞大。这里我们可以看出，每个节点就需要计算一次，总计算的次数就是该二叉树节点的数量，可见其时间复杂度为O(2n)，是指数级的，其空间复杂度也就是该二叉树的高度，为O(n)。这样来看，我们应该就清楚了，为什么这段代码效率如此低下了吧。
2.数组保存法
我们应该避免无数次重复的计算
为了避免无数次重复，可以从n=1开始往上计算，并把每一个计算出来的数据，用一个数组保存，需要最终值时直接从数组中取即可，算法如下：
public int fib(int n) {
int[] fib = new int[n];
fib[0] = 1;
fib[1] = 1;
for (int i = 2; i < n; i++) {
fib[i] = fib[i - 2] + fib[i - 1];
}
return fib[n - 1];
}
测试一下结果
n=10；result=55；耗时：0
n=40；result=102334155；耗时：0
n=1000000；result=1884755131；耗时：5
毫秒级，几乎忽略不计的，当计算100万时，也就5毫秒
3.滚动数组法
尽管上述算法已经很高效了，但我们还是会发现一个问题，其实整个数组中，每次计算时都只需要最新的3个值，前面的值计算完后就不再需要了。比如，计算到第10次时，需要的数组空间只有第8和第9两个空间，前面第1到第7个空间其实就不再需要了。所以我们还可以改进，通过3个变量来存储数据，算法如下：
public int Fibo3(int n)
{
int first = 1;
int second = 1;
int third = 2;
for (int i = 3; i <= n; i++)
{
third = first + second;
first = second;
second = third;
}
return third;
}
时间复杂度仍然为O(n)，而空间复杂度为常量级别3，即空间复杂度为0，所以这种方法是非常高效的。
3.尾递归法
首先我们来了解一下什么是尾调用。
在计算机科学里，尾调用是指一个函数里的最后一个动作是一个函数调用的情形：即这个调用的返回值直接被当前函数返回的情形。这种情形下该调用位置为尾位置。
/// n 第n个数
/// first 第n个数
/// second 第n与第n+1个数的和
/// @return 返回斐波那契数列值
public int Fib5(int n, int first, int second) {
if (n <= 1) {
return first;
} else {
return fib5(n-1,second,first+second);
}
}
，也都是通过两个变量保存计算值，传递给下一次进行计算，递归的过程中也是根据n值变化逐步重复运算，和循环差不多，时间复杂度和空间复杂度也都一样,优雅了很多。
我们知道递归调用是通过栈来实现的，每调用一次函数，系统都将函数当前的变量、返回地址等信息保存为一个栈帧压入到栈中，那么一旦要处理的运算很大或者数据很多，有可能会导致很多函数调用或者很大的栈帧，这样不断的压栈，很容易导致栈的溢出。
还有一种优化思路就是矩阵快速幂法，可参考链接 /computer_user/article/details/86927209
回复
【关闭】
学关闭微信朋友圈广告
回复【实战】获取20套实战源码
回复【福利】获取最新微信支付有奖励
回复【被删】学查看你哪个好友删除了你巧
回复【访客】学微信查看朋友圈访客记录
回复【卡通】
学制作微信卡通头像
回复【python】
学微获取全套0基础Python知识手册
回复【】获取 .NET 开发者峰会资料PPT
如果觉得《Php斐波那契数列尾递归优化 递归优化的这三种方式你知道吗？》对你有帮助，请点赞、收藏，并留下你的观点哦！
