和arden一起学算法--第五天

第五天 递归

今天我们一起学习递归这个常见的命题。从这个命题中我们学习这样一种特殊的数据结构：树。在学习数学的时候引来了这个概念，它表示一个可以通过自己来表示的函数。比较通俗的定义是：调用自身的程序。

最常见的一个例子是阶乘：

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下，太多了。