一、递归与迭代的基本概念
1. 递归(Recursion)
递归是指函数在执行过程中直接或间接调用自身,通过将原问题拆分为规模更小的子问题,逐步求解并组合结果。
递归通常包含两个必要组成部分:
- 递归终止条件(Base Case):定义问题何时可以直接得到结果,阻止无限调用。
- 递归关系(Recursive Case):将当前问题转换为规模更小的同类问题。
例如,计算阶乘:
其中:
Python 实现:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(5)) # 120
函数通过调用自身,将阶乘问题逐步分解,直到遇到终止条件。
2. 迭代(Iteration)
迭代是指通过循环结构,重复执行某段代码,并在每次循环中更新状态,直到满足退出条件。
常见迭代结构:
for:按照指定范围或可迭代对象遍历。while:满足条件时持续执行。do-while:先执行一次,再判断是否继续,部分语言支持。
计算阶乘:
def factorial(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
print(factorial(5)) # 120
迭代通过变量保存中间结果,不需要反复调用函数。
3. 核心区别
| 对比维度 | 递归 | 迭代 |
|---|---|---|
| 实现方式 | 函数反复调用自身 | 循环结构重复执行 |
| 状态保存 | 通常依赖调用栈 | 通常使用变量或数据结构 |
| 终止方式 | 递归终止条件 | 循环退出条件 |
| 空间开销 | 通常与递归深度有关 | 通常可以保持常数级额外空间 |
| 代码结构 | 适合表达分治和层次关系 | 适合表达重复状态更新 |
| 性能特点 | 可能产生函数调用开销 | 通常更容易控制开销 |
| 典型场景 | 树遍历、分治、回溯 | 数组遍历、计数、状态更新 |
需要注意,递归与迭代是算法表达方式,不是两种完全不同的计算能力。许多递归算法都可以转换成迭代算法,反之亦然。
二、递归的执行原理
递归最重要的底层机制是函数调用栈。
每次函数调用,运行时都需要维护当前调用的执行状态,例如:
- 参数值。
- 局部变量。
- 返回地址。
- 临时计算结果。
- 寄存器保存信息及其他调用状态。
这些信息通常由调用栈帧(Stack Frame)或其他运行时机制管理。
2.1 递归调用过程
以阶乘函数为例:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
调用:
factorial(4)
递归调用关系:
flowchart TD
A["factorial(4)"] --> B["4 × factorial(3)"]
B --> C["3 × factorial(2)"]
C --> D["2 × factorial(1)"]
D --> E["1 × factorial(0)"]
E --> F["命中终止条件"]
F --> G["返回 1"]
G --> H["返回 1 × 1 = 1"]
H --> I["返回 2 × 1 = 2"]
I --> J["返回 3 × 2 = 6"]
J --> K["返回 4 × 6 = 24"]
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style E fill:#FFF5DE,stroke:#E8D29A,color:#334155
style F fill:#FFF5DE,stroke:#E8D29A,color:#334155
style G fill:#E8EDF2,stroke:#B8C3CE,color:#334155
style H fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style I fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style J fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style K fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
递归执行分为两个阶段:
- 递归深入阶段:不断调用自身,直到满足终止条件。
- 递归回退阶段:从最深层调用开始返回,逐层完成尚未计算的操作。
这两个阶段分别对应调用栈的压入与弹出。
2.2 调用栈与栈帧
以 factorial(4) 为例,递归深入时,逻辑上的调用栈逐步形成:
| 调用层级 | 当前参数 | 等待完成的操作 |
|---|---|---|
| 第 1 层 | 4 | 计算 4 × factorial(3) |
| 第 2 层 | 3 | 计算 3 × factorial(2) |
| 第 3 层 | 2 | 计算 2 × factorial(1) |
| 第 4 层 | 1 | 计算 1 × factorial(0) |
| 第 5 层 | 0 | 返回 1 |
每层调用都需要保留自己的执行状态。
当最深层返回后,调用栈逐层弹出,上一层恢复执行并继续计算。
因此,普通递归通常会产生与递归深度成正比的额外空间开销。
2.3 递归终止条件
递归必须具有能够到达的终止条件。
正确示例:
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
错误示例:
def countdown(n):
print(n)
countdown(n - 1)
第二个实现没有终止条件,会不断创建新的函数调用,最终可能触发运行时的递归深度限制或栈空间耗尽。
终止条件设计需要满足:
- 能够覆盖合法输入的边界情况。
- 递归参数必须向终止条件推进。
- 每条可能执行的递归路径都必须能够结束。
- 终止条件不能遗漏特殊输入。
2.4 递归深度与栈溢出
假设递归每次将问题规模减少 1:
递归深度通常为:
如果每层调用需要常数级栈空间,则额外空间复杂度为:
当递归深度过大时,可能出现:
- Python 的
RecursionError。 - C/C++ 程序的栈空间耗尽。
- Java 的
StackOverflowError。
不同语言、运行时和执行环境的限制并不相同,不能将某个语言的递归深度限制推广到其他语言。
三、迭代的执行原理
迭代通过循环重复执行操作,并通过变量或数据结构保存当前状态。
与递归依赖函数调用栈不同,普通迭代通常在同一个函数调用中更新状态。
3.1 迭代执行过程
阶乘实现:
def factorial(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
执行过程:
flowchart TD
A["初始化 result = 1"] --> B["设置 i = 1"]
B --> C{"i <= n ?"}
C -->|"是"| D["result = result × i"]
D --> E["i = i + 1"]
E --> C
C -->|"否"| F["返回 result"]
F --> G["结束"]
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style C fill:#FFF5DE,stroke:#E8D29A,color:#334155
style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style E fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style F fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style G fill:#E8EDF2,stroke:#B8C3CE,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
3.2 迭代状态
迭代的核心是维护状态。
以上述阶乘算法为例:
| 循环次数 | i |
result |
|---|---|---|
| 初始化 | 1 | 1 |
| 第 1 次 | 1 | 1 |
| 第 2 次 | 2 | 2 |
| 第 3 次 | 3 | 6 |
| 第 4 次 | 4 | 24 |
每轮循环根据当前状态计算下一轮状态。
可以抽象为:
其中:
- S_k:第 k 轮的状态。
- F:状态更新函数。
- S_{k+1}:更新后的状态。
迭代算法通常需要明确三个要素:
- 初始状态。
- 状态转移规则。
- 退出条件。
3.3 循环不变量
循环不变量(Loop Invariant)是理解和证明迭代算法正确性的重要工具。
它指的是:在循环执行的特定位置,始终成立的条件。
例如阶乘迭代:
def factorial(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
可以定义循环不变量:
在每轮循环开始时:
循环开始前,result = 1,对应 0! = 1。
执行一次:
得到:
下一轮开始时,循环变量递增,新的循环不变量仍然成立。
当循环结束时,结果就是:
循环不变量通常通过三个步骤证明:
- 初始化:第一次循环开始前成立。
- 保持:每次循环执行后仍然成立。
- 终止:循环结束时,不变量能够推出算法结果正确。
四、递归与迭代的数学关系
许多算法可以使用递归关系式描述,也可以转换成迭代形式。
4.1 递归关系
递归算法经常使用递归式描述执行时间:
其中:
- a:每次产生的子问题数量。
- n/b:子问题规模。
- f(n):拆分、合并及其他额外工作。
例如归并排序:
通过主定理可以得到:
这里的递归关系描述算法的时间复杂度,并不意味着所有递归算法都具有相同的空间开销。
4.2 迭代关系
迭代算法可以表示为状态转移:
通过不断应用状态转移函数,直到达到目标状态或退出条件。
例如斐波那契数列:
它既可以通过递归计算,也可以通过迭代维护前两个数值计算。
五、递归与迭代的典型算法对比
5.1 斐波那契数列
斐波那契数列定义:
递归实现
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
这种实现直观地表达了数学定义,但存在大量重复计算。
例如计算 fib(5) 时,fib(3)、fib(2) 等子问题会被多次计算。
递归调用树:
flowchart TD
A["fib(5)"] --> B["fib(4)"]
A --> C["fib(3)"]
B --> D["fib(3)"]
B --> E["fib(2)"]
C --> F["fib(2)"]
C --> G["fib(1)"]
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style E fill:#FFF5DE,stroke:#E8D29A,color:#334155
style F fill:#FFF5DE,stroke:#E8D29A,color:#334155
style G fill:#E8EDF2,stroke:#B8C3CE,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
朴素递归的时间复杂度为:
其时间复杂度为指数级:
其中 \varphi 为黄金比例。常见的宽松上界也可以写为 O(2^n)。
迭代实现
def fib(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
时间复杂度:
额外空间复杂度:
迭代只需要保存前两个状态,不需要构建递归调用树。
5.2 二叉树遍历
树结构天然具有递归特征。
例如二叉树前序遍历:
def preorder(node):
if node is None:
return
print(node.value)
preorder(node.left)
preorder(node.right)
递归表达非常自然:
- 访问当前节点。
- 遍历左子树。
- 遍历右子树。
但也可以使用显式栈实现迭代:
def preorder(root):
if root is None:
return
stack = [root]
while stack:
node = stack.pop()
print(node.value)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
这里将原本由运行时调用栈管理的遍历状态,转移到程序显式维护的栈中。
| 对比 | 递归遍历 | 迭代遍历 |
|---|---|---|
| 状态保存 | 系统调用栈 | 显式栈 |
| 代码结构 | 简洁 | 通常更复杂 |
| 空间复杂度 | O(h) | O(h) |
| 深度控制 | 受调用栈限制 | 可自行管理 |
| 适用场景 | 层次结构清晰 | 需要控制执行状态 |
其中 h 表示树的高度。对于退化成链表的树,h 可能达到 O(n)。
六、递归与迭代的复杂度分析
比较递归与迭代时,不能只看代码行数,还需要分析时间复杂度和空间复杂度。
6.1 时间复杂度
时间复杂度主要取决于算法本身,而不是它是否使用递归。
例如: