第1章 递归问题

从汉诺塔、平面分割和Josephus问题提炼建立、展开与求解递推式的方法。

先做预测

先预测索引平移、初值改变、参数取边界或n增大时，精确值与近似值如何变化。从汉诺塔、平面分割和Josephus问题提炼建立、展开与求解递推式的方法。 本页用、、、和建立对象、变换、证书与误差闭环。

第二版权威目录定位

本页一一对应Graham、Knuth和Patashnik《Concrete Mathematics》第二版“第1章 递归问题”。出版社目录给出9个正式章节；作者官网确认1994年第二版、ISBN与657页，并说明新增机械求和内容。

原书小节覆盖

  1. The Tower of Hanoi
  2. Lines in the Plane
  3. The Josephus Problem
  4. Exercises

核心对象

  1. 递推式：用较小规模问题的值定义当前规模的值，并附带足够初值。
  2. 汉诺塔：移动nn个圆盘的最少步数满足Hn=2Hn−1+1H_n=2H_{n-1}+1。
  3. 平面分割：一般位置直线带来的新增区域数转化为一阶差分求和。
  4. Josephus问题：循环删除过程通过编号变换得到规模递减关系。
  5. 递归验收：同时核对初值、索引范围、展开式和小规模枚举。

先固定离散契约

公式前先写索引集合、初值、参数范围和边界约定。递推、取整、组合数和渐近式最常见的错误不是代数，而是少一项、从错误下标开始或在不合法参数上继续使用恒等式。

P=(index domain,initial values,parameters,boundary convention)\mathcal P=(\text{index domain},\text{initial values},\text{parameters},\text{boundary convention})

精确问题应先枚举最小规模：空集合、n为零、第一非平凡值和正好落在边界的值。小例子不能替代理论，但能尽早暴露符号和约定不一致。

可核查推导

Hn=2Hn−1+1, H0=0⟹Hn=2n−1H_n=2H_{n-1}+1,\ H_0=0\Longrightarrow H_n=2^n-1

把最大片移到目标柱之前，必须把其上n减1片移开；之后再把它们移到目标柱，因此最优步数是两个子问题加一步。减去常数负一或展开几何级数即可得到闭式。 每次换元都同步改上下界，每次交换求和都说明有限性或收敛条件，每次从精确式转为渐近式都保留余项。

def hanoi(n):
    return 0 if n==0 else 2*hanoi(n-1)+1
assert [hanoi(n) for n in range(6)]==[0,1,3,7,15,31]

代码与手算必须在至少五个连续规模上相符。只测一个点可能让两个不同序列偶然相等；还应加入边界和随机小规模穷举。

对象与变换链

递推式：用较小规模问题的值定义当前规模的值，并附带足够初值。

汉诺塔：移动nn个圆盘的最少步数满足Hn=2Hn−1+1H_n=2H_{n-1}+1。

平面分割：一般位置直线带来的新增区域数转化为一阶差分求和。

具体数学的核心是把离散对象在多种表示间切换：递推转求和，求和转差分，组合对象转生成函数，概率计数转指示变量，精确式转带余项的渐近式。每一步都要能逆向检查。

边界、反例与误差

Josephus问题：循环删除过程通过编号变换得到规模递减关系。

递归验收：同时核对初值、索引范围、展开式和小规模枚举。

边界集至少包括空和、空积、零规模、负参数、参数恰在端点、取模负数、重复根、发散级数和小n渐近失真。失败应明确指出哪个前提不成立。

e(n)=exact(n)−approx(n),∣e(n)∣≤B(n)e(n)=\text{exact}(n)-\text{approx}(n),\qquad |e(n)|\le B(n) 
audit={"exact":"enumerate small n","boundary":"zero and endpoint","counterexample":"只写递推关系却没有初值，导致无限多组序列都满足公式。","certificate":"replay transformations"}
assert set(audit)=={"exact","boundary","counterexample","certificate"}

算法案例

递归算法分析先从状态转移写递推，再用小规模枚举验证初值和偏移；闭式、递推计算与程序调用次数三路一致后才接受。 报告保存精确输入、索引域、中间恒等式、机械证书或组合解释、程序输出与误差界，保证他人能从头重算。

evidence=[("递推式","definition"),("平面分割","derivation"),("递归验收","certificate")]
assert len({name for name,_ in evidence})==3
  1. 写出索引域、初值和空对象约定，手算最小非平凡样例。
  2. 一次只做一种变换，保存边界项和前后等价关系。
  3. 删除一个假设构造反例，解释首个失败步骤。
  4. 对近似结论计算残差与误差界，并标明何时进入渐近区间。

验收证书

accept⁡=exact examples∧derivation∧counterexample∧error budget\operatorname{accept}=\text{exact examples}\land\text{derivation}\land\text{counterexample}\land\text{error budget}

证书拒绝孤立闭式。它应包含问题对象、精确关系、推导步骤、初值、机械或组合证据、小规模重放、反例和误差预算。

常见误区

本章回顾

本章覆盖递推式、汉诺塔、平面分割、Josephus问题、递归验收。掌握标准是能从对象建立精确式，逐步变换并保留边界，给出可重放证书，再说明近似误差和反例。

术语表

讨论

评论区加载中…