递归函数：自己调用自己的神奇技巧

你有没有想过，一个函数竟然可以“自己调用自己”？听起来像“镜子里的镜子”，一层叠一层，直到某个“终点”才停住。这种技巧在编程里就叫递归。递归特别擅长解决那种“大问题可以拆成小问题，小问题和原问题长得一模一样”的情况。比如：算阶乘、数楼梯、遍历文件夹等。

什么是递归？

想象你站在两面对着的镜子中间——镜子里有镜子里有镜子里……无穷无尽。但编程里的递归不能永远下去，它必须有一个“停下来的条件”，否则程序就会崩溃（像镜子里的镜子永远没完）。递归的套路是：

把大问题拆成更小的同类问题（比如：求 5! = 5 × 4!）
直到问题小到可以直接解决（比如：0! = 1）
然后层层返回结果（像俄罗斯套娃打开后，再一个个合上）

那个“直接解决”的条件叫作基线条件（也叫停止条件）。没有它，递归就变成了“无限套娃”。

第一个例子：计算阶乘

阶乘是递归的经典入门题：5! = 5 × 4 × 3 × 2 × 1。用递归的思路：

如果 n == 0，那么 0! = 1（基线条件）
否则 n! = n × (n-1)!（递归）

下面是完整代码：

#include <iostream>
using namespace std;

int factorial(int n) {
    if (n == 0) {           // 基线条件：0的阶乘等于1
        return 1;
    } else {
        return n * factorial(n - 1);  // 递归调用：n! = n * (n-1)!
    }
}

int main() {
    cout << "5! = " << factorial(5) << endl;  // 输出 120
    return 0;
}

执行过程：当 factorial(5) 被调用时，它发现 n!=0，于是计算 5 * factorial(4)。factorial(4) 又计算 4 * factorial(3)……这样一层层往下，直到 factorial(0) 直接返回1。然后结果像多米诺骨牌一样往回推：
factorial(1) = 1 * 1 = 1
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24
factorial(5) = 5 * 24 = 120

就像你拆俄罗斯套娃：外面最大的娃娃，里面套着一个稍小的，再里面还有更小的……直到遇到一个实心的（基线条件），然后从最小的开始，一层层把外面的合上，最后得到完整的套娃。

生活中的递归例子

例子1：排队数人数

老师说：“请报出你前面有几个人。”你只知道前面的人比自己高，看不见队伍尽头。怎么办？你可以问前面的同学：“你前面有几个人？”他也不知道，就继续往前问，直到第一个人（基线条件：前面没人），他回答“0”。然后消息传回来：第一个人+1 = 1，第二个人+1 = 2……一直传到你这里，你就知道前面有几个人了。

这就是递归——把问题“我前面有几个人”变成“我前面的人前面有几个人”，直到不用再问。

例子2：分糖果

妈妈要把一堆糖果分给孩子们，规则是：每个孩子拿一颗，然后把剩下的糖果继续分给下一个孩子，直到糖果分完（基线条件：没有糖果了）。这个“不断分糖果直到分完”的过程，也像递归。

递归的执行过程：栈的秘密

每次函数调用自己，计算机都会在内存的“栈”上留下一份记录，包括参数、局部变量和返回地址。当基线条件满足时，开始一层层“弹出”记录，返回结果。调用太深（比如求10000!），栈可能会被撑爆，这叫栈溢出（就好像你往一个杯子里放太多层硬币，最后硬币溢出来）。

第二个例子：斐波那契数列

斐波那契数列就是：第0项=0，第1项=1，从第2项开始，每一项等于前两项之和。即：

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

用递归写非常直观：

#include <iostream>
using namespace std;

int fib(int n) {
    if (n == 0) {           // 基线条件1：第0项是0
        return 0;
    }
    if (n == 1) {           // 基线条件2：第1项是1
        return 1;
    }
    return fib(n - 1) + fib(n - 2);  // 递归：第n项 = 前两项之和
}

int main() {
    cout << "第10个斐波那契数是：" << fib(10) << endl;  // 输出55
    return 0;
}

注意：这个递归效率很低，因为很多值重复计算（比如 fib(5) 会调用 fib(4) 和 fib(3)，而 fib(4) 又会调用 fib(3) 和 fib(2)……），但作为理解递归思想非常合适。

新手容易犯的错误

错误1：忘记写基线条件

int badFactorial(int n) {
    return n * badFactorial(n - 1);  // 没有停止条件，无限递归！
}

这会导致程序崩溃（栈溢出）。

错误2：基线条件写错（比如写成了 `if (n == 1)` 却传入 `n=0`）

int wrongFactorial(int n) {
    if (n == 1) return 1;   // 如果输入0，永远不会进入该条件，无限递归
    return n * wrongFactorial(n - 1);
}

调用 wrongFactorial(0) 时，0!=1，所以永远不会停，直到溢出。

#include <iostream>
using namespace std;

int sum(int n) {
    if (n == 0) {           // 基线条件：0元总和就是0
        return 0;
    }
    return n + sum(n - 1);  // 递归：n + 前n-1元的总和
}

int main() {
    int totalMoney = sum(100);  // 从1存到100元
    cout << "1+2+...+100 = " << totalMoney << endl;  // 输出5050
    return 0;
}

这个递归的思路：总钱数 = 第n元 + 前n-1元的总和。就好比你存钱：先放进第n元，然后心里想“我之前已经存了前n-1元”，继续想下去，直到n=0（还没开始存钱）。

练练手（经典题目）

用递归计算n的阶乘（已学过，自己再敲一遍）
用递归打印1到n（提示：先递归打印前n-1个数，再打印n）
用递归求数组的最大值（想想怎么拆分成更小的数组）
汉诺塔问题：有三个柱子，把n个盘子从A移到C，一次只能移一个，且大不能压小。递归思路很优雅。

递归函数