2.3 递归式求解
当一个算法包含对自身的递归调用时，其运行时间通常可以用递归式（Recurrence）来表示。递归式是一组等式或不等式，它所描述的函数是用在更小的输入下该函数的值来定义的。例如归并排序算法的最坏情况运行时间T(n)可以由下面的递归式
表示，其解为T(n)=Θ(n⋅lgn)。
下面将介绍如何解递归式，即找出解的渐进“Θ”或“O”界的方法。解递归式的方法主要有代换法（Substitution Method）、递归树方法（Recursion-Tree Method）与主方法（Master Method）。下面我们将主要介绍主方法。
在给出主方法定义之前，首先对一些技术细节进行说明。在表达和解递归式时常常略去一些技术性细节。例如，常常假设函数的自变量为整数，另外一个容易忽略的细节是边界条件，因为对于固定规模的输入来说，算法的运行时间为常量，故对足够小的n来说，表示算法运行时间的递归式一般为T(n)=Θ(1)。据此，为了方便起见，就常忽略递归式的边界条件，并且假设n值足够小时T(n)是常量。
主方法给出了递归式T(n)=a⋅T(n/b)+f(n)的边界，其中a≥1，b>1，f(n)是给定的函数。T(n)=a⋅T(n/b)+f(n)描述了将规模为n的问题划分为a个子问题的算法的运行时间，每个子问题规模为n/b，a和b是正常数。a个子问题被分别递归地解决，时间各为T(n/b)。划分原问题和合并答案的代价由函数f(n)描述。主方法主要依赖于下面的定理：
定理2.2（主定理）设a≥1，b>1为常数，设f(n)为一函数，T(n)由递归式
T(n)=a⋅T(n/b)+f(n)
对非负整数进行定义，其中n/b指
或
。那么T(n)可能有如下的渐进界：
1）若存在常数ε>0，使得
，则
；
2）若
，则
；
3）若存在常数ε>0，使得
，且对常数c＜1与所有足够大的n，有a⋅f(n/b)≤cf(n)，则T(n)=Θ(f(n))。
在定理2.2的三种情况中，每一种情况都把函数f(n)与函数
进行比较。直觉上感觉解是由两个函数中较大的一个决定。在第一种情况中，不仅要有
，还必须是多项式地小于（即对某个常量ε>0，f(n)必须渐进地小于
，两者差一个因子nε）。在第三种情况中，不仅要有
，还必须是多项式地大于（即对某个常量ε>0，f(n)必须渐进地大于
，两者之间相差一个因子nε），还要满足规则性条件“a⋅f(n/b)≤cf(n)”。
要注意这三种情况并没有覆盖所有可能的f(n)。当
，但不是多项式地小于时，就在第一种情况和第二种情况中存在一条“空隙”。同样当
，但不是多项式地大于时，就在第三种情况和第二种情况中存在一条“空隙”。如果f(n)处于以上两种情况中的任一种，那么主方法就不能用于解递归式。
现在来看一个例子，设某一算法的时间复杂度用递归式可以表示为：
T(n)=9T(n/3)+n
那么，在这个递归式中，a=9，b=3，f(n)=n，则
。因为
，其中ε=1，这对应主定理中的第一种情况，因此答案为T(n)=Θ(n2)。
再看一个例子，设某一算法的时间复杂度用递归式可以表示为：
那么，在这个递归式中，a=9，b=3/2，f(n)=1，则
。第二种情况成立，因为
，故递归式的解为T(n)=Θ(lg n)。
设某一算法的时间复杂度用递归式可以表示为：
那么，在这个递归式中，a=3，b=4，f(n)=n⋅lg n，
。因为f(n)=
，其中ε≈0.2。如果能证明对f(n)第三种情况中的规则性条件成立，那么就可以选用定理2.2中的第三种情况，因此递归式的解为T(n)=Θ(n⋅(lg n))。