平时在做题的时候，我们经常都要用到递归来解题，因为递归能最快速的让计算机知道我们想让他做什么，解放了我们的思维量（但在一定程度上加重了计算机的计算量，这也是可能超时的原因所在），方便我们阅读理解和修改。
这里我想再引用一下Leigh Caldwell在Stack Overflow上说的一句话：
“如果使用循环，程序的性能可能会更高，如果使用递归，程序可能更容易理解，如何选择要看什么对你来说更重要。”
如果你还不太理解递归，可以看我之前写过的一篇文章
也许正在学习练习递归的你并没有碰到递归超时的情况，那可能的原因是题目的测试数据太小啦！你的计算机计算能力还算可以，所以就不存在超时的问题。
下面我以斐波那契数列举个例子让你理解下为什么会超时
我们都知道斐波那契数列从第三项开始每一项为前两项的和，那么如果我们要求第七项，那么流程如下：
嗯，也许你已经发现了不对的地方，我们重复计算了5两遍，4三遍，3四遍…如果项数很大，重复计算的次数只会越来越多
导致这样子的原因取决于递归的本质所决定的，我将此理解为触底才反弹。（下面会详细解释）
注意，我觉得这里要先特别区分一下递推和递归的区别，虽然只有一字之差，但意思和本质却截然相反。从小学数学的时候其实我们就已经接触了递推，就姑且还以斐波那切数列为例吧，我们只有知道了前面几项，比如1、2才能推第三项的值，只有知道了第三项和第四项的值才能推出第五项…以此类推递推到我们需要求的那个项，有点类似于滚大雪球吧，只能从小雪球滚起。
而递归呢，方向就是相反的（但最后求解过程中又包括递推），先告诉你，我要求第100项的值，嗯，这时候你就说“只要我知道第98项和第99项我就能求出第100项”，紧接着“只要我知道第97和98项我就能求出第99项”…等等等等这样一直把大问题（求第100项的值）逐渐化解为小问题（第99、98、…、1项的值），从上往下递归，直到递归到最低，也就是第一项时停止，然后原路一层层的把数值返回，从第一项第二项求出第三项，返回求出第四项（这里不就是递推吗）所以我更倾向于把递归理解为反向索引+递推。
总结来说递推就是自底向上，从下往上求解，而递归是从上往下，触底反弹，返回答案。
嗯，可能你已经有点感悟了，其实在大部分情况下递归都能用递推来实现，甚至在某些情况下递推还要更好，因为递推是记忆化的，而递归要看你如何设计了，如果不是记忆化的递归，那么每次都要触底才能反弹，也未免太浪费时间了。是的，在有时候碰到数据很大的时候，用递归固然可以直接解放你的思维量，让代码看上去很简洁，也易于别人阅读和修改，但随之而来的可能是空间的极度浪费或者根本就不够用啊，这时候你就要用递推了
我们还是以例题来说明吧
在这道题中，我们先看下我一开始写的递归代码：
#include <stdio.h>
int num( int n )
{
int total = 0;
int i;
if ( n==1 )
return n;
else
{
for ( i=2; i<=n; i++ )
{
total += num(i-1);
}
total++;
return total;
}
}
int main()
{
int t;
scanf ( "%d", &t );
while ( t-- )
{
int n;
scanf ( "%d", &n );
printf ( "%d\n",num(n) );
}
return 0;
}
推荐大家上机运行看看，当输入15、20等数据时几乎是秒出答案，但29、30时就要等上大概1秒的时间了，的确，刚刚上面已经给大家一个直观的理解了，重复计算的部分的确很多。
那这道题如何改成递推呢？（或者记忆化递归呢？）
先上代码：
#include <bits/stdc++.h>
using namespace std;
int stair[31];
int main()
{
int t,n;
int i,j;
cin >> t;
while ( t-- )
{
cin >> n;
stair[1] = 1;
stair[2] = 2;
for ( i=3; i<=n; i++ )
{
if ( stair[i] == 0 )
{
for ( j=i-1; j>0; j-- )
stair[i]+=stair[j];
stair[i]++;
}
}
cout << stair[n] << endl;
}
return 0;
}
这个代码的思路就是将算好的数据储存在数组中，然后在大数据的时候直接调用，如果调用的时候还没算好就先算好再调用计算。这样子就相当于“记忆”下了递归的结果，不用每次都重新计算啦！
大部分的递归优化都可以通过记忆化递归或递推实现~
什么？你还是有点半蒙半懂的？没事，多自己练习优化就会啦，下面几个例子都是我自己踩过的雷，就是自己用递归超时被WA，用递推就AC的例子，都有较详细的解说并附上了递归和递推的代码
为了确保大家能够看懂我的文章，我尽量每字每句都详细讲解，给出证明和解释，真心希望你能够在阅读此篇文章后从中多多少少有所收获。因此每篇文章我都投入了大量的时间和精力，去举例，去说明，去分析，如果你觉得这篇文章写的还不错，点赞、关注和收藏一键三连就是对我最大的鼓励啦，我以后也会写更多更高质量的文章！也欢迎一起讨论指出文章可能存在的逻辑问题~