第2章　递归关系

我们有兴趣进行分析的算法通常可以表示为递归或迭代过程。这意味着，一般可以把求解特定问题的开销用求解较小问题的开销来表示。正如在第1章中对Quicksort和Mergesort的分析中所见，对于这种情况，数学上最基本的处理方法是运用递归关系。这代表着一种实现方法，该方法实现了从程序的递归表示到描述其性质的函数的递归表示的直接映射。虽然递归分解仍然是问题的核心，但还有几种其他的方法能够做到这一点。在第3章中会看到，递归关系也是算法分析中母函数方法的应用基础。

因为递归本身携带大量信息，所以获取描述算法性能的递归关系是分析中的关键一步。与输入模型相关的算法的特定性质被封装于相对简单的数学表达式中。许多算法可能不适合这样简单的描述；但幸运的是，那些最重要的算法中有很多可以用递归公式简单地表示出来，而且其分析涉及递归，这些递归或者描述平均情况，或者确定最坏情况下性能的边界。这一点在第1章以及从第6章到第9章的许多例子中都有说明。本章关注各种递归的基本数学性质，但不考虑它们的起源或来历。其中涉及许多类型的递归，这些递归会在本章特定算法的研究中出现，另外还要重新审视第1章所讨论的递归，只不过现在关注的是递归本身。

首先，我们讨论递归的一些基本性质及其分类方式。然后研究“一阶”递归的准确解，在这里，n的函数表示为n-1的估计函数；我们还要研究高阶线性常系数递归的准确解。接下来分析其他各种类型的递归，并研究一些方法来推导某些非线性递归和非常系数递归的近似解。之后，我们将对分析算法中尤为重要的一类递归进行求解，即“分治”类递归。其中包括Mergesort递归的推导和准确解的求解，而这一递归涉及整数的二进制表示。最后研究适用于一大类分治算法分析的一般结果，并据此对本章内容进行总结。

迄今为止我们考虑的所有递归都有准确解。这种递归在算法分析中经常出现，尤其是用递归对离散量进行精确计数时。但准确解可能会涉及一些不相关的细节，例如，与近似解2n/3相比，(2n-(-1)n)/3这样的准确解也许太过烦琐而不推荐使用。在这种情况下，(-1)n项使答案以整数形式呈现，2n/3与2n相比可以忽略不计；而另一方面，2n(1+(-1)n)这样的准确解却不能忽略(-1)n项。在用精度换取简捷性的过程中，必须避免以下两种情况：一是过于粗心地忽略必要项，二是过分热心地保留非必要项。我们更倾向于得到简单且准确的近似表达式（即便有能力得到准确解）。此外，往往能遇到这样的递归，它的准确解是无法得出的，但可以估计解的增长率，而且在许多情况下能得出精确的渐近估计。

递归关系通常也叫作差分方程（difference equation），因为它们可以用离散差分算子▽fn≡ fn-fn-1表示。差分方程是常微分方程的离散模拟。求解微分方程的方法是相关的，因为类似的方法常常可用于求解相似的递归。下一章我们将会看到，在某些情况下存在明确的对应关系，依据这种对应关系就能通过微分方程的解求得递归的解。

存在大量与递归性质相关的资料，因为递归也直接出现于许多应用数学领域。例如，像牛顿法这样直接引出递归的数值迭代算法，在参考资料[3]中均有详细描述。

本章的目的是研究算法分析中常见的递归类型以及一些基本的求解方法。可以运用母函数（generating function）以严格而系统的方式处理许多这样的递归关系，第3章对此有详尽的讨论。第4章将详细研究能得到渐近近似的工具。在第6章到第9章中，会遇到许多不同的递归示例，这些递归关系描述了基本算法的性质。

一旦开始仔细研究高级工具，你就会发现，递归可能不是算法分析中最自然的数学工具。递归可能会使分析复杂化，但也可以通过使用更高层次的工具避免这种情况，即用符号法得到母函数之间的关系，然后对母函数直接进行分析。第5章会介绍这一内容，参考资料[12]对此有详细的论述。事实证明，在许多情况下，最简单直接的求解途径是避免递归。指出这一点并不是为了阻止对递归进行研究，恰恰相反，对于许多应用而言，递归可能是相当有成效的。但我们向读者保证，某些问题似乎会引发过度复杂的递归，但高级工具也许能为此类问题提供简单的求解方法。

简而言之，递归直接出现于算法分析的自然方法中，可以为许多重要问题提供简单的求解方法。因为后面的内容更注重研究母函数方法，所以此处我们只对涉及求解递归的资料中所提及的方法做简要介绍。关于求解递归的更多信息请查阅标准参考资料，其中包括参考资料[3]、[4]、[6]、[14]、[15]、[16]、[20]和[21]。