2.1
基本性质

第1章分析Quicksort和Mergesort时，我们遇到过以下三种递归：

（1）

（2）

（3）

每个方程都表示特定的问题。在方程两边同时乘以适当的因子，可以求解方程（1）；先求出特殊情况 的解，然后用归纳法证明 N 为一般值时的解，由此可得出方程（2）的近似解；用 种情况下的同一方程式减去（3），即可把方程（3）转换为方程（1）。

这种特殊技巧可能代表了求解递归经常需要的“智囊”。但刚刚提及的为数不多的“智囊”技巧却并不适用于许多常见的递归问题，其中包括著名的线性递归：

该递归关系定义了斐波那契（Fibonacci）数列{0,1,1,2,3,5,8,13,21,34,…}。斐波那契数经过人们的深入研究，实际上已经明确用于许多重要算法的设计和分析。本章考虑了求解这类递归以及其他递归的一些方法，而且在第3章以及后续章节中我们还会考虑其他适用的系统性方法。

可根据以下特点对递归进行分类：各项的组合方式、所涉及系数的性质以及所用的前面各项的数量和性质。表2.1列举了将要研究的一些递归及其典型示例。

值的计算

在正常情况下，递归为计算问题中的量提供了一种有效的方法。尤其是求解任意递归的第一步都是先用该递归计算很小的数值，并据此感受递归是如何增长的。若要完成这个步骤，可以徒手计算一些很小的数值，也可以设计一个简单的程序来计算相对较大的值。

例如，对应递归关系（3），程序2.1能够计算Quicksort平均比较次数的准确值，其中 N 小于或等于maxN。该程序用一个大小为maxN的数组存储前面算出的数值。应该避免直接使用基于递归的纯递归程序，即通过递归地计算所有 C _{N -1} , C _{N -2} ,…, C ₁ 的值最终得到 C _N 。该方法的效率极其低下，因为许多值会被不必要地重复计算。

程序2.1　计算值（Quicksort递归）

如果像程序2.1那样即可满足条件，那么就需要避免过于深入地研究数学。我们认为简单的数学求解方法更为可取——实际上，我们把分析本身视为一种能够使程序2.1更加有效的处理！无论如何，这种求解方法可以用于验证分析。另一个极端做法是对所有可能的输入都运行程序，据此计算该程序的平均运行时间，然而这是一种蛮力（通常是不切实际的）方法。

习题 2.1 分别编写递归程序和非递归程序来计算斐波那契递归的值，并用每个程序都计算一次 F ₂₀ 。解释在这种情况下每个程序的性能。

习题2.2 当函数中 N 取值为 N _max 时，程序2.1进行了多少次算术运算？

习题2.3 编写一个直接使用递归关系（1）的程序来计算其值。与程序2.1（见习题2.2）相比，该程序使用的算术运算次数如何？

习题 2.4 如果用递归关系（2）和（3）计算其值，请估计递归程序和非递归程序分别需要多少次运算？

习题2.5 编写一个程序比较Quicksort、其三项中值变体和基数交换排序，从第1章给出的递归中求值。对于Quicksort，检查与已知解相对的值；对于其余两种算法，猜想解的性质。

缩放和平移

递归具有一个基本性质，即依赖于初始值：若存在线性递归

将初始条件 改为 ，该操作会改变 的值，其中 n 为所有可能值（若 ，则 的值都将增加一倍）。“初始”值可以出现在任何地方：若存在递归关系

则一定存在 。改变初始值叫作 缩放 （scaling）递归；移动初始值叫作 平移 （shifting）递归。最常见的情况是由问题内容直接得出初始值，但常用缩放或平移简化求解过程。我们不是在陈述递归的解的最一般形式，而是在求解一种自然形式，并假设解可以适当地缩放或平移。

线性

通过独立地改变初始值并对解进行组合，具有多于一个初始值的线性递归可以实现“缩放”。若 是一个线性方程，且 ，则

（初始值是 和 的函数）的解为 乘以

时，

的解，加上 乘以

时，

的解。条件 使该递归成为 齐次 （homogeneous）递归：如果 f 中有常数项，那么必须考虑这个常数项和 f 的初始值。直接把任意 t 阶线性齐次递归（对于任意一组初始值）的通解视为 t 个特解的线性组合。第1章用该过程求解了描述Quicksort所用交换次数的递归，其结果用描述比较次数和阶段数的递归表示。

习题2.6 求解递归

时，

用斐波那契数表示得到的答案。

习题2.7 求解非齐次递归

时，

用斐波那契数表示得到的答案。

习题2.8 对于线性函数 f ，将递归

的解用 、 、 以及 对于 、 和 、 的解表示。 eXz6XTrf/UO0NCgYsEYUCq4ItBwQPUx9bhinyAG3PNHxo/XrUcjiV132UMtmZ2po