递归：那面照向自己的镜子，为什么会让无数程序员又爱又恨？ - 每日分享

想象一下这个场景：你站在两面相对的镜子中间，镜子里是无限延伸的影像，一层套着一层，永远看不到尽头。大多数人第一次看到这一幕会觉得神奇，但如果我告诉你，这段无限循环的影像，就是程序世界里一个强大到令人战栗的思维工具——递归——你能信吗？

更让人意外的是，递归这个概念，我第一次真正理解它，不是在看代码的时候，而是在厨房里。那天我在切一棵卷心菜，一层层剥开，里面还是一层，直到最后只剩下一个硬芯。那一刻我突然意识到：这不就是递归吗？处理当前这一层，然后把剩下的部分交给同样的方法去处理。

递归的骨架：基本情形 + 递归步骤

递归函数就像一道数学归纳法证明题。你需要两步：第一步，证明n=1时成立（基本情形/递归出口）；第二步，假设n-1时成立，证明n时也成立（递归步骤）。缺了任何一步，这个证明就是废纸。

看一个教科书级的例子——从1加到n：

int sum(int n) {
    if (n == 1) return 1;        // 基本情形：出口
    return n + sum(n - 1);       // 递归步骤：把问题缩小
}

这段代码的运行过程，就像你在一个长长的队伍里想知道总人数。你问前面的人："你前面还有几个？"，他接着往前问，直到队首的人回答"0"，消息再一层层传回来。递推是层层深入，"回归"是层层返回答案。

但递归最迷惑人的地方，不在代码本身，而在那本"备忘录叠叠乐"

计算机执行递归时，靠的是一种叫栈的结构。每次函数调用，当前的状态（参数、局部变量、返回地址）都会被压入栈中，等函数返回时再弹出。

以阶乘为例，fact(3) 的执行过程是这样的：

调用 fact(3) → 需要 fact(2) → 需要 fact(1) → 需要 fact(0)
fact(0) 返回 1，栈弹出
fact(1) 计算 1*1=1，返回，栈弹出
fact(2) 计算 2*1=2，返回，栈弹出
fact(3) 计算 3*2=6，返回，栈弹出

栈就像一叠盘子，你只能从最上面放，也只能从最上面拿。 如果递归没有出口，这叠盘子就会无限增高，直到把内存挤爆——这就是著名的栈溢出（stack overflow）。

有个学生曾经问我："老师，为什么我的程序跑着跑着就崩了？" 我让他检查递归出口，他一脸无辜地说："我写了啊。" 然后我看到了这段代码：

int loop_forever(int n) {
    if (n == 0) return 0;
    return n + loop_forever(n + 1);  // n 越变越大，永远到不了出口
}

递归步骤必须让问题规模越来越小，逼近基本情形，而不是越来越远。 这是新手最容易掉进去的坑。

递归的代价：那只看不见的手

递归代码简洁优雅，但简洁不等于高效。最经典的例子就是斐波那契数列：

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);   // 朴素递归
}

这段代码的时间复杂度是 O(2^n)，指数级爆炸。为什么？因为 fib(5) 需要算 fib(4) 和 fib(3)，而 fib(4) 又需要算 fib(3) 和 fib(2)——fib(3) 被重复计算了两次。n越大，重复计算越恐怖，就像你在图书馆里每次找同一本书都从第一排开始翻。

怎么救？两个方向：

方向一：记忆化。把算过的结果存起来，下次直接取用：

long long memo[100] = {0};
long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fib(n-1) + fib(n-2);
    return memo[n];
}

这就像你做练习册时把难题答案记在笔记本上，下次遇到直接抄。

方向二：彻底抛弃递归，用循环。很多递归能改写成迭代，而且更快、不占栈空间。

递归真正的用武之地：那些天然自带递归结构的问题

有人可能会问："既然递归有这么多坑，为什么还要学它？" 因为有些问题，用递归写是降维打击，用循环写是自找麻烦。

比如统计第n个月兔子的总数。题目是这样的：一对兔子出生后第3个月起每个月都生一对，问第n个月有多少对？这本质上就是斐波那契数列——但如果你用递归加记忆化，代码清晰，逻辑直白；如果你非要用循环硬写，虽然也能写出来，但思维负担重得多。

再看一道更典型的递归题——数的计数。给一个自然数n，可以在它左边加一个不超过n/2的数，加完还能继续加，问能产生多少个新数。比如n=6，可以产生16、26、126、36、136，共5个。

这道题的递归结构非常漂亮：f(n) = 1 + f(1) + f(2) + ... + f(n/2)，其中1代表"不再加了"，后面的f(i)代表在左边加上i之后还能继续扩展的方案数。如果你试图用循环去模拟这个过程，你会发现自己在手动维护一个栈，而且逻辑绕得让人头皮发麻。但用递归，三行代码就写完了：

int count(int n) {
    int total = 1;  // 不加任何数的情况
    for (int i = 1; i <= n/2; i++) {
        total += count(i);  // 左边加i，继续递归
    }
    return total;
}

递归的本质，是把"怎么做"的细节交给函数自己，你只需要定义清楚"什么时候停"和"怎么缩小问题"。

递归的边界感：何时用递归，何时用循环

我给学生一个简单的判断标准：

问题天然有递归结构（树形结构、分治思想、汉诺塔）→ 用递归，代码清晰
递归深度小且无重复计算 → 直接递归，简单直接
有重复计算但深度不大 → 记忆化递归
深度可能很大（超过几千） → 必须用循环，否则栈溢出

记住：递归不是银弹，它是一把精巧的手术刀，用对了地方事半功倍，用错了场合就是灾难。

写在最后

递归是一面镜子，你让它照向自己，它就会无限延伸下去。但真正的高手，知道什么时候该让这面镜子停下来。

如果你正在学习递归，我建议你从这几道题开始练手：汉诺塔（理解递归的递推与回归）、倒序打印数字（理解栈的LIFO特性）、目录递归遍历（理解递归处理嵌套结构的优势）。每道题写完后，问自己三个问题：基本情形是什么？递归步骤怎么缩小问题？这个递归有没有重复计算？

想清楚这三个问题，你就真正掌握了递归的"道"，而不仅仅是"术"。