第五天 递归
今天我们一起学习递归这个常见的命题。从这个命题中我们学习这样一种特殊的数据结构：树。在学习数学的时候引来了这个概念，它表示一个可以通过自己来表示的函数。比较通俗的定义是：调用自身的程序。
最常见的一个例子是阶乘：
1 n=0;
F(n)=
F(n-1) n>=1;
如果直接计算，可以使用一个循环：for(n=1,s=1; n<=N; n++) s*=n; 这也是按照数学定义式来计算的，但是将这两个表达放在一起也需要人的思维整合过程。下面使用递归的方法可以更加直观的表示其定义：
Int fac(int N)
{
If (N==0) return 0;
return N*fac(N-1);
}
我们在高中、大学的数学课上都做过很多，需要找到F(n)=Q(n)*F(n-1)这样关系来解决的问题(Q(n)相对比较好计算)。而在计算机中使用递归可以使用更简洁的代码表达程序员的思想，并且良好的递归效率并不差（其函数调用底层机制是使用下堆栈来实现的）。可以看到，递归总是可以找到等同的非递归算法。而且大部分的for循环都可以转化成一个递归式。
使用递归需要注意的是它的递归深度。这可能导致我们的递归无法完成。
我们来看看递归的基本结构：
1、 它需要解决一个基本的情况：如阶乘的0！=1
2、 每次递归都需要逼近基本的情况： n！=(n-1)!*n；
这样递归的正确性我们可以使用归纳法来证明，阶乘这样的直接用定义式来表达的就不需要证明了吧。
有一个命题叫母牛问题：
若一头小母牛, 从出生第四年开始每年生一头小母牛,按此规律,第n年时有多少头母牛
这个问题可以很好的使用递归方法表达人的思考方式。我们在解决此问题时需要找到一个表示母牛数量的数学等式。
前面3年中，没有新的小牛成为妈妈。那么3年后，不断有小牛变成妈妈。我们来这样写此表达式：N年时牛的数量=N-3年时牛的数量+N-1年时牛的数量。
N-3年前牛的数量其实就是N-1年时牛妈妈的数量。
并且有N=1时，牛的数量为count。如此分析，它可以套用上面的公式来解决问题了。
cpp递归实现：
//this function is write by zhouhuahai(大草原) in CSDN
int getNumber(int years)
{
if(years<4 && years>=0)
return 1;
else
return getNumber(years-1)+getNumber(years-3);
}
这里还有一个非递归的算法，大家可以比较参考下。
// this function write by pomelowu(羽战士) in CSDN
int GetBaby (int n)
{
int sum = 0;
if (n >= 4)
{
for(int i = 1; i <= n - 4 + 1; i ++)
{
sum ++;
sum += GetBaby(i); //虽然不是递归这里却也调用了自己仍然有递归的成分在里面
}
}
return sum;
}
上面的两个程序来自CSDN的两位朋友。这个问题在chinaunix板块上讨论了很长时间。有兴趣的朋友可以去参加一下。地址：
http://www.chinaunix.net/jh/23/130156.html
给大家留个练习：fibonacci数列：1，1，2，3，5，8，13 … 请给出来此数列的第N项递归算法。不写答案了，去google上自己search下，太多了。
