C++ 递归函数

在 C++ 中，递归函数（recursive function）指的是一个函数在自己的函数体内部又调用了自己。

很多初学的小伙伴第一次看到 “函数自己调用自己” 时，容易觉得有点绕。其实递归的思路很直观：我们让函数不断调用自身，把一个大问题拆解成规律相同的小问题，直到算出最后一步的明确结果，再把结果逐层返回回来。

C++ 递归函数语法

要让一个递归函数正常工作，我们不能只写一句 “自己调用自己”，否则程序就会没完没了地调用下去。一个合法的递归函数通常具有以下基本结构。

语法：

返回类型 函数名(参数列表) {
    if (终止条件) {
        return 终止结果;
    }
    ……
    return 函数名(缩小后的参数);
}

说明：

从上面的结构可以看出，编写递归函数必须同时具备以下 2 个条件，缺一不可：

• 终止条件（退出条件）：负责告诉函数 “算到这里就不要再往下调用自己了”，为整个调用链提供一个明确的出口。
• 递归推进：每次调用自身时，我们都必须把当前问题的规模缩小，比如让参数从 n 变成 n - 1，逐步往终止条件靠近。

递归函数的执行过程

为了方便看清递归内部的每一步变化，我们先拿最简单的 “计算 1 到 n 的整数累加和” 来举例。虽然在实际开发中求和直接使用循环即可，但这个例子非常适合用来推演递归的执行路线。

观察求和规律可以发现：计算 1 到 4 的和，其实就是 4 加上 “1 到 3 的和”。而 1 到 3 的和，又是 3 加上 “1 到 2 的和”。以此类推，计算 1 到 n 的和，可以拆解为 n 加上 “1 到 n - 1 的和”，直到 n 减小到 1 时直接返回 1。

示例 1：递归计算 1 到 n 的和

#include <iostream>

// 计算 1 到 n 的累加和
int sumUpTo(int n) {
    if (n <= 1) {
        return 1;
    }
    return n + sumUpTo(n - 1);
}

int main() {
    std::cout << "1 到 4 的和：" << sumUpTo(4) << '\n';
    return 0;
}

运行结果如下。

1 到 4 的和：10

分析：

在这个例子中，sumUpTo(int n) 在函数体内部再次调用了 sumUpTo(n - 1)，构成了递归调用。其中 n <= 1 是退出条件，满足时直接返回 1。当 n 大于 1 时，则执行 return n + sumUpTo(n - 1); 继续往下拆解。

初学者最容易卡壳的地方，是想不通调用 sumUpTo(4) 后底层是怎么一步步算出结果的。其实整个执行过程分为 “逐层递推” 和 “逐层返回” 两个阶段。首先是逐层递推，外层调用需要等待内层调用的结果，于是层层往下拆解：

sumUpTo(4) -> 4 + sumUpTo(3)
sumUpTo(3) -> 3 + sumUpTo(2)
sumUpTo(2) -> 2 + sumUpTo(1)
sumUpTo(1) -> 1

当调用到最里层的 sumUpTo(1) 时，满足 n <= 1 的退出条件直接拿到结果 1。随后进入逐层返回阶段，程序从最里层开始把结果一层层往回代入相加：

sumUpTo(1) -> 1
sumUpTo(2) -> 2 + 1 = 3
sumUpTo(3) -> 3 + 3 = 6
sumUpTo(4) -> 4 + 6 = 10

建议小伙伴们拿纸笔把上面这两个阶段推演一遍，只要你亲手顺下来一次，就能彻底理清递归的执行路线了。

每一层参数的名字都叫 n，当里层变成 3、2、1 时，外层原来的 4 不会被覆盖掉吗？其实不会。形参属于局部变量，每次调用函数都会开辟一块独立的内存空间来保存当前这一层自己的 n，各层之间互不干扰。

反过来，如果在编写时漏掉了 if (n <= 1) 这个退出条件，只写一句 return n + sumUpTo(n - 1);，会发生什么呢？此时参数 n 会从 4 一直减到 0、-1、-2 无休止地调用下去，直到耗尽栈空间引发崩溃。

