Hello 算法解析：Python 迭代与递归的图解实现与计算复杂性入门

导读

本篇围绕《Hello 算法》日文版（ja/）"计算复杂性"章节中"迭代与递归"这一核心主题展开：从随书 Python 源码与 Python Tutor 可视化链接出发，系统讲解 for/while 循环、嵌套循环、递归、调用栈、尾递归与递归树等基础控制结构。读者完成后既能看懂随书示例的逐步运行过程，也能理解"操作次数随输入规模 n 如何增长"这一通往时间/空间复杂度分析的必经之路。

一、为什么先讲迭代与递归

算法中存在大量"重复执行"的需求：循环求和、遍历数组、遍历树与图、按状态逐层推进……这类行为与复杂度分析关系极为密切。因此在讲解时间复杂度和空间复杂度之前，先明确两个实现重复执行的基本控制结构——迭代（iteration）与递归（recursion），是最自然的编排。本文对应的配套文档位于 ja/docs/chapter_computational_complexity/iteration_and_recursion.md，可直接运行的 Python 示例位于 ja/codes/python/chapter_computational_complexity/iteration.py 与 recursion.py。

在《Hello 算法》项目中，每个关键代码片段还会附带一个 Python Tutor 可视化入口。例如日文版 iteration.md 中的每条记录，都以

<!-- [file]{iteration}-[class]{}-[func]{for_loop} --> + 一段编码后的 Python Tutor URL 形式存放：

• 前半部分标注了源码文件与函数名的对应关系（MkDocs 插件据此把链接渲染成可运行的代码块）；
• 后半部分是 https://pythontutor.com/render.html#code=... 格式的 URL，其 py=311 参数表明运行环境为 Python 3.11，mode=display&curInstr=3 表示以逐步指令回放方式展示。

打开这些链接即可逐行、逐帧观察变量 res、i 与调用栈的变化——这正是"动画图解 + 一键运行"体验在计算复杂性章节的具体落地。

二、迭代：重复执行的控制结构

迭代（iteration） 是让程序在满足条件期间反复执行某段代码、直到条件不再满足为止的控制结构。在 iteration.py 中，作者用四个函数覆盖了迭代的常见形态。

2.1 for 循环：次数已知时的首选

for 循环适合迭代次数事先已知的场景。求和函数 for_loop(n) 计算 $1+2+\dots+n$：

def for_loop(n: int) -> int:
    """for ループ"""
    res = 0
    # 1, 2, ..., n-1, n を順に加算する
    for i in range(1, n + 1):
        res += i
    return res

需要特别注意的是 Python range(a, b) 的区间语义是左闭右开，即遍历 $a, a+1, \dots, b-1$，所以求和 $1..n$ 要写成 range(1, n + 1)。这一细节在日文文档中被作者专门标注，也是初学者最容易出错的地方之一。

该求和流程可用官方流程图直观查看：循环从 i=1 初始化开始，每轮判断 i ≤ n 是否成立，成立则执行累加任务并更新 i += 1，最终跳出循环输出结果。

从复杂度视角看，这个求和函数的操作次数与输入规模 $n$ 成"线性关系"——时间复杂度的概念描述的正是这种线性关系本身（详见 time_complexity.md）。在 iteration.py 的驱动代码中，以 n = 5 调用将输出 for ループの合計結果 res = 15。

2.2 while 循环：条件驱动、自由度更高

while 循环在每轮迭代前先检查条件，条件为真继续、为假退出。它的自由度比 for 更高——条件变量的初始化与更新步骤可以完全按需设计：

def while_loop(n: int) -> int:
    """while ループ"""
    res = 0
    i = 1  # 条件変数を初期化する
    # 1, 2, ..., n-1, n を順に加算する
    while i <= n:
        res += i
        i += 1  # 条件変数を更新する
    return res

下面的变体 while_loop_ii 演示了 for 循环难以自然表达的情形——条件变量在每轮迭代中被连续更新两次（i += 1 之后再 i *= 2），使 i 依次取 $1, 4, 10, \dots$，累加项数从线性退化为对数级别：

def while_loop_ii(n: int) -> int:
    """while ループ（2回更新）"""
    res = 0
    i = 1  # 条件変数を初期化する
    # 1, 4, 10, ... を順に加算する
    while i <= n:
        res += i
        # 条件変数を更新する
        i += 1
        i *= 2
    return res

总体结论正如日文文档所述：for 循环代码更简洁，while 循环更灵活，两者都能实现迭代结构，具体取舍应依据问题需求。

