递归专题 · 个人项目 A 启动

本次目标

• 把递归的两个要素变成肌肉记忆
• 亲手做一次”递归 vs 循环”的对照
• 理解回溯的基本套路
• 启动个人项目 A

基础题

7-1 递归数位数

实现 count_digits(n: int) -> int，用递归数出非负整数有几位。

count_digits(0)     →  1
count_digits(7)     →  1
count_digits(12345) →  5

7-2 递归反转字符串

实现 reverse_string(s: str) -> str。不许用 [::-1]、reversed() 或循环。

reverse_string("")      →  ""
reverse_string("a")     →  "a"
reverse_string("hello") →  "olleh"

7-3 回文判断

实现 is_palindrome(s: str) -> bool，用递归判断字符串是否正读反读一样。

is_palindrome("")      →  True
is_palindrome("a")     →  True
is_palindrome("abba")  →  True
is_palindrome("abc")   →  False

7-4 压平嵌套列表

实现 flatten(items: list) -> list[int]，把任意深度的嵌套列表压成一维。

flatten([1, [2, [3, [4]]]])      →  [1, 2, 3, 4]
flatten([])                       →  []
flatten([[], [1], [[2], [3]]])    →  [1, 2, 3]

7-5 递归 vs 循环

用两种写法分别实现”求各位数字之和”：

• sum_digits_rec(n: int) -> int：递归
• sum_digits_loop(n: int) -> int：循环（你在 Lab 4 写过）

然后在提交说明里回答：

1. 哪个更短？哪个更好懂？
2. 用 n = 10**1000（一千位的数）分别跑一下，会发生什么？为什么？

7-6 数硬币的组合

给定面额列表和一个金额，用递归数出有多少种凑法（不计顺序）。

def count_ways(amount: int, coins: list[int]) -> int:
    ...

count_ways(5, [1, 2, 5])    →  4     # 5 / 2+2+1 / 2+1+1+1 / 1×5
count_ways(0, [1, 2, 5])    →  1     # 什么都不选，算一种
count_ways(3, [2])          →  0

---

个人项目 A：汉诺塔可视化

占总成绩 7.5%（个人项目 A 与 B 合计 15%） 截止：下周日 23:59

背景

你在 Lab 4 用循环算过汉诺塔的最少步数，在 L7 用递归解出了完整的移动过程。这个项目把它做完整。

要求

实现一个模块，包含以下函数（签名必须一致，平台按此调用）：

def hanoi_moves(n: int) -> list[tuple[int, str, str]]:
    """返回移动步骤列表，每项是 (盘子编号, 从哪根柱子, 到哪根柱子)。
    柱子用 "A" "B" "C" 表示，起点 A，终点 C。"""

def is_valid_sequence(n: int, moves: list[tuple[int, str, str]]) -> bool:
    """检验一个移动序列是否合法：每次只动一个盘子、
    不把大盘压在小盘上、最终所有盘子都在 C 上。"""

def render(n: int, moves: list[tuple[int, str, str]]) -> str:
    """把整个过程画成文本，返回一个多行字符串。"""

分项

报告要求

一份 不超过一页 的说明，回答三个问题：

1. is_valid_sequence 你设计了哪些检查？ 每一条对应什么样的非法情况？
2. render 你为什么选择这种画法？ 你考虑过但放弃了什么方案？
3. n 最大能到多少？ 实际试一下，说明是什么限制了它——是时间、内存、还是递归深度？

提交前自查

• 六道基础题都有类型提示
• 7-1 用 n = 0 测过
• 7-3 的两个 base case 都处理了
• 7-5 的两个问题在提交说明里回答了
• 项目 A：三个函数签名与要求一致
• 项目 A：is_valid_sequence 用非法序列测过
• 项目 A：报告三个问题都回答了