递归函数的典型应用

弄清楚递归函数的执行过程后，下面我们再来看两个经典的递归应用：计算阶乘与求斐波那契数列。

1. 计算阶乘

在数学中，正整数 n 的阶乘（记作 n!）表示从 1 到 n 所有连续整数的乘积，例如 5! = 5 × 4 × 3 × 2 × 1 = 120，并且数学上规定 0! = 1、1! = 1。

观察阶乘的定义可以发现，当 n 大于 1 时，n! 其实就等于 n × (n - 1)!。我们把前面求和示例中的加号 + 换成乘号 *，就能编写函数算出整数 n 的阶乘。

示例 2：使用递归计算阶乘

#include <iostream>

int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main() {
    std::cout << "5 的阶乘：" << factorial(5) << '\n';
    return 0;
}

运行结果如下。

5 的阶乘：120

分析：

return n * factorial(n - 1); 表示 n 的阶乘等于 n 乘以 n - 1 的阶乘，而 if (n <= 1) 同时覆盖了传入 1 和 0 时返回 1 的边界，递推后再逐层相乘得出 120。

这里提醒大家，阶乘的结果增长非常快，比如 13! 就已经超出了 int 类型的最大取值范围。如果需要计算较大数字的阶乘，记得把函数的返回类型改成 long long，避免发生数据溢出。

2. 斐波那契数列

斐波那契数列（Fibonacci sequence）又称 “黄金分割数列” 或 “兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34……。

这个数列的规律非常明显：第 0 项是 0，第 1 项是 1。从第 2 项开始，每一项都等于它前面两项之和，也就是满足 fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2)。下面我们就使用递归函数来输出该数列的前 10 项。

示例 3：输出斐波那契数列前 10 项

#include <iostream>

// 计算斐波那契数列的第 n 项
int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    for (int i = 0; i < 10; i++) {
        std::cout << fibonacci(i) << ' ';
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

0 1 1 2 3 5 8 13 21 34

分析：

在这个例子中，fibonacci() 的退出条件设为了 n <= 1：当 n 为 0 时直接返回 0，当 n 为 1 时直接返回 1。当 n 大于 1 时，则同时发起两次递归调用，返回前两项 fibonacci(n - 1) 与 fibonacci(n - 2) 之和。

虽然这段代码写起来简短直观，但如果我们把计算 fibonacci(5) 的调用关系拆开，就会发现一个明显的性能问题：

fibonacci(5) -> fibonacci(4) + fibonacci(3)
fibonacci(4) -> fibonacci(3) + fibonacci(2)
fibonacci(3) -> fibonacci(2) + fibonacci(1)

求 fibonacci(5) 时要算一次 fibonacci(3)，求 fibonacci(4) 时又会把它重算一遍，更底层的项也会被反复计算。当 n 较小时影响不大，一旦 n 变大到 40 以上程序就会明显变慢，此时改用循环递推计算斐波那契数列效率会高得多。

递归函数的优缺点与选型建议

对于递归函数来说，它主要有以下 2 个优点：

• 代码简短清晰：遇到具有递推规律或分层嵌套结构的问题时，使用递归写出来的代码往往比多层循环更加紧凑好懂。
• 问题拆解直观：直接把大问题拆解为规模更小的同类子问题，贴合数学公式或问题本身的自然描述。

同时，递归函数也有以下 2 个明显的缺点：

• 内存开销较大：外层函数调用内层函数后还没结束，必须占用内存中的 “调用栈” 空间来保存当前这一层的数据。如果递归层数过深，就会引发栈溢出报错。
• 可能产生重复计算：就像前面的斐波那契数列一样，一次调用里包含多次递归分支时，容易对相同的子问题反复计算，降低运行效率。

因此在实际开发中，遇到简单的计数、累加求和、求阶乘或遍历数组等任务时，建议小伙伴们优先使用 for 循环或 while 循环。循环不仅执行速度更快，也不会额外占用调用栈空间。

只有当问题本身天然适合分层拆解时，比如遍历多层嵌套的文件夹、树结构遍历或快速排序，使用递归才会让代码简单很多。