笔记14-《程序员的数学》递归  

目录
  1. 递归
  2. 用 Ruby 验证
  3. 这一章其实在讲「分解」

递归

  • 汉诺塔

    • 问题设定

      • 把套在 A 柱上的 6 个圆盘全部移到 B 柱
      • 规则：一次只能移动柱子最上端的一个圆盘；小圆盘上不能放大圆盘
      • 求最少移动次数

    • 先缩小问题规模（提示：先从小汉诺塔着手）

      • 一开始就考虑 6 层会头脑混乱，先找 3 层的解法
      • 3 层汉诺塔经过多次尝试可找到移动 7 次的解法

    • 发现规律

      • 在来回移动圆盘的过程中会觉得「在重复做相似的事情」
      • 之所以产生这种感觉，是因为我们有「发现规律的能力」—— 这种感觉很重要
      • 移动 2 个圆盘从 A 到 C 是 3 次，移动 2 个圆盘从 C 到 B 也是 3 次
      • 「移动 2 个圆盘」这个动作本身就是「2 层汉诺塔」的解法

    • 递归结构

      • 解 n 层：把 n-1 个移到中转柱 → 移动最大盘 1 次 → 把 n-1 个从中转柱移到目标柱
      • 用 x（起点）、y（目标）、z（中转）代替 A/B/C，因为三者会不固定地对应
      • 当 n = 0 时什么都不做

    • 最少性证明

      • 要把最大的圆盘从 A 移到 B，必须先把上面的 5 个圆盘都移到 C
      • 因此这个递归解法就是移动次数最少的解法

    • 解析式

      H(n)=2n−1H(n) = 2^n - 1

      • 观察 0、1、3、7、15、31、63 都是「2 的幂减 1」

      • 只使用 n 表示 H(n) 的式子叫解析式，可以用数学归纳法证明

  • 阶乘的递归定义

    • n!=n×(n−1)!n! = n \times (n-1)!，其中 0!=10! = 1
    • 0!=10! = 1 是定义，不是推导 —— 它的作用是让递归链条能启动

  • 和的定义

    • 递归与归纳是同一件事的两种视角
      • 归纳：从 n=0 的基底出发，逐步推向 n
      • 递归：从 n 出发，退回到 n-1

  • 斐波那契数列

    • 不断繁殖的动物问题
      • 第 n-1 天出生的动物在第 n 天还活着
      • 第 n-2 天以前出生的动物在第 n 天会繁殖 1 个后代
      • 所以第 n 天的总数 = 第 n-1 天 + 第 n-2 天
    • 数列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
      • 13 世纪由 Leonardo Fibonacci（1170–1250）发现，故名
      • 也常以 1 开头：1, 1, 2, 3, 5, …
    • 递推公式中把一块砖头都没有的摆法（n=0）算作「1 种」情况，公式才成立
    • 出现在鹦鹉螺内壁间隔、葵花种子排法、植物枝叶长法、爬 n 层阶梯（一次走 1 阶或 2 阶）里
    • 创作旋律：用 4 分音符和 2 分音符打 n 拍，可打出 F(n+1) 种节奏
      • 先打 4 分音符 → 剩余 n-1 拍的情况数
      • 先打 2 分音符 → 剩余 n-2 拍的情况数

  • 帕斯卡三角形（杨辉三角）

    • 相邻两数之和得出下一行的数

    • 用组合数表示会出现很多阶乘，但仅通过反复计算「相邻两数之和」就能得出 —— 着实让人大吃一惊

    • 组合数的递归定义

      Cnk={1(n=0 或 n=k)Cn−1k−1+Cn−1k(0<k<n)C_n^k = \begin{cases} 1 & (n = 0 \text{ 或 } n = k) \\ C_{n-1}^{k-1} + C_{n-1}^{k} & (0 < k < n) \end{cases}

    • 左边出现 n、k，右边出现 n-1、k-1 —— 与汉诺塔、阶乘的递归模式非常相似

    • 组合的数学理论解释

      • 「n 中选 k 的组合数」= 「n-1 中选 k-1 的组合数」+「n-1 中选 k 的组合数」
      • 用格子路线问题理解：从起点到终点的走法数

  • 发现递归结构的要领

    • 从 n 层的整体问题中隐去部分问题
    • 判断剩余部分是否是 n-1 层的问题
    • 隐去自己着眼的树枝，剩余部分就是缩小的树枝
    • 本章所有问题（数学归纳法、汉诺塔、阶乘、组合数）都具有递归结构
    • 关注特定部分，便可发现剩余部分和自身具有相同的结构

  • 递归图形

    • 以递归形式画树：树枝有左右两个分叉，每个分叉又连接着与树本身一样的结构
    • 谢尔平斯基三角形（Sierpinski gasket）
    • 编程中常见的递归结构：源代码缩进、树形数据结构、XML 语法、快速排序算法

用 Ruby 验证

# 汉诺塔：递归解法与移动次数
def hanoi(n, x, y, z, moves = [])
  return moves if n == 0
  hanoi(n - 1, x, z, y, moves)
  moves << "#{x}->#{y}"
  hanoi(n - 1, z, y, x, moves)
  moves
end

# 递归求最少移动次数
def hanoi_count(n)
  return 0 if n == 0
  2 * hanoi_count(n - 1) + 1
end

puts "H(0)=#{hanoi_count(0)}"
(1..10).each { |n| puts "H(#{n})=#{hanoi_count(n)}" }

# 验证解析式 H(n) = 2^n - 1
(0..10).each do |n|
  raise "不一致 n=#{n}" unless hanoi_count(n) == 2**n - 1
end
puts "解析式 H(n)=2^n-1 全部验证通过"

m3 = hanoi(3, "A", "B", "C")
puts "3层移动次数 = #{m3.size}"
puts "序列: #{m3.join(' ')}"
puts "6层移动次数 = #{hanoi(6, "A", "B", "C").size}"

输出：

H(0)=0
H(1)=1
H(2)=3
H(3)=7
H(4)=15
H(5)=31
H(6)=63
H(7)=127
H(8)=255
H(9)=511
H(10)=1023
解析式 H(n)=2^n-1 全部验证通过
3层移动次数 = 7
序列: A->B A->C B->C A->B C->A C->B A->B
6层移动次数 = 63

H(3)=7 与书上「移动 7 次可解决问题」一致，6 层 63 次。

这一章其实在讲「分解」

作者在最后的课后对话里点破了：

学生：把握结构是关键吧？
老师：对！非常关键！
学生：为什么呢？
老师：因为把握结构是「分解」整个问题的突破口。

递归不是一种编程技巧，是一种分解方式。三个步骤在汉诺塔、阶乘、斐波那契、帕斯卡三角形里完全通用：

  1. 找出基底 —— n = 0 时做什么（汉诺塔不动、0!=10! = 1、砖头 0 种算 1 种）

  2. 确认剩余部分是同类问题 —— 规模缩小了，但结构没变

  3. 写出递归式 —— 把原问题拆成同类问题的组合

而 0!=10! = 1 这个「反直觉」的定义，在这一章有了完整解释：它不是为了凑公式，是为了让递归链条能启动。这正是上一章笔记13 里那个「推倒不了第一张多米诺骨牌」的延续 —— 定义是为了让链条跑通，而不是因为它「自然」。

帕斯卡三角形那一段最值得反复看：组合数可以写成 n!k!(n−k)!\frac{n!}{k!(n-k)!} 这种满是阶乘的式子，但只靠「相邻两数相加」也能算出来。同一个对象的两种表述，一条要阶乘，一条只要加法 —— 而递归的那条更好用。

学习  :分类
 :标签
123.8k