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

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

        又学到递归，其实结合谭老师《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  Primer Plus》的例子，最开始的时候很不容易理解）：

        运行结果：

        程序分析：

        ①  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。

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

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

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

本文转载自异步社区。

原文链接：

https://www.epubit.com/articleDetails?id=NC7E3EF9233300001EC811DD017DC4180