2.3 嵌套循环：操作次数升至 $n^2$

循环结构可以互相嵌套。nested_for_loop 用两层 for 生成 $(i,j)$ 坐标序列：

def nested_for_loop(n: int) -> str:
    """二重 for ループ"""
    res = ""
    # i = 1, 2, ..., n-1, n とループする
    for i in range(1, n + 1):
        # j = 1, 2, ..., n-1, n とループする
        for j in range(1, n + 1):
            res += f"({i}, {j}), "
    return res

外层 $i$ 每取一个值，内层 $j$ 就要完整遍历 $n$ 次，因此操作次数与 $n^2$ 成正比，即执行时间与输入规模呈二次关系。

继续增加嵌套层数时，每多一层就"升高一个维度"，时间复杂度会从二次、三次一路抬升。以 n = 5 运行此函数会得到 (1, 1), (1, 2), …, (5, 5), 共 25 个坐标对（对应驱动代码 iteration.py 的输出）。

三、递归：函数自我调用的策略

递归（recursion） 是指函数通过调用自身来解决问题的策略，包含两大阶段：

1. 递（再帰呼び出し）：程序不断向更深层调用自身，通常传入更小或更简化的参数，直到触及"终止条件"；
2. 归（復帰）：终止条件满足后，从最深层的递归函数逐层返回，并在每层汇总结果。

从实现看，递归代码由三个要素构成：终止条件（决定何时从递转为归）、递归调用（传入更小的子问题）、结果返回（将本层结果交还给上一层）。以下 recur(n) 用递归方式计算 $1+2+\cdots +n$，对应源码见 recursion.py：

def recur(n: int) -> int:
    """再帰"""
    # 終了条件
    if n == 1:
        return 1
    # 再帰：再帰呼び出し
    res = recur(n - 1)
    # 帰りがけ：結果を返す
    return n + res

3.1 迭代与递归：两种相反的思维范式

计算层面上两者结果等价，但它们代表两种截然不同的解题范式：

• 迭代：自底向上。从最基本的步骤出发，通过反复累加推进直到完成。对求和问题，即在循环中模拟累加过程，从 $1$ 遍历到 $n$。
• 递归：自顶向下。把原问题 $f(n)=1+2+\dots+n$ 分解为同构的子问题 $f(n)=n+f(n-1)$，继续分解到已知的基本情况 $f(1)=1$ 为止。

3.2 调用栈：递归的空间代价

每次递归调用，系统都要为新开启的函数分配内存，保存局部变量、返回地址等信息。这些函数上下文存放在"栈帧区域（スタックフレーム領域）"，直到函数返回才被释放。由此产生两个必然结果：

• 递归通常比迭代占用更多内存空间；
• 递归调用存在额外开销，因此通常比循环时间效率更低。

在终止条件触发之前，尚未返回的递归函数同时存在 $n$ 个，因此递归深度为 $n$。实践中编程语言对递归深度通常设有上限，过深的递归会引发栈溢出（Stack Overflow）。

3.3 尾递归：空间效率逼近迭代

若函数在返回之前的最后一个操作是递归调用，编译器/解释器可能对其优化，使空间效率接近迭代——这就是尾递归（tail recursion）：

• 普通递归：返回上一层后仍需继续执行后续代码，因此系统必须保留上层调用的上下文；
• 尾递归：递归调用是返回前的最后一步，返回后无需再做其他处理，系统不必保存上层函数上下文。

把结果变量 res 作为函数参数传入，即可把 $1+2+\dots+n$ 写成尾递归形式：

def tail_recur(n, res):
    """末尾再帰"""
    # 終了条件
    if n == 0:
        return res
    # 末尾再帰呼び出し
    return tail_recur(n - 1, res + n)

对比两种形式的执行时机：普通递归的加法发生在归的阶段（每层返回时再累加）；尾递归的加法发生在递的阶段（归的过程中各层只是原样返回）。运行输出同为 res = 15（见 recursion.py）。

⚠️ 注意：多数编译器/解释器并不支持尾递归优化。例如 Python 默认不支持 TCO，因此即便写成尾递归形式，深递归依然可能栈溢出——这一限定条件随书文档专门以 tip 形式提示。

3.4 递归树：一次调用分叉为两次

当函数体内出现两次递归调用时，一次调用会分叉出两个调用分支，持续展开便形成深度为 $n$ 的递归树（recursion tree）。经典例子是斐波那契数列 $0,1,1,2,3,5,8,13,\dots$：

• 前两项为 $f(1)=0,\ f(2)=1$；
• 其余每项为前两项之和：$f(n)=f(n-1)+f(n-2)$。

