写在前面递归不是靠背模板学会的刚开始学递归那会我们大多数人脑子里就一个印象——函数自己调用自己。背几个例题、套几个公式好像也会写了。可一到自己动手就卡在递到什么时候停返回值怎么一层层传回来这些地方死活绕不明白。下面这篇复盘是我把函数递归这一讲重新拆了一遍从为什么会有递归讲到两个限制条件再到阶乘、打印每一位、斐波那契三个例子里踩过的坑最后聊聊递归和迭代到底怎么选。不追求把模板背下来只求把大事化小这个思路真正讲透。一、递归是什么为什么说它是自己调用自己递归是学 C 语言函数绕不开的一个话题。说白了递归就是一种解决问题的方法在 C 语言里它就是函数自己调用自己。先看一段史上最简单的递归代码#include stdio.h int main() { printf(hehe\n); main(); // main 函数里又调用了 main 函数 return 0; }这段代码只是用来演示递归基本形式的反面教材——它不是为了解决问题最终会陷入死递归直接栈溢出Stack Overflow。为什么会栈溢出我们先按下不表第三节「递归与迭代」会专门讲。这里先记住一句话递归必须得有结束条件否则就是灾难。1.1 递归的思想把大事化小递归的核心思路就是把一个大而复杂的问题一层层转化成一个跟原问题相似、但规模更小的子问题直到子问题拆不动了递归就结束了。所以递归的思考方式本质上就是大事化小。拆开递归这两个字其实特别有意思递是递推把问题一层层递下去规模越来越小归是回归子问题解决之后再一层层归回来。先递后归合起来才是递归。很多同学只记住了递、忽略了归所以才觉得递归难。1.2 递归的两个限制条件写递归的时候有两个必要条件缺一不可递归得有限制条件——满足这个条件时递归就不再继续每次递归调用之后都要越来越接近这个限制条件。这两条是写递归的铁律第一条保证递归停得下来第二条保证它确实会走到停的那一步。下面三个例子我们会反复体会这两条。二、三个经典例题从看得懂到会写2.1 求 n 的阶乘一个公式引出的递归阶乘factorial是啥一个正整数的阶乘就是所有小于等于它的正整数相乘另外规定0 的阶乘是 1记作n!。题目算 n 的阶乘先不考虑溢出也就是 1~n 的累积相乘。分析思路阶乘的公式大家都熟n! n × (n−1)!。举个具体的5! 5 × 4 × 3 × 2 × 14! 4 × 3 × 2 × 1所以5! 5 × 4!看出门道了吗这就把一个求 n!的大问题转化成了求 (n−1)!的小问题——正是大事化小。当n 0时0 的阶乘是 1其余都能套公式。于是递归公式长这样Fact(n) 1 n 0 时 n * Fact(n-1)n 0 时代码实现假设Fact(n)就是求 n 的阶乘那Fact(n-1)就是求 n-1 的阶乘函数如下int Fact(int n) { if (n 0) return 1; else return n * Fact(n - 1); }完整测试代码#include stdio.h int Fact(int n) { if (n 0) return 1; else return n * Fact(n - 1); } int main() { int n 0; scanf(%d, n); int ret Fact(n); printf(%d\n, ret); return 0; }运行结果这里不考虑 n 太大的情况n 太大存在溢出输入5 输出120画图推演以Fact(5)为例看递和归到底怎么走的【待插入图片】图1Fact(5) 的「递」与「归」推演实线箭头是递向下递归调用虚线箭头是归逐层返回结果。最内层的Fact(0)先返回 1再逐层乘回去最终得到 120。这一步看懂了递归的归也就懂了。2.2 顺序打印整数的每一位先递归还是先打印题目输入一个整数 m按顺序打印它的每一位。比如输入1234输出1 2 3 4输入520输出5 2 0。分析思路这题第一反应是怎么拿到每一位n 是一位数每一位就是 n 自己n 超过一位就得拆。规律很简单1234 % 10得到 41234 / 10得到 123相当于把 4 去掉了再123 % 10得 3再/10去 3……不断%10和/10直到每一位都被拆出来。但这里有个坑这样拆出来的数字顺序是反的先拿到 4、3、2、1。不过换个角度我们反而有了灵感一个数最低位最好拿%10一下就出来了。那我们写个函数Print把Print(1234)拆成两步Print(1234/10)→ 打印 123 的每一位printf(1234%10)→ 打印 4两步做完1234 的每一位就打印完了。以此类推Print(1234) Print(123) printf(4) Print(12) printf(3) Print(1) printf(2) printf(1)直到数字变成一位数不用再拆递归结束。代码实现void Print(int n) { if (n 9) { Print(n / 10); } printf(%d , n % 10); } int main() { int m 0; scanf(%d, m); Print(m); return 0; }运行结果输入1234 输出1 2 3 4这题的关键在于printf写在递归调用之后也就是先递归、后打印。最内层的Print(1)先打印返回时再依次打印 2、3、4顺序正好被纠正过来了。这个顺序很多同学第一次都会写反。画图推演【待插入图片】图2Print(1234) 顺序打印每一位的推演三、递归与迭代别迷恋递归递归是个好东西但和很多技巧一样也容易被误用。就拿求阶乘来说看到公式手一滑就写成递归了。Fact函数确实能出正确结果但递归调用是有运行时开销的C 语言里每次函数调用都要在内存的栈区申请一块空间保存调用期间各种局部变量的值这块空间叫运行时堆栈也就是函数栈帧。函数不返回栈帧就一直占着。递归里每次调用都开新栈帧直到不再递归、开始回归才逐层释放。所以递归层次太深就会大量浪费栈帧甚至栈溢出Stack Overflow。这也正是开头那段main递归会栈溢出的根本原因每次调用都开新栈帧、又永远不返回栈空间很快就被耗光。不想用递归通常就用迭代循环。比如求阶乘同样能 1~n 累积相乘int Fact(int n) { int i 0; int ret 1; for (i 1; i n; i) { ret * i; } return ret; }这段代码照样完成任务而且效率比递归更好。事实上很多问题用递归描述更清晰但迭代实现往往效率更高。当问题复杂到难以用迭代实现时递归的简洁性就能补偿运行时开销。3.1 求第 n 个斐波那契数递归的反面典型再举一个更极端的例子算第 n 个斐波那契数。数列是1, 1, 2, 3, 5, 8, 13, ...递推公式Fib(n) 1 n 2 时 Fib(n-1) Fib(n-2)n 2 时看到这个公式很容易手滑写成递归int Fib(int n) { if (n 2) return 1; else return Fib(n - 1) Fib(n - 2); }测试代码#include stdio.h int Fib(int n) { if (n 2) return 1; else return Fib(n - 1) Fib(n - 2); } int main() { int n 0; scanf(%d, n); int ret Fib(n); printf(%d\n, ret); return 0; }当我们输入n 50结果要等很久很久才出来——这个时间谁都接受不了说明递归写法非常低效。为什么这么慢递归会不断展开展开过程中有大量重复计算而且层次越深冗余越多。写个计数器验证#include stdio.h int count 0; int Fib(int n) { if (n 3) count; // 统计第 3 个斐波那契数被算了几次 if (n 2) return 1; else return Fib(n - 1) Fib(n - 2); } int main() { int n 0; scanf(%d, n); int ret Fib(n); printf(%d\n, ret); printf(\ncount %d\n, count); return 0; }输出输入40 输出102334155 count 39088169看到没算第 40 个斐波那契数光第 3 个数就被重复算了 39088169 次全是冗余计算。所以斐波那契数用递归是非常不明智的。画图推演【待插入图片】图3Fib(5) 递归树——重复计算一目了然图里Fib(3)被算了2 次这才只是 n5。n 越大重复量会指数级膨胀。既然递归不合适就换迭代从前往后、从小到大算。前 2 个数都是 1前两个相加就是第三个int Fib(int n) { int a 1; int b 1; int c 1; while (n 2) { c a b; a b; b c; n--; } return c; }迭代实现效率高出很多。四、总结递归的正确打开方式最后收个尾递归的本质函数自己调用自己核心是大事化小别只记递忘了归。写递归的两条铁律① 有限制条件② 每次调用都更接近限制条件。递归的代价每次调用都开函数栈帧层次太深会栈溢出还可能有大量重复计算。递归 vs 迭代递归简洁易读迭代通常更高效迭代难写时递归的简洁能补回运行时开销。一句话收尾递归虽好可别迷恋适可而止就好。拓展学习下面两个经典问题都能用递归漂亮地解决感兴趣可以研究青蛙跳台阶问题汉诺塔问题