第十五单元：汉诺塔 · 递归思想与栈的堆叠

在 Kelvintaph 冰川最高峰的僧侣中,流传着一个既能取暖又能锻炼头脑的古老游戏:三根柱子,一根上按从大到小叠着一摞圆盘,要把整摞盘子搬到另一根柱子上——一次只能搬一个,而且永远不能把大盘压在小盘上面。你的冒险队没有真正的柱子和圆盘,那就用这些身材各异的农民和三个树桩来玩吧!这个看似简单的搬运游戏,正是计算机科学中最经典的递归范例:汉诺塔(Tower of Hanoi)。作为封神冰川的终极试炼,它会让你真正领悟"递归"这一优雅而强大的思想。

15.1.1 什么是汉诺塔（What Is the Tower of Hanoi）

15.1.1.1 三根柱子间搬移一摞圆盘 Move a stack of disks among three pegs

汉诺塔是一个数学谜题:有三根柱子(记作起点、目标、中转),起点柱上叠着 n 个大小不一的圆盘,大的在下、小的在上。目标是把这 n 个圆盘全部搬到目标柱,搬完后依然保持"大在下、小在上"的顺序。它之所以在计算机科学中如此重要,是因为它用递归解决极其简洁,用非递归(循环)却相当繁琐——是理解递归思想的绝佳教材。

15.1.2 三条规则（The Three Rules）

15.1.2.1 简单的规则，深刻的挑战 Simple rules, deep challenge

汉诺塔的规则只有三条,却让问题充满智慧:① 一次只能移动一个圆盘;② 每次只能移动某根柱子最顶端的圆盘;③ 任何时候都不能把大盘放在小盘之上。在本关里,这三条对应:一次只能带一个农民、只能取树桩顶端的农民、不能把大农民压在小农民身上。

15.2.1 柱子就是栈（A Peg Is a Stack）

15.2.1.1 只能从顶端存取的数据结构 A structure you can only access from the top

每根柱子(树桩)本质上就是一个栈(stack)——一种只能从顶端存取的数据结构。你只能看到、取走最顶端的圆盘,底下的都被压住无法直接触及。栈遵循后进先出(LIFO, Last In First Out)规则:最后放上去的,最先被取下来。汉诺塔的每根柱子,都完美体现了栈的这一特性。

15.2.2 大盘不压小盘（Never Stack Big on Small）

15.2.2.1 栈顶总是最小的圆盘 The top is always the smallest disk

由于规则限制"大不压小",每根柱子(栈)在任意时刻,从下往上都是严格递减的:越靠底越大、越靠顶越小,栈顶永远是这根柱子上最小的圆盘。这条约束保证了移动的合法性——你 dropItem 放盘时,放上去的必须比目标柱顶端的盘更小。理解这一点,就明白为什么递归要"先把小盘们清走"。

15.3.1 pickUpItem 出栈（pickUpItem as pop）

15.3.1.1 拿起顶端 = 从栈弹出 Picking up the top = popping the stack

关卡提供的 hero.pickUpItem(container) 会拾取容器顶端(最后一个)的物品——这正是栈的 pop 操作:它把目标柱的栈顶元素弹出,并压入英雄自己的手(英雄可看作一个只能拿一个盘的临时栈)。一次只能拿一个,对应"一次只移动一个圆盘"的规则。

# pickUpItem = pop:从目标柱弹出顶端圆盘,拿在手上
hero.pickUpItem(stump1)   # 取走 stump1 栈顶的农民

15.3.2 dropItem 入栈（dropItem as push）

15.3.2.1 放下 = 压入栈顶 Dropping = pushing onto the top

hero.dropItem(container) 则把英雄手上的圆盘放到目标容器顶端——这是栈的 push 操作:从英雄的手弹出,压入目标柱的栈顶。pickUpItem 与 dropItem 成对出现,一取一放,就完成了"把一个圆盘从一根柱子移到另一根柱子"的完整动作。

