递归是一种编程技术，函数通过调用自身来解决问题。它通常包含基准条件（终止递归）和递归条件（继续调用自身）。#

什么是递归？#

把一个大问题拆解成结构相同但规模更小的子问题，直到触及一个可以直接回答的边界条件（基准情形）。 简单来说：

• 递归就像查一个词的解释，发现解释里又有一个不认识的词，于是又去查那个词，直到找到一个不需要查其他词就能懂的解释为止。

二、递归三要素#

1. 基准条件（Base Case） 递归的”紧急出口”。当问题简化到最简形式时，直接返回结果而不再自我调用。

1
def factorial(n: int) -> int:
2
    # 基准条件：最小子问题，已知答案
3
    if n <= 1:
4
        return 1  # 0! = 1, 1! = 1

关键点：基准条件必须可达，否则会导致无限递归和溢出。 2. 递归条件（Recursive Case） 将问题分解为更小的同类子问题，并向其委托求解。

1
def factorial(n: int) -> int:
2
    if n <= 1:
3
        return 1
4

5
    # 递归条件：缩小问题规模，委托给factorial(n-1)
6
    return n * factorial(n - 1)

3. 回归过程（Unwinding） 子问题解决后，逐层返回并组合结果，最终得到原问题的答案。

1
# 以 factorial(4) 为例的回归过程演示
2
factorial(4)  # 返回 4 * factorial(3)
3
└── factorial(3)  # 返回 3 * factorial(2)
4
    └── factorial(2)  # 返回 2 * factorial(1)
5
        └── factorial(1)  # 基准：返回 1
6
        # 开始回归：
7
        └── 返回 2 * 1 = 2
8
    └── 返回 3 * 2 = 6
9
└── 返回 4 * 6 = 24  # 最终结果

1
def countdown(n):
2
    # 1. 停止条件（到家了，不用再走了）
3
    if n == 0:
4
        print("时间到！")
5
        return
6

7
    # 2. 先做事（输出当前数字）
8
    print(n)
9

10
    # 3. 然后让下一个同学继续（调用自己）
11
    countdown(n - 1)
12

13
countdown(3)# 调用：countdown(3)

1
total = 0
2
for i in range(1, 6):   # 1 2 3 4 5
3
    total += i
4
print(total)            # 15

1
def total(n):
2
    if n == 1:          # 最小娃
3
        return 1
4
    return n + total(n-1)  # 先问下层，再回头加
5

6
print(total(5))         # 15

1
def factorial(n):
2
    if n == 1: return 1  # 基准：最小的娃
3
    return n * factorial(n-1)  # 套娃

graph TD
    A["factorial(4)"] -->|"4 × ?"| B["factorial(3)"]
    B -->|"3 × ?"| C["factorial(2)"]
    C -->|"2 × ?"| D["factorial(1)"]
    
    %% 基准情形：返回 1
    D -->|"返回 1"| D1["1"]
    
    %% 回归阶段：层层返回并相乘
    D1 -.->|"2 × 1"| C1["2"]
    C1 -.->|"3 × 2"| B1["6"]
    B1 -.->|"4 × 6"| A1["24"]
    
    %% 最终结果说明
    A1 -.->|"最终结果"| R["递归完成<br/>factorial(4) = 24"]
    
    %% 样式定义（使用非保留字名称）
    classDef c1 fill:#ffe599,stroke:#333,stroke-width:2px;
    classDef c2 fill:#9ccff9,stroke:#333,stroke-width:2px;
    classDef c3 fill:#d9ead3,stroke:#333,stroke-width:2px;
    classDef c4 fill:#fff,stroke:#333,stroke-width:1px;
    
    %% 应用样式
    class A,B,C,D c1;
    class D1,C1,B1,A1 c2;
    class D c3;
    class R c4;

经典案例介绍#

斐波那契数列 说到递归思想，总是离不开斐波那契数列 斐波那契数列（Fibonacci sequence），又称黄金分割数列，是一个在数学和自然界中广泛出现的数列。这个数列由意大利数学家列奥纳多·斐波那契（Leonardo Fibonacci）在1202年提出，因此得名。 定义 斐波那契数列的定义如下：

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2)，对于 n ≥ 2

数列的前几项 根据上述定义，斐波那契数列的前几项是： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … 简单来说，就是： 从 0 和 1 开始，后面的每个数，都是前两个数相加。 数列： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34…

所以，这里就很适合用递归思想了 于是，我们可以得出：

1
def fib(n):
2
    """返回第 n 个斐波那契数，从 0 开始计数。"""
3
    if n < 2:          # ① 最最简单的情况
4
        return n
5
    return fib(n-1) + fib(n-2)  # ② 自己调用自己 → 这就是“递归”
6

7
# 测试
8
for i in range(8):
9
    print(f'fib({i}) = {fib(i)}')

运行结果

1
fib(0) = 0
2
fib(1) = 1
3
fib(2) = 1
4
fib(3) = 2
5
fib(4) = 3
6
fib(5) = 5
7
fib(6) = 8
8
fib(7) = 13

总结#

核心本质 递归不是循环，而是信任的委托链： “我（n层）不知道完整答案，但我知道n-1层会算，我只需要在他结果上+1就行” 每一层只做两件事：

• 判断：“是不是最小的问题了？“（基准检查）
• 委托：“不是？那我处理一点点，剩下的交给下一层” 为什么必须回头？ 因为下一层的答案依赖于更下一层，必须等到最底层答案返回后，上一层才能计算出结果。就像你不能在拿到子结果前就拼出最终结果。 一句话原理：递归 = 往下问到头，往上答回来。