写在前面
其实我也说不太清楚到底递归算不算算法，因为我一开始从0基础接触递归是从《算法图解》这本书中得知的（也很推荐刚学算法的朋友可以先看看这本书，写的挺不错的），也就把它当成算法了。但写了那么多题目，渐渐的感觉递归这个东西把，它更像是一种工具而已，要用的时候很自然而然地就和加减乘除一样用上了，不会特别感受得到它地存在（也正是因为理解地不深刻，导致我经常用错陷入死循环）。
再次深入理解递归
回想起第一次接触递归是在这道题上母牛的故事——函数与类斐波那契数列，其实当时在写这道题时真的没有刻意去说 啊 我要用递归，只不过考到了类斐波那契数列，感觉如果用函数会思路会更清晰简洁一点。
我们现在再回顾一下这个题目的核心代码
int cow(int n)
{
if ( n<=4 ) return n;
else return cow(n-1) + cow(n-3);
}
虽然只有五行代码，但却囊括了递归的两大基本要素，即基线条件和递归条件，其实我觉得第一个名字有点绕，或者说不好理解。
我更倾向于把基线条件理解为“结束条件”，递归条件就比较好理解了，就是递归的主体部分。如上面中
if ( n<=4 ) return n;
是基线条件，当n小于等于4就跳出递归,而
else return cow(n-1) + cow(n-3);
就是递归条件啦，在没有达到结束底线的时候就执行它，得到答案。
也许你会说，这个直接在main函数里面通过while循环也能实现啊，是的，这也印证了Leigh Caldwell在Stack Overflow上说的一句话：
“如果使用循环，程序的性能可能会更高，如果使用递归，程序可能更容易理解，如何选择要看什么对你来说更重要。”
还是这道题，我们看下整个代码
#include <stdio.h>
int cow(int n)
{
if ( n<=4 ) return n;
else return cow(n-1) + cow(n-3);
}
int main(void)
{
int n;
while ( ~scanf("%d", &n) )
{
if ( n==0 ) break;
printf ( "%d\n", cow(n) );
}
return 0;
}
可以看出，用了递归函数后整个程序显得结构分明，十分利于理解，如果把递归用while或者for循环写到main里面以打表的形式（还可以用滚动数组的方式优化打表的空间复杂度）算结果也不是不行，且在性能上，如果有多组输入输出的话，循环会更快（因为递归每次都有从大数据一直算算算算到基线条件）但只是阅读性差了点而已。
设计递归的易错点
在深入理解完递归后，我们重点关注下在实际应用时的易错点，因为到最后都要学以致用，实践才是唯一标准。
下面是我个人在用递归时的几个常见错误，均有例题解说以加深印象：
错误一：分裂基线条件和递归条件
母牛的故事——函数与类斐波那契数列
对，还是这道题，这道题上收录了一开始我写错的代码，现在拿出来分析下
#include <stdio.h>
int cow_num( int year );
int main()
{
int y;
while ( ~scanf("%d", &y) )
{
if ( y==0 ) break;
if ( y<=4 )
printf ( "%d\n", y );
else
printf ( "%d\n", cow_num(y) );
}
return 0;
}
int cow_num( int year )
{
int num;
num = cow_num(year-1) + cow_num(year-3);
return num;
}
通过对比可以很明显的看出这里我把基线条件写到main函数里面了，导致递归缺少跳出的条件，根本的不出答案。
错误二：忘记写基线条件
过河问题——动态规划的经典线性模型
这个和上一个错误有点像，但这个更致命，连跳出条件都忘记写了，会陷入死循环的，调试时直接崩掉死机。
int DP(int i)
{
//打表前几个数据
dp[1]=a[1];
dp[2]=a[1];
dp[3]=a[1]+a[0]+a[2];
dp[i] = min ( ( DP(i-1) + a[0] + a[i] ),( DP(i-2) + a[0] + a[i] + 2*a[1] ) );
return dp[i];
}
上面这个就是没有基线条件，dp(i-1)会一直执行，从4，3，2，1，0，-1，-2，-3，-4…永无止境的循环下去。
绝对值排序——快速排序
这道错题也是，在写快速排序的时候忘记写结束递归的条件了，导致快排无法实现。
错误三：找不准递归条件
跳台阶——超时、递归、斐波那契
这点就很扎心了，其实整个递归最核心的部分就是递归条件，这个式子一旦列错那这道题肯定就解不出来，有时候可能递归着递归着自己就被绕进去了，深陷其中无法自拔。上面这个跳台阶就是例题之一，真的有点晕，找不准或者说不确定这是不是递归条件。有时候又可能出现多递归一次或少递归一次的情况（但这个往往都是和下标从0开始数还是1开始数有关）。
一半这种情况的解决方案，我是更倾向于还是老老实实地拿起笔和纸在草稿纸上老老实实地画吧，把前面几组的数据自己先算一算把，假若还是理解不了，实在不行找规律也行呀（笑）。
写在后面：
第100篇博客啦！本来想在这个有纪念意义的时刻写点其他东西的，但还是写了技术博客，也不侨情做做了，以后继续努力，坚持输入和高质量的输出把。
