C / C++ / 系统课时
用递归解决重复子问题
用递归解决重复子问题
递归让一个函数通过调用自身,把较大的问题逐步转换为结构相同的较小问题。本节用阶乘程序观察递归条件、终止条件以及调用逐层返回的过程,并说明什么时候递归会失去控制。
学习目标
- 识别递归函数中的终止条件和递归步骤
- 理解函数调用逐层进入、再按相反顺序返回的过程
- 避免缺少终止条件和递归过深等常见问题
递归必须同时具备两个部分
递归不是简单地“函数调用自己”。一个可工作的递归函数通常需要两部分:终止条件直接给出最小问题的结果,递归步骤则把当前问题缩小后再次调用自身。
以非负整数阶乘为例, 可以写成:当 为 0 或 1 时结果为 1;当 时,结果是 。每次调用都让参数减少 1,因此最终能够到达终止条件。
用函数计算阶乘
下面的完整程序计算 5!。factorial 先判断是否已经到达最小问题,否则把 n - 1 交给下一层调用处理。
#include <stdio.h>
unsigned long long factorial(unsigned int n)
{
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
int main(void)
{
unsigned int n = 5;
unsigned long long result = factorial(n);
printf("%u! = %llu\n", n, result);
return 0;
}预期输出
5! = 120当 factorial(5) 执行到 factorial(4) 时,第一层并没有立刻得到最终结果,而是等待下一层返回。直到 factorial(1) 直接返回 1,前面的调用才开始依次完成乘法。
调用为什么会逐层返回
对于 factorial(5),进入阶段依次形成 factorial(5)、factorial(4)、factorial(3)、factorial(2) 和 factorial(1)。到达终止条件后,返回方向相反:先得到 1,再计算 2 × 1、3 × 2、4 × 6,最后得到 5 × 24。
每一层调用都必须保留自己的参数和尚未完成的执行位置,因此递归会占用调用栈空间。它不是“一次调用反复修改同一个 n”,而是同时存在多层彼此独立的函数调用。

终止条件错误会发生什么
如果递归步骤不能稳定接近终止条件,函数就可能不断调用自身。例如把递归调用误写成 factorial(n),参数没有变小,终止条件永远无法从 n > 1 的状态到达。
持续创建新的函数调用会不断消耗调用栈,最终可能导致栈空间耗尽并使程序异常终止。因此检查递归函数时,不能只确认“有一个 if”,还要确认每次递归都朝着这个条件推进。
什么时候适合使用递归
当问题天然由相同结构的子问题组成时,递归往往能直接表达思路,例如目录遍历、树结构处理、分治算法等。对于阶乘这类简单线性计算,循环同样可以完成任务,而且不会为每一步额外创建函数调用。
还要注意结果本身的数据范围。阶乘增长很快,在常见的 64 位 unsigned long long 实现中,20! 仍可表示,而 21! 已超出范围。递归是否正确与整数是否溢出是两个不同问题,实际程序必须同时检查输入范围。
理解递归时最重要的不是背写法,而是始终追踪三个问题:当前调用处理什么输入、下一次调用是否让问题变小、最深一层返回后每一层还要完成什么操作。只要这三点明确,递归的进入与返回过程就能被准确推导。