2.2
一阶递归

也许最简单的递归类型可以直接简化为乘积。递归

等价于

于是，若 ，则 ；若 ，则 ，等等。

这个变换是 迭代 （iteration）的一个简单示例：将递归应用于自身，直至只剩下常数和初始值为止，然后化简。迭代也直接适用于下一种最简单的递归类型，而这类递归更加常见，可直接简化为求和式：

它等价于

所以，若 ，则 ；若 ，则 ，等等。

表2.2列举了一些常见的离散和。除此之外，还可以在标准参考资料里找到更全面的列表，如参考资料[13]或参考资料[22]。

习题2.9 求解递归

习题2.10 求解递归

如果递归不是这么简单的，我们往往可以在递归的两边同时乘以一个适当的因子，从而完成对递归的化简。第1章我们已经讨论过这样的例子。例如，先在式（1）两边同时除以 N +1，得到一个 形式的简单递归，然后经迭代将其直接变换为一个求和式，即可实现求解式（1）。

习题2.11 求解递归

（提示：两边同时乘以 。）

习题2.12 求解递归

（提示：两边同时除以2 ⁿ 。）

用上述方法求解递归关系（差分方程）与求解微分方程的过程类似，即先乘以积分因子，然后积分。用于递归关系的因子有时叫作 求和因子 （summation factor）。适当选择求和因子有助于求解许多实际工作中出现的递归。例如，Knuth就是用这样的技巧 ^[17] （也可见参考资料[23]）得到了描述三项中值Quicksort平均比较次数的递归的准确解。

定理2.1（一阶线性递归） 递归

有显式解

证明：等式两边同时除以 ，然后迭代，得到

相同的结果也可以通过另一种方法得到，即在等式两边同时乘以 （假设它是收敛的），然后迭代。

例如，定理2.1的证明说明要求解递归

应该在等式两边同时除以

这恰恰是我们在1.5节所做的。另外，解

也可以根据定理给出的显式解形式直接得到。

定理2.1完整地展现了把常系数或变系数一阶线性递归转换为求和式的过程。求解递归的问题简化为了求解求和式的问题。

习题2.13 求解递归

习题2.14 以 x 、 y 和初始值 的形式写出

的解。

习题2.15 求解递归

习题2.16 求解递归

，当 时 ）

习题2.17 [Yao]（“2-3树的边缘分析[24]”）求解递归

该递归描述了以下随机过程：将一组元素（ N 个）分成“2-节点”和“3-节点”。在每个步骤中，每个2-节点以概率2/ N 转化为一个3-节点；每个3-节点以概率3/ N 转化为两个2-节点。那么经过 N 个步骤之后，2-节点的平均个数是多少？ 6qRQMfuGejRoAczJik85MsjNMa4ZmB5MEiTdKFeWq6tBBKkDkTwOu5WOuaocEC7K