C语言初学者这样理解递归

2016-12-17 12:04:11来源:作者:异步社区人点击

题外:目前在学习Stephen Prata的《C PrimerPlus》。最初决定学习C时,先通读了谭浩强老师的《C程序设计(第四版)》两遍,毕竟此书是很多高校C语言的学习教材,C的特点及基本的语法已有所了解。于是兴致勃勃的找了几个C开发的案例来看,结果是一脸懵逼。感觉《C程序设计》一书中只是讲解了C最基本的知识点,一些比较深入的内容并没有涉及。于是有了再看看其他C语言类书籍的念头,《C PrimerPlus》出现了(双十一老马家买的,巨便宜。。。窃喜。。。)。

又学到递归,其实结合谭老师《C程序设计》内的讲解,根据实例程序的运行结果,这一部分能理解,但有些牵强,总有种不上不下、半吊子的感觉,理解非常不深入,更谈不上灵活运用。

于是逛论坛、看帖子不亦乐乎,上网搜各种关于递归的讲解。

生硬滴转入正题。

看例子。谭老师用的汉诺塔例子就比较经典,很多人应该都玩过这个小游戏,很容易理解。有一个老和尚戒懒想把64个盘子借助B座从A座移到C座,规定每次只能移动一个盘,且在移动过程中在3个座上都始终保持大盘在下,小盘在上。

“递归”顾名思义,递:传递,传递的是什么呢?就是将复杂问题一步步传递给简单问题,直到最简单的解决方法。戒懒就是用的这种传递方法,找第2个和尚戒色将上面的63个盘子从一个座移到另一个座,那戒懒只需要移动第64个盘子就可以了,问题就解决了。

梳理一下:

①第2个和尚戒色将63个盘子从A座移到B座(不管他用什么方法,反正就是移过去了);

②戒懒将第64个盘子从A座移到C座;

③再让戒色将63个盘子从B座移到C座。

同理,第2个和尚戒色找了第3个和尚戒酒来移动62个盘子,第3个和尚戒酒找了第4个和尚戒烟移动61个盘子,以此类推,一个个传递下去,最终找的第64个和尚断奶只需要能移动1个盘子即可。

至于“归”,就是回来。就是从最简单的解决方法一步步返回,直到最终解决问题。也就是第64个和尚断奶完成移动1个盘子,使第63个和尚戒糖能成功移动2个盘子,再使第62个和尚戒怒能成功移动3个盘子,以此类推,最终让第2个和尚戒色能成功移动63个盘子时,戒懒就能完成所有盘子的移动了。

总结来说,递归分为"递"和"归"。递就是传递,就是将一个规模较大问题传递给稍小的问题(除了规模稍小,其他都相似,也就是需要保证解决大问题的方法和解决小问题的方法是类似的,才能使用函数调用它自身。),稍小问题传递给更小问题,直到不能再小,那么这时候函数就得到一个最终的值,这个值是很容易知道(最小问题(断奶小和尚)的解决方法)。这时候就执行"归",函数带着那个最终的值按顺序逐级返回,直到返回问题本身时,就终止了"归",最终的结果返回给调用函数。

递归的思路理解了,但对具体程序实现来说,递归有两个难点:

①递归就是函数直接或间接调用自身,那么它是怎么执行的呢?

②递归什么时候该终止呢?它又是怎么返回的?

如果能明白了这两点,恭喜你,你已经掌握了。

用例子来说明一下(《C PrimerPlus》的例子,最开始的时候很不容易理解):

运行结果:

程序分析:

①main()调用了带参数1的ud()函数,执行结果是ud()中的形式参数n的值是1,所以执行第一条打印语句,打印“行(递归前)1”。

②由于n小于4,ud()(第1级)根据ud(n+1)语句调用实际参数为2的ud()(第2级)。于是第2级调用中的n的值是2,执行第一条语句,打印“行(递归前)2”。

③以此类推,下面两次调用打印的分别是“行(递归前)3”和“行(递归前)4”。

④当执行到第4级时,n的值是4,所以if测试条件为假。ud()函数不再调用自己。第4级调用接着执行第二条打印语句,即打印“行(递归后)4”,因为n的值是4。此时,第4级调用结束,控制被传回它的主调函数(即第3级调用)。

⑤在第3级调用中,执行的最后一条语句是调用if语句中的第4级调用。被调函数(第4级调用)把控制返回在这个位置,因此,第3级调用继续执行后面的代码,执行第二条打印语句,打印“行(递归后)3”。

⑥然后第3级调用结束,控制被传回第2级调用,接着执行第二条打印语句,打印“行(递归后)2”,以此类推。

如果有难理解的地方可能就是从⑤开始,需细细品味。根据书中对每一级调用中变量的变化能更高的理解。每级函数调用都有自己的变量,也就是说每级递归的变量n都属于本级递归私有。如下方表格所示,第1级的n和第2级n不同,所以程序创建了4个单独的变量,每个变量名都是n,但他们的值各不相同。当程序最终返回ud()的第1级调用时,最初的n仍然是它的初值1。

如果上方的解释没有理解,可以死记硬背下面这段话,那么随着练习增多、理解深入,慢慢就会掌握。递归函数中位于递归调用之前的语句,均按被调函数的顺序执行;而递归函数中位于递归调用之后的语句,均按被调函数相反的顺序执行。

对于使用递归解决的常规问题来说,递归的真正价值在归,因为递更像是在描述问题(规模大转化为规模小的过程,即从戒懒一直找到断奶的过程),但递归并非是只做这步转化,而是把规模大的问题分解为规模小的问题后,可以在最小问题解决的基础上逐步往上将剩余的问题自行解决,即归才是解决问题。所以,如果把思考的重点放在归上,应该能更好理解递归(当然这个说法不完全对,有很多特殊问题需要特别对待,但这样说有助于初期对递归的理解)。

其实,从网上看了很多资料之后觉得对递归已经有了很深入的了解,可以用自己理解的方式描述出来,但写着写着却觉得书中的一些解释更确切。于是才明白,书中讲到的很多知识点并不是讲解的不详细,只是自己没有准确、完整的理解而已。

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台