返回专栏
· 11 分钟阅读

递归与迭代(Recursion vs. Iteration)


一、递归与迭代的基本概念

1. 递归(Recursion)

递归是指函数在执行过程中直接或间接调用自身,通过将原问题拆分为规模更小的子问题,逐步求解并组合结果。

递归通常包含两个必要组成部分:

  • 递归终止条件(Base Case):定义问题何时可以直接得到结果,阻止无限调用。
  • 递归关系(Recursive Case):将当前问题转换为规模更小的同类问题。

例如,计算阶乘:

n! = n \times (n-1)!

其中:

0! = 1

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

递归执行分为两个阶段:

  1. 递归深入阶段:不断调用自身,直到满足终止条件。
  2. 递归回退阶段:从最深层调用开始返回,逐层完成尚未计算的操作。

这两个阶段分别对应调用栈的压入与弹出。

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:

T(n) = T(n-1) + O(1)

递归深度通常为:

D(n) = O(n)

如果每层调用需要常数级栈空间,则额外空间复杂度为:

S(n) = O(n)

当递归深度过大时,可能出现:

  • 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+1} = F(S_k)

其中:

  • S_k:第 k 轮的状态。
  • F:状态更新函数。
  • S_{k+1}:更新后的状态。

迭代算法通常需要明确三个要素:

  1. 初始状态。
  2. 状态转移规则。
  3. 退出条件。

3.3 循环不变量

循环不变量(Loop Invariant)是理解和证明迭代算法正确性的重要工具。

它指的是:在循环执行的特定位置,始终成立的条件。

例如阶乘迭代:

def factorial(n):
    result = 1

    for i in range(1, n + 1):
        result *= i

    return result

可以定义循环不变量:

在每轮循环开始时:

result = (i-1)!

循环开始前,result = 1,对应 0! = 1。

执行一次:

result = result \times i

得到:

result = i!

下一轮开始时,循环变量递增,新的循环不变量仍然成立。

当循环结束时,结果就是:

result = n!

循环不变量通常通过三个步骤证明:

  • 初始化:第一次循环开始前成立。
  • 保持:每次循环执行后仍然成立。
  • 终止:循环结束时,不变量能够推出算法结果正确。

四、递归与迭代的数学关系

许多算法可以使用递归关系式描述,也可以转换成迭代形式。

4.1 递归关系

递归算法经常使用递归式描述执行时间:

T(n) = aT(n/b) + f(n)

其中:

  • a:每次产生的子问题数量。
  • n/b:子问题规模。
  • f(n):拆分、合并及其他额外工作。

例如归并排序:

T(n) = 2T(n/2) + O(n)

通过主定理可以得到:

T(n) = O(n\log n)

这里的递归关系描述算法的时间复杂度,并不意味着所有递归算法都具有相同的空间开销。

4.2 迭代关系

迭代算法可以表示为状态转移:

S_{k+1} = F(S_k)

通过不断应用状态转移函数,直到达到目标状态或退出条件。

例如斐波那契数列:

F(n) = \begin{cases} 0 & n=0 \\ 1 & n=1 \\ F(n-1)+F(n-2) & n\geq 2 \end{cases}

它既可以通过递归计算,也可以通过迭代维护前两个数值计算。

五、递归与迭代的典型算法对比

5.1 斐波那契数列

斐波那契数列定义:

F(0)=0,\quad F(1)=1
F(n)=F(n-1)+F(n-2)

递归实现

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

朴素递归的时间复杂度为:

T(n)=T(n-1)+T(n-2)+O(1)

其时间复杂度为指数级:

O(\varphi^n)

其中 \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

时间复杂度:

O(n)

额外空间复杂度:

O(1)

迭代只需要保存前两个状态,不需要构建递归调用树。

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 时间复杂度

时间复杂度主要取决于算法本身,而不是它是否使用递归。

例如: