Python 递归入门#

学习目标#

理解递归的核心思想：自己调用自己
掌握递归三要素：终止条件、递归关系、递归调用
能通过递归解决阶乘和斐波那契数列等经典问题
了解递归的优缺点，知道什么时候该用、什么时候不该用

一、什么是递归？#

想象你站在两面相对的镜子之间，会看到无穷无尽的镜像。这就是递归的直观感受：一个函数在内部调用它自己。

flowchart TD
    A["n = 5<br/>调用 fac(5)"] --> B["n = 4<br/>调用 fac(4)"]
    B --> C["n = 3<br/>调用 fac(3)"]
    C --> D["n = 2<br/>调用 fac(2)"]
    D --> E["n = 1<br/>碰到终止条件！"]
    E --> F["返回 1"]
    F --> G["返回 2"]
    G --> H["返回 6"]
    H --> I["返回 24"]
    I --> J["返回 120"]

    style A fill:#ffe599,stroke:#333
    style E fill:#d9ead3,stroke:#333
    style J fill:#9ccff9,stroke:#333

二、递归的三要素#

写对递归，必须把下面三件事想清楚：

要素	含义	以阶乘为例
① 终止条件（base case）	什么时候停下来？	`n == 1` 时返回 `1`
② 递归关系（recurrence）	大问题和小问题是什么关系？	`fac(n) = n × fac(n-1)`
③ 递归调用（recursive call）	怎么用更小的参数调用自己？	`return n * fac(n-1)`

递归，到底”递”了什么，“归”了什么？#

把”递归”两个字拆开看：

递：把问题传递下去—— “我算不出来，但我可以把问题缩小一号，交给下一个我”
归：把答案归还上来—— “最底层的我算出来了，一层一层把结果传回去”

打个比方：你排在一列长队的最后面，想知道自己是第几个人。你不会从头数，而是——

拍前面人的肩膀：“嘿，你是第几个？” 前面的人也不知道，他又拍更前面的人…… 一直传到第一个人：“我是第 1 个！” 然后答案一路往回传：“我是第 2 个” → “我是第 3 个” → …… → “你是第 10 个！”

flowchart LR
    A["第10人<br/>'我是第几个？'"] -->|"递：往前问"| B["第9人<br/>'我是第几个？'"]
    B -->|"递：往前问"| C["..."]
    C -->|"递：往前问"| D["第1人<br/>'我是第1个！'"]
    D -->|"归：往回传"| C
    C -->|"归：往回传"| B
    B -->|"归：往回传"| A

    style A fill:#ffe599,stroke:#333
    style D fill:#d9ead3,stroke:#333

这个排队问人的过程，就是递归——

排队场景	对应递归
“你是第几个？”	函数调用自己
第一个人说”我是第1个”	终止条件（base case）
“我是前面那个的编号 +1”	递归关系
一路往回传答案	返回值逐层弹栈

💡 选看：递归的底层原理——调用栈

每次函数调用，Python 都会在调用栈上压入一个”栈帧”，记录函数的局部变量和返回地址。递归本质上就是把栈帧一层一层叠上去，触底（终止条件）后再一层一层弹回来。

1
# 用一个简单例子观察调用栈
2
def countdown(n):
3
    print(f"进入 countdown({n})")   # ← 压栈时打印
4
    if n <= 0:
5
        return
6
    countdown(n - 1)
7
    print(f"退出 countdown({n})")   # ← 弹栈时打印
8

9
countdown(3)

1
进入 countdown(3)
2
进入 countdown(2)
3
进入 countdown(1)
4
进入 countdown(0)
5
退出 countdown(1)
6
退出 countdown(2)
7
退出 countdown(3)

三、实战题目#

题目 1：计算阶乘和（1! + 2! + … + n!）#

题目：#

用户输入一个正整数 n，计算 1! + 2! + 3! + … + n! 的值并输出。

讲解：#

这道题可以分为两步：

写一个递归函数计算阶乘：jiecheng(n)
累加 1 到 n 的阶乘：jiecheng(1) + jiecheng(2) + ... + jiecheng(n)

阶乘的递归关系：

n! = \begin{cases} 1 & (n = 1) \\ n \times (n-1)! & (n > 1) \end{cases}

解题思路：#

flowchart LR
    A["输入 n"] --> B["定义递归函数<br/>jiecheng(k)"]
    B --> C{"k == 1 ?"}
    C -- 是 --> D["返回 1"]
    C -- 否 --> E["返回 k × jiecheng(k-1)"]
    D --> F["累加 jiecheng(1) 到 jiecheng(n)"]
    E --> F
    F --> G["输出结果"]

    style B fill:#9ccff9,stroke:#333
    style D fill:#d9ead3,stroke:#333
    style G fill:#ffe599,stroke:#333

代码实现：#

1
# ── 递归版：求 n 的阶乘 ──
2
def jiecheng(n):
3
    if n == 1:              # 终止条件：1! = 1
4
        return 1
5
    return n * jiecheng(n - 1)  # 递归关系：n! = n × (n-1)!
6

7
# ── 累加 1! 到 n! ──
8
n = int(input(""))
9
k = 0
10

11
for j in range(1, n + 1):
12
    k += jiecheng(j)
13
print(k)

变量	作用
`jiecheng(n)`	递归计算 `n!`
`k`	累加器，存放最终的和
`range(1, n+1)`	从 1 遍历到 n，逐个累加阶乘

运行测试：#

输入	计算过程	输出
`3`	1! + 2! + 3! = 1 + 2 + 6	`9`
`5`	1! + 2! + 3! + 4! + 5! = 1 + 2 + 6 + 24 + 120	`153`

题目 2：递归计算斐波那契数列第 n 项#

题目：#

使用递归计算斐波那契数列的第 20 个数字。

讲解：#

斐波那契数列的定义：

F(n) = \begin{cases} 1 & (n = 1 \text{ 或 } n = 2) \\ F(n-1) + F(n-2) & (n > 2) \end{cases}

数列的前几项：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

斐波那契数列是递归的天然例题——因为它的定义本身就是递归的：每一项等于前两项之和。

flowchart TD
    A["F(5)"] --> B["F(4)"]
    A --> C["F(3)"]
    B --> D["F(3)"]
    B --> E["F(2)"]
    C --> F["F(2)"]
    C --> G["F(1)"]
    D --> H["F(2)"]
    D --> I["F(1)"]
    E --> J["= 1"]
    F --> K["= 1"]
    G --> L["= 1"]
    H --> M["= 1"]
    I --> N["= 1"]

    style A fill:#ffe599,stroke:#333
    style J fill:#d9ead3,stroke:#333
    style K fill:#d9ead3,stroke:#333
    style L fill:#d9ead3,stroke:#333
    style M fill:#d9ead3,stroke:#333
    style N fill:#d9ead3,stroke:#333

解题思路：#

三要素分析：
- 终止条件：n == 1 或 n == 2 → 返回 1
- 递归关系：F(n) = F(n-1) + F(n-2)
- 递归调用：return feibo(n-1) + feibo(n-2)

代码实现：#

1
# ── 递归版：求斐波那契数列第 n 项 ──
2
def feibo(n):
3
    if n == 1 or n == 2:         # 终止条件
4
        return 1
5
    return feibo(n - 1) + feibo(n - 2)  # 递归关系
6

7
print(feibo(20))

运行结果：#

1
6765

输入	含义	输出
`feibo(1)`	第 1 项	`1`
`feibo(2)`	第 2 项	`1`
`feibo(10)`	第 10 项	`55`
`feibo(20)`	第 20 项	`6765`

四、递归 vs 循环：什么时候用递归？#

对比维度	递归	循环
代码简洁度	简洁、接近数学定义	通常代码更长
内存占用	每次调用占一个栈帧，可能栈溢出	只用一个循环体，内存开销小
执行速度	函数调用有开销，略慢	直接循环，更快
适合场景	树遍历、分治、回溯、数学归纳	简单重复操作、线性迭代

~~斐波那契用递归来计算第 20 项已经要调用 13529 次函数了，求第 50 项怕不是要等到天荒地老……~~

💡 进阶：用记忆化优化斐波那契

递归求斐波那契最大的问题是重复计算。用一个字典把算过的结果存起来，下次遇到直接取，效率就能从指数级降到线性级：

1
# ── 记忆化递归：用字典缓存已计算结果 ──
2
cache = {}
3

4
def feibo(n):
5
    if n in cache:           # 算过了，直接返回
6
        return cache[n]
7
    if n == 1 or n == 2:
8
        result = 1
9
    else:
10
        result = feibo(n - 1) + feibo(n - 2)
11
    cache[n] = result        # 存入缓存
12
    return result
13

14
print(feibo(20))  # 6765，但这次快得多
15
print(feibo(50))  # 12586269025，瞬间出结果

这就是记忆化搜索，也叫自顶向下的动态规划——是递归进阶的重要技巧！

五、总结#

核心要点	一句话
什么是递归	函数自己调用自己，把大问题拆成小问题
递归三要素	终止条件 + 递归关系 + 递归调用，缺一不可
调用栈	先进后出，终止条件触底后逐层返回
阶乘递归	`n! = n × (n-1)!`，终止于 `1`
斐波那契递归	`F(n) = F(n-1) + F(n-2)`，终止于 `F(1)=F(2)=1`
什么时候用	问题天然是”自相似”结构时用递归，简单重复用循环

愿有一天你能和你重要的人重逢

Python 递归入门#

学习目标#

一、什么是递归？#

二、递归的三要素#

递归，到底”递”了什么，“归”了什么？#

三、实战题目#

题目 1：计算阶乘和（1! + 2! + … + n!）#

题目：#

讲解：#

解题思路：#

代码实现：#

运行测试：#

题目 2：递归计算斐波那契数列第 n 项#

题目：#

讲解：#

解题思路：#

代码实现：#

运行结果：#

四、递归 vs 循环：什么时候用递归？#

五、总结#

继续阅读

换条路线

愿有一天你能和你重要的人重逢

Python 递归入门#

学习目标#

一、什么是递归？#

二、递归的三要素#

递归，到底”递”了什么，“归”了什么？#

三、实战题目#

题目 1：计算阶乘和（1! + 2! + … + n!）#

题目：#

讲解：#

解题思路：#

代码实现：#

运行测试：#

题目 2：递归计算斐波那契数列第 n 项#

题目：#

讲解：#

解题思路：#

代码实现：#

运行结果：#

四、递归 vs 循环：什么时候用递归？#

五、总结#

分享文章

沿着主题读

换条路线