递归算法

1. 基本概念

核心定义：递归是一种通过函数调用自身来解决问题的算法策略。它将一个复杂的大问题转化为一个或多个与原问题结构相同、但规模更小的子问题来求解。
核心思想：“大事化小，小事化了”。
- 如果问题很大，就把它拆成小问题（递推）。
- 如果问题很小（到了边界），就直接解决（回归）。
两大要素：
- 基准情况：递归的“出口”，即最小的、可以直接求解的问题（防止死循环）。
- 递归步骤：将大问题拆解，并调用自身去解决子问题。

2. 费曼理解

用最简单的语言解释给“小白”听：

想象你在电影院里，想知道自己是第几排，但太黑了看不清。

递归（问人）：你问前一排的人：“你是第几排？”

前一排的人也不知道，他只好问他前一排的人。

这个问题一直传到了第一排的人。

基准情况（出口）：第一排的人说：“我是第 1 排。”

回归（传话）：

第二排的人听到后，说：“我是第 1+1=2 排。”

第三排的人听到后，说：“我是第 2+1=3 排。”

最后传回给你，你知道了自己是第 N 排。

3. 算法核心步骤

递归算法的执行过程可以严格拆解为以下 4 个标准步骤。这是编写递归代码的“万能公式”。

表格

步骤序号	步骤名称	核心操作描述	关键问题
Step 1	定义功能	明确这个递归函数到底是干嘛的。输入是什么？返回什么？（不要跳进细节，要宏观理解）。	“这个函数 f(n) 代表什么意义？”
Step 2	寻找基准	找出最简单、最小的情况（边界条件），直接返回结果，不再递归。	“什么时候可以停止递归？”
Step 3	拆解问题	将当前问题拆解为“当前步操作” + “子问题”。假设子问题已经解决，利用子问题的结果来构建当前问题的解。	“大问题 f(n) 和小问题 f(n-1) 有什么关系？”
Step 4	调用与返回	代码实现：调用自身函数 `func(sub_problem)`，并将结果返回给上层。	“如何把子结果组合成最终结果？”

4. 步骤实战演示：计算阶乘

为了让你更直观地理解上述 4 步，我们用计算 n 的阶乘 来演示：

题目：计算 n!=n×(n−1)×⋯×1n!=n×(n−1)×⋯×1 。

定义功能：
- 函数 factorial(n) 的功能是：返回数字 n 的阶乘值。
寻找基准：
- 最小的情况是 1!。
- 我们知道 1!=1 。所以当 n == 1 时，直接返回 1。
拆解问题：
- 数学公式： n!=n×(n−1)! 。
- 这意味着：要算 n 的阶乘，只需要算出 n-1 的阶乘，然后乘以 n 即可。
- 这里假设 factorial(n-1) 已经帮我们算好了结果。
调用与返回：
- 返回 n * factorial(n-1)。

代码映射：

def factorial(n):
    # Step 2: 寻找基准 (出口)
    if n == 1:
        return 1
    
    # Step 3 & 4: 拆解问题 & 调用返回
    # 假设 factorial(n-1) 已经算出了结果，直接拿来用
    return n * factorial(n - 1)

5. 进阶技巧：递归的“坑”与优化

在编写递归时，除了上述步骤，还需要注意以下几点：

栈溢出：
- 递归本质上是函数调用栈。如果递归层数太深（例如 n = 10000），会导致内存溢出。
- 解决：确保基准情况正确，或者改用“迭代（循环）”写法。
重复计算：
- 在斐波那契数列等场景中，递归会重复计算大量相同的子问题（例如算 f(5) 需要算 f(3)，算 f(4) 也要算 f(3)）。
- 解决：使用记忆化搜索，用一个数组或哈希表把算过的结果存起来，下次直接用。

6. 总结：递归的“哲学”

人脑的限制：人类的大脑不擅长处理多层嵌套的循环，但非常擅长处理单层逻辑。
递归的精髓：相信函数。
- 当你写 factorial(n-1) 时，不要去想它里面是怎么算的，不要去想栈是怎么变化的。
- 你要无条件相信 factorial(n-1) 能正确返回结果，你只需要关注如何利用这个结果来完成 factorial(n)。
- 这种“宏观思维”是掌握递归的关键。

7.相关

TABLE without id file.link AS "题目名称", 数据结构,date
FROM #LeetCode 
WHERE contains(数据结构, "递归")
SORT file.mtime DESC