大家好啊这里是土豆的博客一个正在努力学习技术的大学生。上一篇和大家聊了递归的四步法并且用阶乘那个例子带着大家完整走了一遍。如果还没看上一篇的话建议先去翻一翻不然这篇直接看可能会有点懵。那今天这篇咱们就继续用四步法来做两道练习题。这两道题看起来很像但有一个关键的区别——把“缩小问题”和“还原回去”这两步的顺序换一下结果就完全不一样了。我觉得这个对比挺好的应该能帮你更深刻地理解递归的执行顺序。好了废话不多说咱们直接开始。案例1倒序输出一个数字的每一位题目输入一个正整数用递归的方式把它的每一位数字倒序输出。比如输入 1234输出 4 3 2 1。不考虑负数咱们还是用四步法一步一步来分析。第一步明白这个函数用来干什么这个函数的功能很直白接收一个整数 n在屏幕上倒序打印它的每一位。// 输入一个整数 n倒序打印它的每一位数字 void printReverse(int n) { // 先不用管里面的实现 }注意返回值是 void因为这个函数只负责打印不需要返回计算结果。第二步递归得确定终止条件这里我觉得需要你先思考下当n 等于多少的时候我们可以直接处理既然咱们题目的要求是倒序输出每一位数字那对于个位数来说是不是就输出就可以了呢所以当n 只有一位数的时候也就是 n 10直接把它打印出来就行了不需要再递归。void printReverse(int n) { // 终止条件n 是一位数时直接打印 if (n 10) { cout n ; return; } }第三步想办法把问题“变小一号”这一步我觉得咱们可以举个例子那这里有引入了一个新的问题就是咱们在举例子的时候不能举太极端的例子就比如个位数要不然看不出来要怎么把问题变小所以在这里咱们得尽量弄一个比较普适的例子所以就拿1234来说大家先暂停思考下好好想想这块内容首先1234 怎么变小是不是去掉最后一位就行了。所以怎么去呢是不是很快就能想到用n / 101234 / 10 123这样就得到去掉最后一位的数字了既然1234变小了那我们毕竟采用递归的思想所以应该继续调用printReverse(123也就是调用printReverse(n / 10)。所以在第三步咱们明确了这里的代码要写调用 printReverse(n / 10)。第四步怎么把缩小后的问题还原回去咱们先不用管里面具体的实现逻辑就先假设printReverse(123)已经帮我把 123 倒序打印好了。那现在我要倒序打印 1234要怎么利用这个结果呢1234 的最后一位是 4所以我们肯定得有个输出是不是所以有cout 4 ;那咱们怎么得到4呢是不是想到了%这个符号咱们可以通过1234%10来得到所以这里就是cout n%10 ;现在重点来了咱们是先打印再调用呢还是是先调用后打印呢这两个顺序看起来差不多但结果完全不一样。我们先分析一下逻辑题目要求是倒序输出也就是从最后一位开始打印。对于 1234 来说最后一位是 4,也就是 n % 10所以4必须第一个被打印。那怎么保证 4 第一个打印呢很简单在调用递归之前先把4打印出来。这样屏幕上先显示 4然后递归再去处理剩下的 123递归内部会依次打印 3、2、1整个顺序就变成了 4 3 2 1。所以我们的选择是先打印 n % 10再调用 printReverse(n / 10)。把这一步写进代码结合四步 就是void printReverse(int n) { // 第二步终止条件 if (n 10) { cout n ; return; } // 第四步先打印 第三步再缩小 cout n % 10 ; printReverse(n / 10); }到这里这个题其实就解完了。但你有没有想过——如果反过来先调用再打印会发生什么这个问题我当时也好奇过所以专门试了一下结果发现输出完全变了。具体怎么回事咱们接着往下看。重点来了调换一下顺序会怎样咱们先来看下代码void printReverse(int n) { if (n 10) { cout n ; return; } printReverse(n / 10); // 先缩小 cout n % 10 ; // 后打印 }结果是什么呢答案是1 2 3 4——变成正序输出了这样我来手画个结构图咱们一起来看看因为如果咱们先递归程序会一路扎到最深处此时n1所以程序先打印 1然后返回上一层打印 2再返回上一层打印 3……最后打印 4。所以第三步缩小和第四步还原的先后顺序决定了是从大到小处理还是从小到大处理。对本题来说有所以确定这两步骤的顺序也是十分关键的。案例2计算一个数字的各位之和题目输入一个正整数用递归计算它各位数字之和。比如输入 123返回 1236。建议大家先暂停自己用四步法想一想再看分析。第一步明白这个函数用来干什么// 输入一个整数 n返回它各位数字之和 int sumDigits(int n) { // 先不用管里面的实现 }第二步递归得确定终止条件当 n 10 时它只有一位所以各位数字之和就是它自己。int sumDigits(int n) { //终止条件当n为个位数的时候也就是n10 if (n 10) { return n; } }第三步想办法把问题“变小一号”依旧咱们先举个例子123和倒序输出一样用 n / 10去掉最后一位问题从 123 缩小成 12。和上一道题一样的思路也就是sumDigits(12)即sumDigits(n / 10)第四步怎么把缩小后的问题还原回去拿到sumDigits(12)的结果也就是 123怎么得到sumDigits(123) 的结果123 的最后一位是n%10也就是 3。所以把它加上去就行了3 3 6。所以还原方式是n % 10 sumDigits(n / 10)完整代码int sumDigits(int n) { if (n 10) { return n; } return (n % 10) sumDigits(n / 10); }最后调用 sumDigits(123)返回 6。咱们看这道题和倒序输出题目的结构几乎一模一样只是把“打印”换成了“加法”。所以这也能体现四步法的好处套路是很固定的具体操作换一下就行。一个比较容易犯的问题终止条件没写严谨刚学递归的时候最常犯的错误就是第二步终止条件考虑不周全。就比如倒序输出那个例子如果没有写 if (n 10) 这个终止条件void printReverse(int n) { cout n % 10 ; printReverse(n / 10); }对于 n 1234程序会一直执行1234 → 123 → 12 → 1 → 0 → 0 → 0……无限循环直到程序崩溃。所以后来我养成一个习惯写完递归代码之后用几个例子在脑子里跑一遍检查终止条件有没有写全。写在最后递归这个东西刚开始接触确实会觉得别扭但我觉得只要多练几道套路其实就那么几个。今天这篇咱们用四步法做了两道练习题还发现了第三步缩小和第四步还原的顺序一换结果就完全不一样。同时我也希望这两个案例能帮你更深入地理解递归的执行顺序。如果你学到后面就会发现递归有时候会重复计算很多次同样的东西比如斐波那契数列这时候可以用一个数组把算过的结果存起来这个技巧叫“记忆化搜索”等咱们以后聊到数组的时候再详细展开之后我会继续分享一些相关的C知识入门学习经验的。如果这篇文章对你有帮助麻烦点赞、关注和收藏吧谢谢有什么问题或者想法欢迎在评论区留言我们一起交流我们下篇见