# 一次完整的圆盘移动 = pop + push
hero.pickUpItem(who)    # pop:从 who 柱取顶端盘
hero.dropItem(whom)     # push:放到 whom 柱顶端

15.3.3 peekItem 与 viewStack（Peek and View）

15.3.3.1 只看不取的观察工具 Look without taking

关卡还提供两个"只读"工具:peekItem() 返回栈顶(最后一个)物品但不移除它;viewStack() 返回整个栈的物品数组(索引 length-1 是栈顶)。农民还有 size 属性表示其规模。这些用于观察当前局面、调试或验证——比如查看某柱顶端农民的尺寸,确认移动是否合法。

# 观察工具:peek 看栈顶, viewStack 看整个栈
hero.say("第1柱有这些农民:" + stump1.viewStack())
hero.say("第2柱顶端农民尺寸:" + stump2.peekItem().size)

15.4.1 分而治之（Divide and Conquer）

15.4.1.1 把大问题变成同类的小问题 Turn a big problem into a smaller same-shaped problem

递归(recursion)是"函数调用自己"来解决问题的方法。它的核心是分而治之:把一个大问题,转化成一个或多个结构相同、规模更小的子问题。汉诺塔就是递归的完美化身——"移动 n 个盘"可以借助"移动 n-1 个盘"来完成。只要你能把 n-1 个盘搬来搬去,搬 n 个盘就迎刃而解。

15.4.2 基线条件与递归条件（Base Case and Recursive Case）

15.4.2.1 递归必须有终点 Recursion must have a stopping point

每个递归都必须包含两部分:基线条件(base case)——问题小到可以直接解决、停止递归的情形;递归条件(recursive case)——把问题缩小、调用自身的情形。在汉诺塔里,基线条件是 n == 0(没有盘要搬,直接 return);递归条件则是 n ≥ 1 时的三步搬运。没有基线条件,递归会无限调用下去直到崩溃。

# 递归的两大要素
def hanoi(n, who, whom, via):
    if n == 0:       # 基线条件:没有盘,停止
        return
    # 递归条件:调用自己解决更小的问题(见 15.5)

15.5.1 三步递归（The Three-Step Recursion）

15.5.1.1 移上面、移最大、再移上面 Move the top n-1, move the biggest, move the top n-1 again

汉诺塔的完整递归解法只有优雅的三步:① 把上面 n-1 个盘从起点(who)借助目标(whom)当中转,移到中转柱(via);② 把最底下那个最大的盘,从起点(who)直接搬到目标(whom)——这一步就是 pickUpItem + dropItem;③ 把那 n-1 个盘从中转柱(via)借助起点(who)当中转,移到目标柱(whom)。三步之后,n 个盘全部就位。

# 汉诺塔的经典三步递归
def hanoi(n, who, whom, via):
    if n == 0:
        return
    hanoi(n - 1, who, via, whom)   # ① 上面 n-1 个:起点 → 中转
    hero.pickUpItem(who)            # ② 最大盘:
    hero.dropItem(whom)             #    起点 → 目标
    hanoi(n - 1, via, whom, who)   # ③ 那 n-1 个:中转 → 目标

15.5.2 参数角色轮换（Rotating the Roles of Parameters）

15.5.2.1 起点、目标、中转在递归中互换身份 Source, target, and spare swap identities in recursion

递归解法最精妙、也最烧脑的地方,是三根柱子的角色在每层递归里互相轮换。函数签名 hanoi(n, who, whom, via) 里,who 是当前的起点、whom 是目标、via 是中转。第一步递归 hanoi(n-1, who, via, whom) 里,原来的"目标 whom"临时充当了"中转";第三步 hanoi(n-1, via, whom, who) 里,原来的"中转 via"变成了新的"起点"。正是这种角色轮换,让同一个函数能处理每一层不同的搬运方向。

15.6.1 2ⁿ − 1 步（Two to the n, Minus One）

15.6.1.1 盘数每加一，步数几乎翻倍 Each extra disk nearly doubles the moves

