递归

一、函数调用与递归

调用与返回的顺序

上一讲的列表可以包含其他列表。例如，[1, [2, 3], [4, [5]]] 有不同深度的嵌套。固定两层循环不能处理所有可能的层数。处理内层列表时，能否再次使用处理外层列表的函数？

先观察普通函数调用。下面的 outer 调用 inner，得到返回值后继续执行。

def inner() -> int:
    print("B")
    return 2

def outer() -> int:
    print("A")
    result = inner()
    print("C")
    return result + 1

print(outer())

输出顺序为 A、B、C、3，各占一行。inner 执行期间，outer 的调用没有结束。outer 保留自己的局部变量和后续操作，等待 inner 返回。

函数执行到调用语句时，被调用的名字必须已经绑定到函数。不要求被调用函数的定义在文本中永远位于调用者定义之前；上述例子真正执行 outer() 时，两个名字都已经绑定。

阶乘的递归定义

递归（recursion）指函数直接或间接调用自身。阶乘可以用一个规模更小的阶乘定义：

• 0! = 1；
• 对正整数 n，n! = n × (n−1)!。

以下函数的输入约定是：n 为非负整数。类型提示 n: int 不会自动检查输入，也不会自动排除负数。

def factorial(n: int) -> int:
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(3))
print([factorial(n) for n in range(6)])

结果分别为 6 和 [1, 1, 2, 6, 24, 120]。每次递归调用把参数减一，最终到达 n == 0，直接返回 1。

调用顺序与返回顺序

在下面的阶乘实现中，乘法需要等待下一层调用返回。加入输出后，可以分别观察进入函数和返回结果的顺序。depth 只用于缩进。

def factorial(n: int, depth: int = 0) -> int:
    pad = "  " * depth
    print(f"{pad}enter {n}")
    if n == 0:
        result = 1
    else:
        result = n * factorial(n - 1, depth + 1)
    print(f"{pad}return {result}")
    return result

print(factorial(3))

进入顺序是 3 → 2 → 1 → 0；四次返回的值依次为 1 → 1 → 2 → 6。最外层的 print 随后输出 6。

每次调用有自己的局部环境。内层的 n = 1 不会覆盖外层的 n = 2。factorial(2) 恢复执行时，仍用自己的 n 完成 2 * 1。

这里的乘法发生在递归调用返回之后。一般递归程序也可以在调用前、调用后或两次递归调用之间计算或输出；汉诺塔会使用第三种顺序。

调用栈与深度上限

尚未结束的调用需要保留局部变量和恢复执行的位置。用调用栈（call stack）可以描述这些调用的关系。栈遵循后进先出（LIFO, last in, first out）：内层调用先结束，外层调用再继续。

进入 f(3)      [f(3)]
进入 f(2)      [f(3), f(2)]
进入 f(1)      [f(3), f(2), f(1)]
进入 f(0)      [f(3), f(2), f(1), f(0)]
f(0) 返回 1    [f(3), f(2), f(1)]
f(1) 返回 1    [f(3), f(2)]
f(2) 返回 2    [f(3)]
f(3) 返回 6    []

这是逻辑调用帧示意，不是 CPython 的物理内存布局。递归调用需要存储执行状态，但不同解释器的具体实现可能不同。

import sys

print("Recursion limit:", sys.getrecursionlimit())

常见环境的上限是 1000，实际值应以上述输出为准。已经存在的调用也会影响可用深度，不能据此认定第 1000 次用户函数调用必然报错。

下面的程序在数学上会终止，但调用链过深。在本讲核验所用的默认上限下，运行会触发预期的 RecursionError。

def countdown(n: int) -> int:
    if n == 0:
        return 0
    return countdown(n - 1)

print(countdown(5000))

RecursionError 表示超过解释器允许的递归深度，不等于物理内存已经耗尽。原因可能是无法终止，也可能是合法输入需要的深度超过当前上限。本讲不通过提高上限解决问题。

基准情形与递减度量

要让递归在约定的输入范围内终止，需要明确：

1. 基准情形（base case）：直接处理，不再递归。
2. 递推关系：下一层处理什么同类问题，返回结果怎样用于当前问题。
3. 终止性依据：证明下一层更接近基准情形。本讲主线使用严格递减的非负整数度量。

度量可以是 n、列表长度或剩余行数，不要求所有参数的数值都减少。皇后问题中，已放置的皇后数增加，但剩余行数减少。参考区的 Ackermann 函数则需要分层比较两个参数。

以下三个运行块分别展示三种错误，都会在默认上限下触发预期的 RecursionError。

没有基准情形。

def bad(n: int) -> int:
    return n * bad(n - 1)

print(bad(3))

有基准情形，但调用没有取得进展。

def never_ends(n: int) -> int:
    if n == 0:
        return 0
    return never_ends(n)

print(never_ends(3))

参数不断减少，但无法到达基准情形。

def down(n: int) -> int:
    if n == 0:
        return 0
    return down(n - 2)

