下载掌阅APP，畅读海量书库
立即打开
利用 递归 技术，能将一个问题转化为同一个样子问题的求解过程。这是我最喜欢的经典的递归例子：计算 n ！（“ n 的阶乘”），它被定义为如下，对于一个非负数 n ，当 n =0时， n ！=1且 n ！= n ·（ n -1）·（ n -2）·（ n -3）…3· 2·1（如果 n ≥1）。例如，5！=5·4·3·2·1=120。观察得（ n -1）！=（ n -1）·（ n -2）·（ n -3）…3·2·1，并且得 n ！= n ·（ n -1）！（对于 n ≥1）。针对 n ！这个问题，我们定义了“较小的”问题，也就是（ n -1）！。我们能够写出一个递归程序来计算 n ！，具体如下：
程序 FACTORIAL（ n ）
输入： 一个整数 ， n ≥0。
输出： n ！ 的值 。
1. 如果 n =0， 那么返回 1 作为输出 。
2. 否则 ， 返回递归调用 FACTORIAL（ n -1） 的 n 倍 。
第2步的表达方式过于啰嗦。我可以将其改写为“Otherwise,return n ·FACTORIAL（ n -1）”[否则，返回 n ·FACTOR2AL（ n -1）]，即在一个更大的算术表达式中使用递归调用的返回值。
对于递归，我们必须强调两个特性。首先，必须有一个或多个 基础情况 （base case），它是指不用递归而直接计算出结果。第二，程序中的每个递归调用一定是通过一系列关于 同一问题 的 子问题 的求解而最终迭代到基础情况。对于FACTORIAL程序，当 n 等于0时，基础情况发生，并且每一个递归调用最终均会将 n 归约到1。只要初始时 n 是非负的，递归调用最终均会归约到基础情况。
证明递归算法工作流程的第一步可能让人感觉过于简单。证明的关键是每次递归调用均会产生正确的结果。只要我们愿意相信递归调用确实得到了正确结果，那么证明正确性通常是容易的。如下是我们如何证明FACTORIAL程序返回了正确的结果。很明显，当 n =0时，结果返回1，1等价于 n ！。假定当 n ≥1时，FACTORIAL（ n -1）这个递归调用返回了正确的结果：它返回了（ n -1）！。该程序再用 n 乘以该值，因此计算出了 n ！这一结果，也就是最后要返回的值。
下面举一个程序，虽然它利用了正确的数学公式计算，但它不是基于子问题求解的递归调用。当 n ≥0时，确实有 n ！=（ n +1）！/（ n +1）。下列递归程序虽然利用了该数学公式，但是未能得出正确的结果（当 n ≥1时）：
程序 BAD-FACTORIAL（ n ）
输入、输出： 与 FACTORIAL 的输入 、 输出相同 。
1. 如果 n =0， 那么返回 1 作为输出 。
2. 否则 ， 返回 BAD-FACTORIAL（ n +1）/（ n +1）。
如果要调用BAD-FACTORIAL（1），那么它会产生一个递归调用BAD-FACTORIAL（2），该递归调用会产生一个递归调用BAD-FACTORIAL（3），等等，这一系列递归调用均不会归约到基础情况（即 n =0事件）。如果要用一种实际编程语言来实现该程序并且将该程序运行到一个真正的计算机上，那么你会很快就能看到一条“栈溢出错误”的错误信息。
我们通常能将算法表示成一种递归风格的循环方式。如下是一个线性查找算法，它没有使用标记，而是使用递归方式书写的：
程序 RECURSIVE-LINEAR-SEARCH（ A , n , i , x ）
输入： 与 LINEAR-SEARCH 的相同 ， 额外再加上一个参数 i 。
输出： 从 A [ i ] 到 A [ n ] 的子数组中元素值等于 x 的索引 ， 或者 NOT-FOUND（ 如果 x 没有在子数组中出现 ）。
1. 如果 i > n ， 那么返回 NOT-FOUND。
2. 否则 （ i ≤ n ）， 如果 A [ i ]= x ， 那么返回 i 。
3. 否则 （ i ≤ n 并且 A [ i ]≠ x ）， 返回 RECURSIVE-LINEAR-SEARCH（ A , n , i +1, x ）。
这里，子问题是在 A [ i ]～ A [ n ]这个子数组中寻找 x 的问题。基础情况发生在第1步中即当子数组本身是空时，也就是当 i > n 时。因为每执行一次第3步的递归调用，如果没有第2步中的值返回， i 的值就会自增一，那么最后 i 会大于 n ，此时我们会执行基础情况。