汉诺塔搬 n 个盘的最少移动次数是 2ⁿ − 1 步。因为搬 n 个盘 = 搬 n-1 个 + 搬 1 个 + 再搬 n-1 个,即 T(n) = 2·T(n-1) + 1,展开正好是 2ⁿ − 1。本关搬 5 个农民,就需要 2⁵ − 1 = 31 步。这个指数增长非常惊人:传说中 64 个金盘的"梵天之塔",需要约 1800 亿亿步,即使每秒一步也要几千亿年。

这一节聚焦关卡的策略、思路与算法设计,只展示用于说明的关键片段,完整通关程序请你自己动手完成。

第 32 关 · Kelvintaph 柱子

🗼 Kelvintaph 柱子 —— 用递归搬运一摞农民

图2：Kelvintaph 柱子——三个树桩当柱子、身材不一的农民当圆盘,用汉诺塔递归把整摞农民从起点树桩搬到目标树桩

策略:把农民当圆盘、树桩当柱子,套用汉诺塔递归

三个树桩 stump1/2/3 就是三根柱子,身材从大到小叠放的农民就是圆盘。规则完全对应:一次只带一个农民、只能取树桩顶端的、不能把大农民压在小农民上。策略非常清晰:识别出这是汉诺塔问题,写一个递归函数 hanoi,再用起点、目标、中转三个树桩调用它。递归会自动生成合法的 31 步搬运顺序。

思路拆解一:定义递归函数骨架

函数 hanoi(n, who, whom, via) 表示"把 who 上的 n 个农民搬到 whom,via 作中转"。先写基线条件 if n == 0: return(没有农民要搬就结束),这是防止无限递归的关键。然后是三步递归主体。

# 关键片段:递归函数骨架 + 基线条件
def hanoi(n, who, whom, via):
    if n == 0:   # 基线:没有农民要搬,直接返回
        return
    # 递归主体(见下)…

思路拆解二:三步搬运的递归主体

主体严格按"移上面 n-1、移最大、再移上面 n-1"三步展开。中间那步用 pickUpItem(who) 取起点树桩顶端农民、dropItem(whom) 放到目标树桩,正是"移动一个圆盘"的实现。两侧的递归调用注意参数角色的轮换——中转与目标/起点互换。

# 关键片段:三步递归主体
    hanoi(n - 1, who, via, whom)   # ① 上面 n-1 个 → 中转
    hero.pickUpItem(who)            # ② 取最大农民
    hero.dropItem(whom)             #    搬到目标
    hanoi(n - 1, via, whom, who)   # ③ 中转的 n-1 个 → 目标

思路拆解三:用三个树桩发起调用

最后一行是"点火"——hanoi(5, stump1, stump2, stump3),意思是"把 stump1 上的 5 个农民搬到 stump2,用 stump3 作中转"。传入 5 是因为有 5 个农民;三个树桩的顺序决定了起点、目标、中转。一句调用,整个 31 步的搬运便自动展开。

# 关键片段:发起递归(起点, 目标, 中转)
hanoi(5, stump1, stump2, stump3)

递归自动保证合法：你可能担心某一步会不会把大农民压到小农民上——不会。只要严格按这个递归结构执行,每一步 dropItem 时目标树桩顶端要么为空、要么是更大的农民,大压小的非法情况绝不会发生。这是汉诺塔递归解法数学上被证明的正确性,你只管信任它。

两处递归调用的参数别写错：本关最容易错的就是两个 hanoi(n-1, …) 里三个树桩参数的顺序。第一步是 (who, via, whom)、第三步是 (via, whom, who)——中转与目标/起点的轮换必须精确,写反一个,搬运顺序就乱了、会触发非法移动。对照 15.5.2 的角色轮换表逐一核对。

15.8.1 新手最容易踩的坑（Pitfalls for Beginners）

15.8.1.1 递归与汉诺塔的典型问题 Typical issues with recursion and Hanoi

图3：忘写基线条件、递归参数顺序写错、pickUp 与 drop 不配对、试图手动跟踪每步,是本单元最常见的失误