print(down(3))

第三个例子的参数依次为 3, 1, -1, -3, ...，始终不等于零。仅检查“参数变小”不足以证明终止。

分析正确性时，先写清函数任务和输入范围，检查基准情形，再假设规模更小的任务已正确完成，证明当前步骤能组合出正确结果。这个归纳式推理还必须有终止性依据，不能只凭某一步的公式判断整个程序正确。

二、递归数据与子问题

isinstance 与嵌套列表

isinstance(x, list) 判断对象 x 是否为列表实例，返回布尔值。它也接受列表子类的实例；本讲例子只使用普通列表。

for x in [3, [1, 2], []]:
    print(isinstance(x, list))

输出依次为 False、True、True。据此可以把每个元素分为整数和内层列表两类。

下面的输入限于有限、没有循环引用的嵌套列表，非列表元素均为整数。例如，令一个列表包含自身就会形成循环引用，不符合本函数的输入约定。

def deep_sum(items: list) -> int:
    total = 0
    for x in items:
        if isinstance(x, list):
            total += deep_sum(x)
        else:
            total += x
    return total

print(deep_sum([1, [2, 3], [4, [5, [6, 7]]]]))
print(deep_sum([1, [], [2, []]]))
print(deep_sum([]))

输出为 28、3、0。每层调用有自己的 total。空列表的循环执行零次，直接返回初值 0，不必单独增加 if。

循环负责处理同一层的各个元素，递归负责处理内层列表。递归不需要预先写出嵌套层数，但仍受调用深度和存储条件限制。参考区给出显式栈循环版本。

最大公约数

对非负整数 a、b，欧几里得算法使用：

• gcd(a, 0) = a；
• b > 0 时，gcd(a, b) = gcd(b, a % b)。

通常最大公约数的输入不同时为零；以下程序另约定 gcd(0, 0) 返回 0。

def gcd(a: int, b: int) -> int:
    if b == 0:
        return a
    return gcd(b, a % b)

print(gcd(48, 18))
print(gcd(1071, 462))
print(gcd(0, 5))

结果为 6、21、5。第一组参数的变化为 (48, 18) → (18, 12) → (12, 6) → (6, 0)。b > 0 时余数非负且小于 b，因此第二个参数是递减度量。第一个参数有时会增加，不影响这个终止性论证。

斐波那契数列与重复计算

统一使用 F(0) = 0、F(1) = 1；对 n ≥ 2，F(n) = F(n−1) + F(n−2)。输入 n 为非负整数。

def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print([fib(n) for n in range(10)])

输出为 [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]。每个非基准调用产生两个子调用。fib(5) 的调用树中，fib(3) 出现两次；相同参数不会自动复用此前结果。

可以让函数同时返回数值和调用次数。基准情形也算一次调用；当前调用的计数是 1 加上两棵子调用树的计数。

def fib_counted(n: int) -> tuple[int, int]:
    if n <= 1:
        return n, 1
    left, c1 = fib_counted(n - 1)
    right, c2 = fib_counted(n - 2)
    return left + right, 1 + c1 + c2

for n in [5, 10, 20, 25]:
    value, calls = fib_counted(n)
    print(n, value, calls)

n = 5, 10, 20, 25 的调用次数分别为 15, 177, 21891, 242785。这些是包括基准调用在内的准确计数，不是 2ⁿ 次，也不是运行秒数。

朴素递归的主要问题是重复计算。保存已算出的结果称为记忆化（memoization），后续课程再讨论；参考区先用两种循环实现作为对照。

快速幂与结果复用

设底数 a 为整数，指数 n 为非负整数：

