7. 跟踪递归代码¶
7.1. 跟踪递归代码¶
编写递归函数时，你应当自顶向下地思考。 不必担心递归调用是如何求解子问题的，只需接受它会正确求解这一点。 就像调用某个库函数一样使用这个结果，从而正确地求解原问题。
而当你需要阅读或跟踪一个递归函数时，你就确实需要考虑这个函数是如何开展工作的。 跟踪几个递归函数，是了解递归行为的好方法。 但等你熟练掌握了跟踪之后，就很少需要再如此细致地过一遍所有细节了。 你会开始对递归的工作方式建立起信心。
你已经知道，信息可以通过函数参数从一个递归调用传递给另一个递归调用，问题规模不断变小，直到在递进阶段（winding phase）到达基本情况。 然后，随着这一串递归调用逐步回归（unwinding），返回值被逐层传回。 人们有时会忘记回归阶段。
在递进阶段，通过递归调用传入的任何参数都一路向前流动，直到到达基本情况。 在回归阶段，函数的返回值（如果有的话）向后流回调用它的那份函数副本。 在下面的例子中，一个计算阶乘的递归函数在递进阶段信息向前流动，在回归阶段信息向后流动。
递归函数可能有不止一个参数携带信息流。 例如，一个对数组中的值进行递归求和的递归函数，可以在递进阶段通过递归调用传入数组本身和下标，并在回归阶段把到目前为止的求和值传回。
7.1.1. 多米诺骨牌类比¶
这种关于多米诺效应的递归模型，可以用作求解所有线性递归函数的模板。 把推倒每一张骨牌看作是朝着最终解又迈出的一步计算。 请记住以下规则：
第一张骨牌必须手动推倒，因此基本情况的解是非递归计算的。
任何一张骨牌要被推倒，它前面的所有骨牌都必须先倒下。
7.1.2. 汉诺塔¶
下面是递归的另一个例子，它基于一个名为"汉诺塔"（Towers of Hanoi）的著名谜题。 求解这个问题的自然算法包含多个递归调用。 它无法轻易地改写成用循环来实现。 "汉诺塔"源自一个古老的越南传说。 一群僧侣受命按照特定规则移动一座由 64 个大小不同的圆盘组成的塔。 传说称，当僧侣们移完所有圆盘之时，世界将会终结。
汉诺塔谜题从三根柱子和 \(n\) 个圆环开始，所有圆环最初都套在最左边的柱子上（标记为柱 A）。 每个圆环大小各不相同，按从大到小的顺序叠放，最大的圆环在最底部，如图 (a) 所示。 问题是要通过一系列步骤，把圆环从最左边的柱子移到中间的柱子（标记为柱 B）。 每一步都把某根柱子顶端的圆环移到另一根柱子上。 这个谜题的有趣之处在于对圆环移动位置的限制：圆环任何时候都不能放到比它小的圆环上面。
你该如何解决这个问题？ 如果不过分纠结细节，其实很容易。 换个思路：所有圆环都要从柱 A 移到柱 B。 不先把最底部（最大）的圆环移到柱 B，这件事就不可能完成。 要做到这一点，柱 B 必须为空，而柱 A 上只能留有最底部的圆环。 其余 \(n-1\) 个圆环必须按顺序叠放在柱 C 上，如图 (b) 所示。 这又该怎么做呢？ 假设有一个函数 \(X\) 可用于解决"把顶端 \(n-1\) 个圆环从柱 A 移到柱 C"的问题。 然后把最底部的圆环从柱 A 移到柱 B。 最后，再次使用函数 \(X\) 把其余 \(n-1\) 个圆环从柱 C 移到柱 B。 在这两种情形中，"函数 \(X\) "只不过是在问题的一个更小版本上调用汉诺塔函数而已。
成功的秘诀在于放心地让汉诺塔算法替你完成工作。 你不必操心汉诺塔子问题 究竟如何 被求解的那些繁琐细节。 只要做到两件事，问题自会解决。 第一，必须有基本情况（只有一个圆环时该怎么办），这样递归过程才不会永远进行下去。 第二，对汉诺塔的递归调用只能用来求解更小的问题，而且只能是形式正确的问题（在适当重命名柱子之后，符合汉诺塔问题原始定义的问题）。
下面是递归汉诺塔算法的一种实现。
函数 move(start, goal) 把柱 start 顶端的圆环取走，移到柱 goal 上。
如果 move 会打印其参数的值，那么调用 TOHr 的结果将是一串解决该问题的圆环移动指令。
// Compute the moves to solve a Tower of Hanoi puzzle.
// Function move does (or prints) the actual move of a disk
// from one pole to another.
// n: The number of disks
// start: The start pole
// goal: The goal pole
// temp: The other pole
static void TOHr(int n, Pole start, Pole goal, Pole temp) {
if (n == 0) { return; } // Base case
TOHr(n-1, start, temp, goal); // Recursive call: n-1 rings
move(start, goal); // Move bottom disk to goal
TOHr(n-1, temp, goal, start); // Recursive call: n-1 rings
}
// Compute the moves to solve a Tower of Hanoi puzzle.
// Function move does (or prints) the actual move of a disk
// from one pole to another.
// n: The number of disks
// start: The start pole
// goal: The goal pole
// temp: The other pole
static void TOH(int n, Pole start, Pole goal, Pole temp) {
if (n == 0) return; // Base case
TOH(n-1, start, temp, goal); // Recursive call: n-1 rings
move(start, goal); // Move bottom disk to goal
TOH(n-1, temp, goal, start); // Recursive call: n-1 rings
}
接下来的这个幻灯片讲解汉诺塔问题的解法。