按递推式递归调用、以前两项为终止条件即可写出 fib(n)：

def fib(n: int) -> int:
    """フィボナッチ数列：再帰"""
    # 終了条件 f(1) = 0, f(2) = 1
    if n == 1 or n == 2:
        return n - 1
    # f(n) = f(n-1) + f(n-2) を再帰的に呼び出す
    res = fib(n - 1) + fib(n - 2)
    # 結果 f(n) を返す
    return res

递归展开后形成以 $f(n)$ 为根、向 $f(n-1)$ 与 $f(n-2)$ 不断分裂的树状结构——大量子问题被重复计算，这正是后文引入动态规划优化的起点。

本质上看，递归体现了"把问题分解成更小子问题"的思考范式，这种分治策略极为重要：搜索、排序、回溯、分治、动态规划等算法策略都直接或间接依赖它；而链表、树、图类问题天然契合递归的分解式分析。

四、迭代与递归的对比总结

下表摘自 iteration_and_recursion.md 末尾的官方总结，是两者的速查对照：

维度	迭代	递归
实现方式	循环结构	函数自我调用
时间效率	通常更高，无函数调用开销	每次调用均有开销
内存占用	通常占用固定规模内存	调用累积可能占用大量栈帧区域
适用场景	简单重复处理，代码直观易读	树、图、分治、回溯等子问题分解场景，代码结构简洁清晰

五、用显式栈把递归改写成迭代

递归中加法在"归"的阶段完成，意味着最先调用的函数最后才完成累加——这与栈的"后进先出（LIFO）"原则如出一辙。事实上，"调用栈""栈帧区域"这些术语本身就在暗示递归与栈的紧密关系：

1. 递：函数被调用时，系统在调用栈上为新函数分配栈帧，保存局部变量、参数与返回地址；
2. 归：函数执行完返回时，对应栈帧从调用栈弹出，上一层函数的执行环境被恢复。

因此，可以用显式栈模拟调用栈的行为，从而把递归改写为迭代。for_loop_recur 先用 for 循环把 $n,n-1,\dots,1$ 依次 push 进栈（模拟"递"），再用 while 循环逐个 pop 累加（模拟"归"）：

def for_loop_recur(n: int) -> int:
    """反復で再帰を模擬する"""
    # 明示的なスタックを使ってシステムコールスタックを模擬する
    stack = []
    res = 0
    # 再帰：再帰呼び出し
    for i in range(n, 0, -1):
        # 「スタックへのプッシュ」で「再帰」を模擬する
        stack.append(i)
    # 帰りがけ：結果を返す
    while stack:
        # 「スタックから取り出す操作」で「帰り」をシミュレート
        res += stack.pop()
    # res = 1+2+3+...+n
    return res

💡 若对"栈"尚不熟悉，随书建议：读完"栈"章节后再回看本段内容效果更佳。

值得注意的是，把递归改写为迭代后，代码往往更复杂、可读性下降；对于复杂问题，模拟系统调用栈本身可能极其困难。因此二者虽多数情况下可互相转换，却并非总是值得——用迭代还是递归，最终取决于问题本身的性质，应权衡两者优劣、因题制宜。

六、动手验证与继续深入

1. 本地运行：直接执行 python3 ja/codes/python/chapter_computational_complexity/iteration.py 与 python3 ja/codes/python/chapter_computational_complexity/recursion.py，可分别看到 for/while/嵌套循环以及普通递归/显式栈改写/尾递归/斐波那契的全部输出。
2. 逐步可视化：打开 ja/codes/pythontutor/chapter_computational_complexity/iteration.md，点击每个函数对应的 Python Tutor 链接，即可在浏览器中观察 res、i、n 等变量的逐帧变化与调用栈展开/回退。
3. 多语言对照：本项目同一份示例在 Python、Java、C++、Go、JS、Rust 等十余种语言中均有实现（日文版位于 ja/codes，中文版位于 codes），例如中文版对应的 codes/python/chapter_computational_complexity/iteration.py，便于横向比较不同语言中 for/while/函数调用的语法差异。
4. 延伸阅读：本节知识直接服务于后续的 time_complexity.md、space_complexity.md 与 performance_evaluation.md。尤其值得留意：上面各例中"操作次数随 $n$ 线性增长（for/while 求和）""以 $n^2$ 增长（嵌套循环）""以 $2^n$ 增长（朴素斐波那契递归）"，恰好对应复杂度的几个典型量级，是理解大 O 记号的直观入口。