• a⁰ = 1；此程序也按该约定令 power(0, 0) 返回 1；
• 偶数指数：aⁿ = (a^(n//2))²；
• 奇数指数：aⁿ = (a^(n//2))² × a。

def power(a: int, n: int) -> int:
    if n == 0:
        return 1
    half = power(a, n // 2)
    if n % 2 == 0:
        return half * half
    return half * half * a

print(power(2, 10))
print(power(3, 5))
print(power(2, 100))

输出为 1024、243 和 1267650600228229401496703205376。指数链 10 → 5 → 2 → 1 → 0 只有一个递归子问题。half 保存该子问题的结果，再用于两个乘数。

如果直接写两次 power(a, n // 2)，就会执行两次调用。表达式的参数相同，不表示解释器自动保存结果。

从初值 1 开始逐次乘以 a 需要 n 次乘法。快速幂的指数逐次减半，每个非基准调用进行一到两次乘法，算术操作次数随指数的二进制位数增长。但整数结果也在变大，乘法的耗时和存储量并不固定。不能把“较少的乘法”直接说成大整数总耗时只与 log n 成正比。参考区会实际计数。

三、分治

分治（divide and conquer）把问题分解为较小的子问题，再利用子问题的结果。二分查找只继续处理一个候选区间；归并排序处理两个子列表并合并；快速幂处理一个子问题并复用结果。三种结构的计算量不同。

二分查找的有序前提

二分查找要求输入列表已经按非递减顺序排列。只有满足这个前提，中点比较才能排除一侧。以下代码不会自动排序，也不会检查有序性。

采用闭区间 [lo, hi]，两端都包含。lo > hi 表示区间为空。辅助函数处理指定区间，包装函数提供全列表接口。

def search_range(nums: list[int], target: int,
                 lo: int, hi: int) -> int:
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if nums[mid] == target:
        return mid
    if nums[mid] < target:
        return search_range(nums, target, mid + 1, hi)
    return search_range(nums, target, lo, mid - 1)

def binary_search(nums: list[int], target: int) -> int:
    return search_range(nums, target, 0, len(nums) - 1)

data = [1, 3, 5, 7, 9, 11, 13, 15]
for target in [7, 1, 15, 8]:
    print(target, binary_search(data, target))
print("empty:", binary_search([], 3))
print("single hit:", binary_search([3], 3))
print("single miss:", binary_search([3], 4))
print("duplicates:", binary_search([1, 3, 3, 3, 5], 3))

搜索 15 的区间变化为 [0,7] → [4,7] → [6,7] → [7,7]。搜索 8 的区间变化为 [0,7] → [4,7] → [4,4] → [4,3]，最终返回 -1。

已比较的中点必须排除，因此下一层使用 mid + 1 或 mid - 1。空输入、单元素和未命中都有相应结果。重复值输入返回任意一个命中下标，不保证是最左位置。

一百万个元素至多需要考察约二十个中点；这不是恰好二十次 == 或 < 运算，每轮可能进行两次值比较。正式的复杂度分析留到 L11。

归并排序与归并过程

归并排序先把列表分为两半，分别排序，再合并两个有序列表。长度为零或一的列表已经有序。

归并时，i 和 j 分别指向两侧尚未使用的第一个元素。选择较小者加入结果；一侧耗尽后，把另一侧剩余元素接到末尾。以下运行块包含所有辅助函数。

def merge(a: list[int], b: list[int]) -> list[int]:
    result: list[int] = []
    i = 0
    j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1
    result.extend(a[i:])
    result.extend(b[j:])
    return result

def merge_sort(nums: list[int]) -> list[int]:
    if len(nums) <= 1:
        return nums.copy()
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    return merge(left, right)

print(merge([3, 7], [1, 4]))
data = [7, 3, 4, 5, 1, 2, 3]
print(merge_sort(data))
print(data)
print(merge_sort([]))

排序结果为 [1, 2, 3, 3, 4, 5, 7]，重复值保留，原列表不变。基准情形也返回副本，因此每次结果都是新列表。

两个子列表的长度都小于原列表，保证递归接近基准。归并扫描、列表切片和结果分配都需要计算或存储，不能只数递归层数来估计总工作量。

四、汉诺塔的指令顺序

规则与任务分解

汉诺塔有三根柱子 A、B、C。n 个盘子大小不同，初始都在 A，大盘在下、小盘在上。盘号从 1 到 n，编号越大盘子越大。一次只能移动一个顶盘，大盘不能放在小盘上。目标是把全部盘子移到 C。

本节先写输出移动指令的函数，不保存或修改柱子状态。参数 n 为非负整数，三个柱名互不相同。把 n 个盘从 source 移到 target，利用 spare，可以分成：

1. 把上面 n−1 个盘从 source 移到 spare，利用 target；
2. 把盘 n 从 source 移到 target；
3. 把 n−1 个盘从 spare 移到 target，利用 source。

柱子名称不变，各柱承担的起始柱、目标柱和备用柱角色随子调用改变。n == 0 表示没有盘子，不输出指令。

def hanoi(n: int, source: str, target: str, spare: str) -> None:
    if n == 0:
        return
    hanoi(n - 1, source, spare, target)
    print(f"disk {n}: {source} -> {target}")
    hanoi(n - 1, spare, target, source)

hanoi(3, "A", "C", "B")

程序输出七条指令。打印位于两个递归调用之间，负责保证输出的先后顺序。若要证明某个实际移动序列合法，还需要根据柱子状态检查每次是否移动顶盘、是否违反大小约束，以及最终位置是否正确。打印出文字本身没有改变盘子状态。

移动次数与最少步数

令 T(n) 为普通三柱汉诺塔转移的最少移动次数。最大盘首次离开起点之前，上面的 n−1 个盘必须移到另一柱；最大盘最终到达目标之后，小盘还必须转移到目标。按最大盘的移动方式分析，可得至少需要两次 n−1 盘转移和一次最大盘移动；若最大盘经备用柱转移，所需移动只会更多。

上述三阶段构造恰好达到下界，因此 T(0) = 0，T(n) = 2T(n−1) + 1，解为 T(n) = 2ⁿ−1。以下函数返回移动次数，不依赖全局计数器。

def count_moves(n: int) -> int:
    if n == 0:
        return 0
    smaller = count_moves(n - 1)
    return 2 * smaller + 1

for n in range(8):
    print(n, count_moves(n), 2**n - 1)

这里计算的是移动次数，不是 hanoi 的函数调用次数。打印七条指令的三盘程序，连同 n == 0 的调用在内，共调用十五次。递归深度随 n 增加，而移动指令数按指数增长。

输出与返回值

-> None 是返回值类型提示，不表示函数不发生返回。执行裸 return 或到达函数末尾，都会返回 None。下面的运行块先打印一条指令，再打印返回值。

def hanoi(n: int, source: str, target: str, spare: str) -> None:
    if n == 0:
        return
    hanoi(n - 1, source, spare, target)
    print(f"disk {n}: {source} -> {target}")
    hanoi(n - 1, spare, target, source)

result = hanoi(1, "A", "C", "B")
print(result)

本函数的作用是输出指令，返回值是 None。数值计算、打印输出和修改状态是不同任务，函数约定必须分别说明。练习要求把指令作为列表返回；个人作业还要求验证序列，不能仅凭步数公式判断正确。

五、枚举与回溯

全排列与空排列

列表的全排列是所有元素次序。递归子任务可以定义为“返回剩余元素的所有排列”：选一个首项，排列其余项，再把首项加在每个结果前面。

def permutations(items: list[int]) -> list[list[int]]:
    if len(items) <= 1:
        return [items.copy()]
    result: list[list[int]] = []
    for i in range(len(items)):
        rest = items[:i] + items[i + 1:]
        for p in permutations(rest):
            result.append([items[i]] + p)
    return result

for p in permutations([1, 2, 3]):
    print(p)
print("empty:", permutations([]))
print("single:", permutations([7]))
print("duplicates:", permutations([1, 1, 2]))

空列表返回 [[]]：长度为零时有一个空排列，不是零个排列。基准情形使用副本，结果列表不与输入列表共用同一个可修改列表。

重复输入按位置枚举，因此 [1, 1, 2] 有六项结果，但只有三种不同的数值次序。本函数不去重，也不修改输入。

与标准库核验

itertools.permutations 可以作为小输入的对照。它产生元组，这里转换为列表。核验必须真正调用自写函数；排序后的列表比较保留每种结果的重复次数，用集合比较则会丢失这些信息。

from itertools import permutations as std_perm

def permutations(items: list[int]) -> list[list[int]]:
    if len(items) <= 1:
        return [items.copy()]
    result: list[list[int]] = []
    for i in range(len(items)):
        rest = items[:i] + items[i + 1:]
        for p in permutations(rest):
            result.append([items[i]] + p)
    return result

for items in [[], [7], [1, 2, 3], [1, 1, 2]]:
    mine = permutations(items)
    standard = [list(p) for p in std_perm(items)]
    print(items, len(mine), len(standard), sorted(mine) == sorted(standard))

四组比较均为 True，数量分别为 1、1、6、6。这些测试覆盖几个重要边界，但有限测试不能替代一般正确性论证。

皇后问题的部分解

在 n × n 棋盘上放置 n 个皇后，任意两个不能同行、同列或同对角线。逐行放置后，不同行由构造保证。用 queens[row] = column 表示已经放置的皇后，行列下标从零开始。例如 [1, 3, 0, 2] 是一个四皇后解。

下一行是 row = len(queens)。新皇后与旧皇后 (r, c) 同列的条件是 col == c，同对角线的条件是 abs(row - r) == abs(col - c)。

def is_safe(queens: list[int], col: int) -> bool:
    row = len(queens)
    for r, c in enumerate(queens):
        if c == col:
            return False
        if abs(row - r) == abs(col - c):
            return False
    return True

def count_queens(n: int, queens: list[int]) -> int:
    if len(queens) == n:
        return 1
    total = 0
    for col in range(n):
        if is_safe(queens, col):
            total += count_queens(n, queens + [col])
    return total

for n in range(4, 9):
    print(n, count_queens(n, []))

结果为 2、10、4、40、92。初始部分解显式传入 []；递归调用只接收合法的部分解。剩余行数 n - len(queens) 严格减少。

回溯（backtracking）逐项尝试候选；候选冲突时，不再扩展该分支，继续尝试其他候选。这里 queens + [col] 创建新列表，外层部分解保持不变，因此不需要原地撤销操作。若改用同一个列表的 append，则必须在返回后撤销相应选择。参考区保留先枚举全部列号排列、再检查对角线的另一种方法。

自相似图形

谢尔宾斯基三角形具有自相似结构：下一阶由三份缩小的上一阶图形组成，适合递归生成。不能把“完全相同的缩小副本”当作所有分形都必须满足的定义。

下面的文本版本接收非负整数阶数 n，返回 2ⁿ 行字符串。

def sierpinski(n: int) -> list[str]:
    if n == 0:
        return ["*"]
    smaller = sierpinski(n - 1)
    size = len(smaller)
    pad = " " * size
    top = [pad + line + pad for line in smaller]
    bottom = [line + " " + line for line in smaller]
    return top + bottom

for line in sierpinski(3):
    print(line)
for n in range(5):
    lines = sierpinski(n)
    stars = 0
    for line in lines:
        stars += line.count("*")
    print(n, len(lines), stars)

上半部分放一份子图，下半部分并排放两份。每增加一阶，行数翻倍、星号数变为三倍；n = 0..4 的行数为 1, 2, 4, 8, 16，星号数为 1, 3, 9, 27, 81。文本图的宽度含有排版空格，不应直接称为几何边长。

六、递归与循环的选择

递归可以改写为显式维护状态的循环，但不一定只需把调用替换成一个 for。对嵌套结构和分支任务，循环可能需要栈等数据结构保存待处理任务。

阶乘是学习调用与返回的短例子，实际计算通常用循环更直接。以下两种实现都接收非负整数。

def factorial_loop(n: int) -> int:
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

def factorial_rec(n: int) -> int:
    if n == 0:
        return 1
    return n * factorial_rec(n - 1)

print(factorial_loop(10), factorial_rec(10))

两者均返回 3628800。它们进行相近数量的乘法，但递归还需保留每层调用。另一方面，朴素 Fibonacci 与循环 Fibonacci 的差异主要来自重复计算，不能把全部差异都归因于一次函数调用的开销。

选择实现时，分别检查问题结构、重复工作、最大调用深度、容器复制和输出规模。代码更短不代表算法更快，也不代表已经证明正确。

小结

• 函数任务要有明确的输入范围、基准情形、递推关系和终止性依据。
• 每次调用有自己的局部环境；外层在内层返回后恢复执行。
• 递归计算可以发生在调用前、调用后或两个调用之间。
• RecursionError 表示深度超过上限，不证明物理内存已经耗尽。
• 嵌套遍历、二分查找、归并排序和快速幂的子问题结构不同。
• 朴素 Fibonacci 重复计算；保存一个返回值可以避免再次求同一个子问题。
• 汉诺塔示例输出指令并返回 None，没有修改柱子状态。
• 回溯扩展合法部分解，并提前排除冲突分支。
• 递归与循环都需要计算和存储；应根据任务比较具体实现。

练习

保留以下七项练习。与 Lab 7 重合的实现应独立完成；参考区只给出相关概念和过程演示。

1. 写 count_digits(n: int) -> int，用递归计算非负整数的十进制位数。说明 n = 0 的基准情形。
2. 写 reverse_string(s: str) -> str，用递归反转字符串，不使用 [::-1]。检查空串和单字符输入。
3. 写 sum_digits(n: int) -> int，用递归求非负整数的数位和，与 Lab 4 的循环写法比较。考虑零和超过当前递归深度的输入。
4. 用显式参数或返回计数的方式统计 fib 在 n = 1..25 时的调用次数，绘制增长曲线，并解释重复子问题。
5. 写 flatten(items: list) -> list[int]，按从左到右的次序压平有限、无循环引用、整数元素的嵌套列表，不修改输入。例如 [1, [2, [3, [4]]]] 得到 [1, 2, 3, 4]。检查空列表和内层空列表。
6. 修改本讲的 hanoi，把移动指令作为列表返回，不再打印。说明返回指令列表与执行移动、验证状态有什么区别。
7. 用递归实现 is_palindrome(s: str) -> bool，判断字符串是否回文。说明空串和单字符的结果。

配套实验见 Lab 7。个人作业 1 的普通汉诺塔与相邻杆变体需要实现和验证移动序列，本讲不提供完整作业答案；提交要求、评分和日期以正式作业说明为准。

参考：完整示例与扩展

以下内容用于课后阅读。每个运行块都包含自身所需的全部定义，不依赖此前运行过其他代码块。

显式栈遍历嵌套列表

把尚未处理的元素放在列表中，用 pop() 取出末项，可以把递归求和改为循环。输入范围与 deep_sum 相同：有限、无循环引用，叶子均为整数。

def deep_sum_stack(items: list) -> int:
    pending = items.copy()
    total = 0
    while pending:
        x = pending.pop()
        if isinstance(x, list):
            pending.extend(x)
        else:
            total += x
    return total

print(deep_sum_stack([1, [2, 3], [4, [5, [6, 7]]]]))
print(deep_sum_stack([1, [], [2, []]]))
print(deep_sum_stack([]))

这个版本优先处理末尾元素，与主线的从左到右访问次序不同，但不影响整数总和。若任务是按顺序压平列表，就不能忽略访问次序。显式栈避开递归调用链，仍占用存储空间。

快速幂的操作计数

以下函数返回结果和乘法次数。偶数分支计一次，奇数分支计两次；包括 1 * 1 这样的乘法。

def power_counted(a: int, n: int) -> tuple[int, int]:
    if n == 0:
        return 1, 0
    half, multiplications = power_counted(a, n // 2)
    if n % 2 == 0:
        return half * half, multiplications + 1
    return half * half * a, multiplications + 2

for n in [0, 1, 5, 10, 100]:
    value, multiplications = power_counted(2, n)
    print(n, value, multiplications)

power_counted(2, 10) 的指数链为 10, 5, 2, 1, 0，共六次乘法。调用深度、乘法次数和结果位数是不同指标。即使乘法次数较少，极大的结果仍需要相应的存储空间，大整数乘法也会随操作数位数增加而更昂贵。

数字递归：二进制表示与置位计数

对非负整数，反复除以二得到更小的商，余数是当前最低二进制位。先得到商的表示，再附加余数，可以生成二进制字符串。零的表示是 "0"，不需要继续递归。

def binary_text(n: int) -> str:
    if n < 2:
        return str(n)
    return binary_text(n // 2) + str(n % 2)

for n in [0, 1, 2, 13]:
    print(n, binary_text(n))

二进制字符串的长度与其中 1 的数量不同。以下函数计算置位数，即值为 1 的二进制位数。零的置位数为零。

def count_set_bits(n: int) -> int:
    if n == 0:
        return 0
    return count_set_bits(n // 2) + n % 2

for n in [0, 1, 2, 13]:
    print(n, count_set_bits(n))

十进制数位与整数逆序

十进制中，n // 10 是去掉末位后的前缀，n % 10 是末位。单个十进制数字包括零，其位数为一。位数练习需要区分原输入零与递归中的结束状态，不在这里给出完整函数。

下面用字符串长度确定末位应移到的位置，演示非负整数的逆序。它不是字符串反转练习的答案。

def reverse_decimal(n: int) -> int:
    if n < 10:
        return n
    width = len(str(n))
    return (n % 10) * 10**(width - 1) + reverse_decimal(n // 10)

for n in [0, 7, 120, 1000, 2026]:
    print(n, len(str(n)), reverse_decimal(n))

120 的整数逆序是 21，不能保留前导零。这个写法每层都计算 len(str(n))，会重复转换越来越短的前缀；若每层递归重算位数，也会增加额外工作。作为计算方法，它不一定优于循环。

数位和的三种思路

数位和可以用字符串循环、算术 while 或递归计算。为保留 Lab 7-5 的实现任务，下面只对固定输入 2026 演示循环及递归的数位贡献，不提供完整的递归求和函数。

n = 2026

text_total = 0
for digit in str(n):
    text_total += int(digit)

arithmetic_total = 0
remaining = n
while remaining > 0:
    arithmetic_total += remaining % 10
    remaining //= 10

def trace_digit_contributions(prefix: int) -> None:
    print("prefix and last digit:", prefix, prefix % 10)
    if prefix >= 10:
        trace_digit_contributions(prefix // 10)

trace_digit_contributions(n)
expanded_total = 6 + (2 + (0 + 2))
print(text_total, arithmetic_total, expanded_total)

三个计算结果都为 10。追踪函数只打印前缀和末位，返回 None；expanded_total 是固定输入的递推展开式，不是可用于任意输入的求和函数。完成练习时，需要自行写出返回值的组合、基准情形和零输入行为。

10**1000 是 1 后接一千个零，十进制有 1001 位。有限的整数输入仍可能需要超过当前上限的递归深度。

import sys

n = 10**1000
print("Decimal digits:", len(str(n)))
print("Recursion limit:", sys.getrecursionlimit())

这里转换的整数在常见环境的十进制转换位数限制内。不能据此推广为任意大整数的 str 转换都不受限制。数位递归的实际异常应在运行环境中记录，不应调高上限后再声称原程序适用于所有位数。

三阶递推

保留往年材料的原递推，不把它改成三个前项相加：

a₁ = 1，a₂ = 2，a₃ = 3；

aₙ₊₃ = 3aₙ₊₂ − 2aₙ₊₁ + aₙ，n ≥ 1。

代码参数 k 是项号，必须为正整数。三个初值分别对应三个基准情形。

def third_order(k: int) -> int:
    if k == 1:
        return 1
    if k == 2:
        return 2
    if k == 3:
        return 3
    return (3 * third_order(k - 1)
            - 2 * third_order(k - 2)
            + third_order(k - 3))

print([third_order(k) for k in range(1, 9)])

前八项为 [1, 2, 3, 6, 14, 33, 77, 179]。这个直接实现也会重复求同一项，运行示例只使用小项号。

二维递推的边界修订

旧材料同时给出 f(0, n) = 1 和 f(m, 0) = m，在 (0, 0) 分别得到 1 和 0，存在冲突。这里明确修订第二条边界的适用范围：

• f(0, n) = 1，n ≥ 0；
• f(m, 0) = m，m ≥ 1；
• f(m, n) = f(m−1, n) + f(m, n−1) − f(m−1, n−1)，m, n ≥ 1。

因此采用 f(0, 0) = 1。这是本讲选择的无冲突版本，不是声称旧题原本就有唯一明确的含义。输入 m、n 均为非负整数。

def grid_value(m: int, n: int) -> int:
    if m == 0:
        return 1
    if n == 0:
        return m
    return (grid_value(m - 1, n)
            + grid_value(m, n - 1)
            - grid_value(m - 1, n - 1))

for m in range(5):
    print([grid_value(m, n) for n in range(5)])

先检查 m == 0，正确处理原点。输出五行分别全为 1、1、2、3、4。每个子问题的 m + n 都严格减少。

Ackermann 函数的小输入

对非负整数定义：

• A(0, n) = n + 1；
• A(m+1, 0) = A(m, 1)；
• A(m+1, n+1) = A(m, A(m+1, n))。

第三条先计算内层结果，再把该结果作为外层调用的参数，不能仅用“所有数字参数都减少”解释。

def ackermann(m: int, n: int) -> int:
    if m == 0:
        return n + 1
    if n == 0:
        return ackermann(m - 1, 1)
    return ackermann(m - 1, ackermann(m, n - 1))

for m, n in [(0, 1), (1, 1), (2, 2)]:
    print(m, n, ackermann(m, n))

结果为 2、3、7。终止性需要分层说明：固定较大的第一参数时，内层的第二参数下降；第一参数下降后，可以处理更大的第二参数。它并不保证实际解释器能承受所需深度。

此函数增长极快。本讲不运行巨大递归输入，例如 A(4, 2)，也不提高递归上限。公式给出 A(4, 2) = 2**65536 - 3；写出这个公式不等于已经完成该递归求值。

本机 turtle 与递归五角星

turtle 创建画笔窗口。forward(size) 沿当前方向前进，left(angle) 左转指定角度，position() 和 heading() 可分别查询位置和方向。它需要本机图形环境，以下代码不提供浏览器运行按钮。

import turtle

def star(pen, size: float) -> None:
    if size <= 10:
        return
    for _ in range(5):
        pen.forward(size)
        star(pen, size / 3)
        pen.left(216)

screen = turtle.Screen()
pen = turtle.Turtle()
pen.speed(0)
star(pen, 360)
screen.exitonclick()

这是往年代码的递归五角星，不是递归树。每走一条线段，在当前位置绘制较小的五角星，再转向下一条边。216° 的五次转向合计 1080°，结束时方向与开始时相同；子图的完整绘制也恢复原位置和方向。

size = 360 时，非基准层的边长为 360、120、40、40/3，下一层停止。共画 5 + 25 + 125 + 625 = 780 条线段，包含停止调用在内共 781 次函数调用。轨迹核验可用画笔替身完成，但不能据此声称已检查本机窗口的显示效果。往年的圆形自相似图片不是这段代码的输出。

插入法排列

主线先选择首项；另一种分解是先排列前 n−1 项，再把最后一项插入每个位置。插入不会丢失或覆盖已有项。

def permutations_by_insertion(items: list[int]) -> list[list[int]]:
    if len(items) == 0:
        return [[]]
    smaller = permutations_by_insertion(items[:-1])
    last = items[-1]
    result: list[list[int]] = []
    for p in smaller:
        for position in range(len(p) + 1):
            result.append(p[:position] + [last] + p[position:])
    return result

print(permutations_by_insertion([]))
print(permutations_by_insertion([1, 2, 3]))
print(len(permutations_by_insertion([1, 1, 2])))

这个枚举次序与主线不同。重复输入仍按位置处理，结果也可能重复。

字典序排列

字典序按第一个不同位置的元素比较序列。它不要求单个排列中的元素严格递增。对互异、升序输入，如果每层都从小到大选下一个元素，并先完整枚举当前分支，就能按字典序输出全排列。

def lexicographic_extensions(prefix: list[int],
                             remaining: list[int]) -> list[list[int]]:
    if len(remaining) == 0:
        return [prefix.copy()]
    result: list[list[int]] = []
    for i in range(len(remaining)):
        rest = remaining[:i] + remaining[i + 1:]
        result.extend(lexicographic_extensions(
            prefix + [remaining[i]], rest))
    return result

def lexicographic_permutations(items: list[int]) -> list[list[int]]:
    return lexicographic_extensions([], items)

for p in lexicographic_permutations([1, 2, 3]):
    print(p)

该示例不自动排序或去重；互异、升序是调用者提供的前提。往年标题中的 “Increasing permutations” 对应字典序全排列，不是严格递增组合。

k 排列与组合

从 n 个互异元素中选取 k 个：k 排列计顺序，组合不计顺序。例如，(1, 2) 与 (2, 1) 是不同排列，却代表同一个组合。下面使用标准库观察两种结果，0 ≤ k ≤ n。

from itertools import permutations, combinations

items = [1, 2, 3]
k = 2
ordered = list(permutations(items, k))
unordered = list(combinations(items, k))
print(ordered)
print(unordered)
print(len(ordered), len(unordered))
print(list(permutations(items, 0)))
print(list(combinations(items, 0)))

数量分别为 6 和 3；k = 0 时两者都只有一个空元组。递归扩展排列可以从所有未选元素中选择下一项；组合则固定候选的索引顺序，只从当前位置之后继续选择，避免把相同选择的不同顺序重复计算。

pprint 显示嵌套结果

pprint 是标准库中的格式化显示工具，适合嵌套列表等结果。它不改变本例列表的顺序，不去重，也不修改原数据。显示字典时，默认会按键排序；显示顺序与原字典的迭代顺序可能不同。

from itertools import permutations
from pprint import pprint

results = [list(p) for p in permutations([1, 2, 3])]
pprint(results, width=20)
print(len(results))

皇后的全排列枚举法

先枚举列号 0..n−1 的全排列，就已经保证每行和每列各有一个皇后。随后只检查对角线冲突。这是往年材料采用的另一种方法。

from itertools import permutations

def diagonals_clear(queens: tuple) -> bool:
    for row in range(len(queens)):
        for earlier in range(row):
            if abs(row - earlier) == abs(queens[row] - queens[earlier]):
                return False
    return True

n = 8
candidates = 0
solutions = 0
for queens in permutations(range(n)):
    candidates += 1
    if diagonals_clear(queens):
        solutions += 1
print(candidates, solutions)

输出为 40320 和 92，即检查 8! 个完整列号排列。主线的回溯在部分解产生冲突时就停止扩展，不必先生成所有完整候选。两种方法都应保留输入约定并核验结果；解的数量相同不表示计算过程相同。

用数组计算 Fibonacci

以下两个循环实现都接收非负整数项号 n。数组版本先处理零输入，再建立保存 F(0)..F(n) 的列表。若无条件写入 values[1]，n = 0 时会越界。

def fib_array(n: int) -> int:
    if n == 0:
        return 0
    values = [0] * (n + 1)
    values[1] = 1
    for i in range(2, n + 1):
        values[i] = values[i - 1] + values[i - 2]
    return values[n]

print([fib_array(n) for n in range(10)])

每项只算一次，但数组保存了所有前项。数组元素是越来越大的整数，不能把列表长度直接当作全部存储字节数。

用两个变量计算 Fibonacci

在第 i 次更新前，a = F(i)、b = F(i+1)；更新后，a = F(i+1)、b = F(i+2)。赋值先求右侧两个值，再更新左侧名字。

def fib_pair(n: int) -> int:
    a = 0
    b = 1
    for _ in range(n):
        a, b = b, a + b
    return a

print([fib_pair(n) for n in range(10)])
print(fib_pair(25))

这个版本只保留两个相邻项，不建立结果数组；两个整数对象的大小仍随项号增长。往年的双变量版本初值正确，需修正的是数组版本的零输入行为。

while 的状态更新

欧几里得算法也可用循环实现。每次更新后，当前 (a, b) 与递归下一层的参数相同。右侧使用更新前的两个值。

def gcd_loop(a: int, b: int) -> int:
    while b != 0:
        a, b = b, a % b
    return a

print(gcd_loop(48, 18))
print(gcd_loop(0, 5))

这是一个状态对的顺次更新，不需要保留未完成的外层运算。其他递归任务可能还要保存返回后继续执行的操作，不能据此断言所有递归都能如此直接改写。

硬币组合的子问题

Lab 7 的硬币题要求：金额为非负整数，面额互异且均为正整数，不计选取顺序。若面额为零，“使用该面额”不会减少金额；若面额重复，可能重复计数。

对当前面额，可以分为“使用一次，仍可继续使用该面额”与“不再使用，改用剩余面额”两个子任务。金额为零有一种空组合；正金额但没有面额时没有组合；允许递推到负金额时，该分支计零。

递减度量可以用“剩余金额 + 剩余面额种数”：使用正面额会减少金额，不用当前面额会减少种数。怎样组合两类计数、避免把硬币次序算成新方案，由实验自行实现。

相邻杆汉诺塔的推导结构

个人作业的相邻杆规则只允许 A ↔ B ↔ C，禁止 A ↔ C 的直接移动。普通汉诺塔程序中的最大盘直接端点移动在这里不合法，不能原样使用。

对于全部盘子从端点 A 转移到端点 C，分解结构为：三次 n−1 盘端点转移，穿插最大盘的两次相邻移动 A → B 和 B → C。每次移动最大盘前，需要先把小盘转移到不妨碍该移动的位置。

令端点转移的最少步数为 T(n)，可据此建立 T(0) = 0、T(n) = 3T(n−1) + 2，得到 T(n) = 3ⁿ−1。n = 0..5 的值为 0, 2, 8, 26, 80, 242。这只给出任务分解和步数关系，不是生成全部移动指令的实现。完整参数安排、序列构造、合法性核验与最少步数论证仍是作业任务。