C / C++ / 系统课时

用递归解决重复子问题

用递归解决重复子问题

递归让一个函数通过调用自身,把较大的问题逐步转换为结构相同的较小问题。本节用阶乘程序观察递归条件、终止条件以及调用逐层返回的过程,并说明什么时候递归会失去控制。

学习目标

  • 识别递归函数中的终止条件和递归步骤
  • 理解函数调用逐层进入、再按相反顺序返回的过程
  • 避免缺少终止条件和递归过深等常见问题

递归必须同时具备两个部分

递归不是简单地“函数调用自己”。一个可工作的递归函数通常需要两部分:终止条件直接给出最小问题的结果,递归步骤则把当前问题缩小后再次调用自身。

以非负整数阶乘为例,n!n! 可以写成:当 nn 为 0 或 1 时结果为 1;当 n>1n > 1 时,结果是 n×(n−1)!n \times (n-1)!。每次调用都让参数减少 1,因此最终能够到达终止条件。

用函数计算阶乘

下面的完整程序计算 5!。factorial 先判断是否已经到达最小问题,否则把 n - 1 交给下一层调用处理。

c
#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;
}

预期输出

text
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! 已超出范围。递归是否正确与整数是否溢出是两个不同问题,实际程序必须同时检查输入范围。

理解递归时最重要的不是背写法,而是始终追踪三个问题:当前调用处理什么输入、下一次调用是否让问题变小、最深一层返回后每一层还要完成什么操作。只要这三点明确,递归的进入与返回过程就能被准确推导。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用递归解决重复子问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通