递归综合题：从状态定义推导递归式

递归题先定义函数“准确返回什么”，再写最小规模答案和规模缩小方式。以汉诺塔为例，move(n,A,B,C) 表示把 $n$ 个盘从 A 借助 B 移到 C：先把 $n-1$ 个从 A 移到 B，移动最大盘 A 到 C，再把 $n-1$ 个从 B 移到 C。

移动次数满足 $T(1)=1$，$T(n)=2T(n-1)+1$。展开得 $T(n)=2^n-1$，时间指数级，递归深度 $n$。不能把“函数里只有两次递归调用”写成 $O(n)$。

再看二分查找递归：每次只进入左右一半中的一边，递推为 $T(n)=T(n/2)+O(1)=O(\log n)$；虽然代码有两个分支文本，运行时只执行一个。复杂度由实际调用结构决定。

手工推演欧几里得算法 gcd(48,18)：gcd(18,12)、gcd(12,6)、gcd(6,0)，随后返回 6。状态中的第二个参数严格减小到 0，保证终止。若写成 gcd(a,b)=gcd(b,a%b)，还需约定非负输入或规范化符号。

递归正确性可用数学归纳法：假设对子规模调用正确，证明本层组合得到规模 $n$ 的正确结果，并验证基础情况。调试时记录“进入参数”和“返回值”，区分前序工作与回溯工作。

错解反馈：把两个分支都存在等同于都会执行；递推式写对却漏基础条件无法唯一求解；递归返回后忘记利用返回值，结果常停留在默认值。

迁移题：归并排序为何是 $T(n)=2T(n/2)+O(n)$？答案是递归处理两个半区，各规模 $n/2$，再线性合并；由主定理得 $O(n\log n)$。独立验收：能为汉诺塔、二分、归并分别画调用树的一层并写出递推式。