大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > C++技巧 > C语言/C++递归算法

C语言/C++递归算法(1)

关键词:C语言C++递归算法  阅读(1159) 赞(18)

[摘要]本文是对【C语言/C++】 递归算法的讲解,对学习C++编程技术有所帮助,与大家分享。

递归算法也是C语言算法中一个比较简单与常用的算法,本文我们就来谈谈递归算法,我们首先了解一下什么是递归算法,关于递归算法的概念只有一句话:一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).。

我们再来看看递归算法的特点:

(1) 递归就是在过程或函数里调用自身。

(2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。

(3) 递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。

(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。

再看看递归的分类:

直接递归
程序设计中,过程或函数直接或者间接调用自己,就被称为递归调用。子程序直接调用自己,这称为直接递归;嵌套关系的子程序A和B,内层的B调用外层的A,这是间接低归;平级关系的子程序A和B,其中A调用了B,B调用了A,这也是间接递归,不过,这种间接递归用到了“超前引用”的规则。

下面,博主找到了一些有关于递归算法的题目。我们看看第一个题目。

这是一道很经典的题目:阶乘。相信大部分的人都知道什么是阶乘,但是你如果不知道的话,不妨参见一下百度百科:阶乘。

好了,其实这题非常简单,我们只需要一个函数即可解决问题。

 int recursive(int i)
 {
     int sum = 0;
     if (0 == i)
         return (1);
     else
         sum = i * recursive(i-1);
     return sum;
 }

就是上面的递归函数,这题我就不浪费篇幅讲解了,重点放在第二个例题:汉诺塔问题。

一个庙里有三个柱子,第一个有64个盘子,从上往下盘子越来越大。要求庙里的老和尚把这64个盘子全部移动到第三个柱子上。移动的时候始终只能小盘子压着大盘子。而且每次只能移动一个。1、此时老和尚(后面我们叫他第一个和尚)觉得很难,所以他想:要是有一个人能把前63个盘子先移动到第二个柱子上,我再把最后一个盘子直接移动到第三个柱子,再让那个人把刚才的前63个盘子从第二个柱子上移动到第三个柱子上,我的任务就完成了,简单。所以他找了比他年轻的和尚(后面我们叫他第二个和尚),命令:

① 你把前63个盘子移动到第二柱子上

② 然后我自己把第64个盘子移动到第三个柱子上后

③ 你把前63个盘子移动到第三柱子上
2、第二个和尚接了任务,也觉得很难,所以他也和第一个和尚一样想:要是有一个人能把前62个盘子先移动到第三个柱子上,我再把最后一个盘子直接移动到第二个柱子,再让那个人把刚才的前62个盘子从第三个柱子上移动到第三个柱子上,我的任务就完成了,简单。所以他也找了比他年轻的和尚(后面我们叫他第三和尚),命令:

① 你把前62个盘子移动到第三柱子上

② 然后我自己把第63个盘子移动到第二个柱子上后

③ 你把前62个盘子移动到第二柱子上
3、第三个和尚接了任务,又把移动前61个盘子的任务依葫芦话瓢的交给了第四个和尚,等等递推下去,直到把任务交给了第64个和尚为止(估计第64个和尚很郁闷,没机会也命令下别人,因为到他这里盘子已经只有一个了)。

4、到此任务下交完成,到各司其职完成的时候了。完成回推了:
第64个和尚移动第1个盘子,把它移开,然后第63个和尚移动他给自己分配的第2个盘子。
第64个和尚再把第1个盘子移动到第2个盘子上。到这里第64个和尚的任务完成,第63个和尚完成了第62个和尚交给他的任务的第一步。
从上面可以看出,只有第64个和尚的任务完成了,第63个和尚的任务才能完成,只有第2个和尚----第64个和尚的任务完成后,第1个和尚的任务才能完成。这是一个典型的递归问题。 现在我们以有3个盘子来分析:

第1个和尚命令:

① 第2个和尚你先把第一柱子前2个盘子移动到第二柱子。(借助第三个柱子)

② 第1个和尚我自己把第一柱子最后的盘子移动到第三柱子。

③ 第2个和尚你把前2个盘子从第二柱子移动到第三柱子。
很显然,第二步很容易实现。

其中第一步,第2个和尚他有2个盘子,他就命令:

① 第3个和尚你把第一柱子第1个盘子移动到第三柱子。(借助第二柱子)

② 第2个和尚我自己把第一柱子第2个盘子移动到第二柱子上。

③ 第3个和尚你把第1个盘子从第三柱子移动到第二柱子。

同样,第二步很容易实现,但第3个和尚他只需要移动1个盘子,所以他也不用在下派任务了。(注意:这就是停止递归的条件,也叫边界值)
第三步可以分解为,第2个和尚还是有2个盘子,命令:
① 第3个和尚你把第二柱子上的第1个盘子移动到第一柱子。

② 第2个和尚我把第2个盘子从第二柱子移动到第三柱子。

③ 第3个和尚你把第一柱子上的盘子移动到第三柱子。
分析组合起来就是:1→3 1→2 3→2借助第三个柱子移动到第二个柱子 |1→3|2→1 2→3 1→3借助第一个柱子移动到第三个柱子|共需要七步。

如果是4个盘子,则第一个和尚的命令中第1步和第3步各有3个盘子,所以各需要7步,共14步,再加上第1个和尚的1步,所以4个盘子总共需要移动7+1+7=15步,同样,5个盘子需要15+1+15=31步,6个盘子需要31+1+31=64步……由此可以知道,移动n个盘子需要(2的n次方)-1步。

从上面整体综合分析可知把n个盘子从1座(相当第一柱子)移到3座(相当第三柱子):
(1)把1座上(n-1)个盘子借助3座移到2座。
(2)把1座上第n个盘子移动3座。
(3)把2座上(n-1)个盘子借助1座移动3座。
下面用hanoi(n,a,b,c)表示把1座n个盘子借助2座移动到3座。
很明显: (1)步上是 hanoi(n-1,1,3,2)(3)步上是 hanoi(n-1,2,1,3)
用C语言表示出来,就是:

«上一页12下一页»


相关评论