11. 实现递归¶

警告！除非你已经能够熟练地实现 recursive 函数，否则不应阅读本节。 学生学习递归时最大的障碍之一，是过分关注递归的"过程"。 思考递归的正确方式是只思考递归调用返回的值。 去思考那个答案 如何 计算出来，只会妨碍理解。 理解递归是如何实现的确实有充分的理由，但帮助你编写递归函数并不在其中。

也许最常见的、使用 stacks 的计算机应用甚至对用户不可见。 这就是大多数编程语言 运行时环境 中子例程调用的实现。 子例程调用通常是通过把子例程的必要信息（包括返回地址、参数和局部变量）:term:入栈 <push> 来实现的。 这些信息称为 活动记录 。 进一步的子例程调用会往栈上添加内容。 每次从子例程返回时，都会从栈顶 出栈 一个活动记录。 作为一个例子，下面是阶乘函数的一个递归实现。

// Recursively compute and return n!
static long rfact(int n) {
  // fact(20) is the largest value that fits in a long
  if ((n < 0) || (n > 20)) { return -1; }
  if (n <= 1)  { return 1; }  // Base case: return base solution
  return n * rfact(n-1);   // Recursive call for n > 1
}

下面是内部处理过程如何工作的图示。

\(\beta\) 值表示当前函数调用完成后要返回的程序指令地址。 每次对 fact 进行递归函数调用时，返回地址和 n 的当前值都必须保存。 每次从 fact 返回时，都会从栈顶弹出一个活动记录。

考虑用值 4 调用 fact 时会发生什么。 我们用 \(\beta\) 表示发出 fact 调用的程序指令地址。 因此，栈必须首先存储地址 \(\beta\) ，值 4 被传递给 fact 。 接下来，对 fact 进行一次递归调用，这次传入的值为 3。 我们把发出该调用的程序地址命名为 \(\beta_1\) 。 地址 \(\beta_1\) 连同 \(n\) 的当前值（即 4）一起保存在栈上。 函数 fact 以输入参数 3 被调用。

以类似的方式，又用输入参数 2 进行了一次递归调用，这要求把发出调用的地址（记为 \(\beta_2\) ）和 \(n\) 的当前值（即 3）存储在栈上。 最后用输入参数 1 进行一次递归调用，这要求栈存储调用地址（记为 \(\beta_3\) ）和当前值（即 2）。

此时，我们已经到达 fact 的基本情况，于是递归开始展开。 每次从 fact 返回都涉及从栈中弹出所存储的 \(n\) 值以及函数调用的返回地址。 fact 的返回值与恢复的 \(n\) 值相乘，然后返回结果。

因为每次子例程调用都必须创建一个活动记录并将其放入栈中，所以进行子例程调用是相对昂贵的操作。 虽然递归常常被用来让实现变得简单清晰，但有时你可能想消除递归函数调用带来的开销。 在某些情况下，例如上面的阶乘函数，递归可以很容易地用迭代来替代。

阶乘函数的迭代形式比示例中所示的版本既更简单也更快。 但并非总能以迭代替代递归。 在实现需要多次分支的算法（例如汉诺塔算法）时，或者在 traversing a binary tree 时，递归或对它的某种模仿是必要的。 Mergesort 和 Quicksort 排序算法 也需要递归。 幸运的是，总是可以用栈来模仿递归。 现在我们来看汉诺塔函数的一个非递归版本，它无法用迭代方式完成。

当描述一个子问题所需的信息量很小时，递归算法很适合用栈来高效实现。 例如，Quicksort 可以有效地用栈来替代其递归，因为只需要保存待处理子数组的边界信息。