第 2 章 算法分析
2.10 线性递归
以 014 节的例题 2.9.1 为例，用递归方式表示阶乘，函数式为：
f(n)={1if n=0n⋅f(n−1)if n>0begin{split}
f(n)=begin{cases}1&quad if~n=0\ncdot f(n-1)&quad if ~ngt0end{cases}
end{split}f(n)={1n⋅f(n−1)if n=0if n>0
对应的算法描述是：
long factorial(int n){
if(n == 0){
return 1;
} else {
return n * factorial(n - 1);
}
}
在此算法描述中，即使用了递归。对此递归的分析如下：
- 满足算法的“有穷性”要求：首先判断
n == 0的条件，满足此条件时，return 1，即终止递归的条件或基准情形，从而避免递归无限进行下去。 n * factorial(n - 1)使得递归朝着基准情形进行自我调用（不断推进），且每一递归实例对自身的调用为一次（合成效益法则），即 f(n),f(n−1),f(n−2),⋯ ,f(1),f(0)f(n),f(n-1),f(n-2),cdots,f(1),f(0)f(n),f(n−1),f(n−2),⋯,f(1),f(0) ，从而构成了一个线性的次序关系，因此称这类递归模式为线性递归。这是递归的最基本形式。
线性递归的模式，是实现减治算法（（decrease and conquer））的一种策略，即：递归每深入一层，待求解问题的规模都缩减一个常数，直至最终达到基准情形。
例题 2.10.1 用递归方式，计算给定 nnn 个整数的总和
在 011 节的例题 2.6.3 中，用迭代的方式实现了计算给定 nnn 个整数的总和的问题，此处用递归方式实现：
int sum(int A[], int n){ //数组求和算法（线性递归版）
if (n < 1) //基准情形
return 0;
else
return sum(A, n-1) + A[n - 1]; //递归：前 n-1 项之和，再累计第 n-1 项
}
1. 递推公式
以例题 2.10.1 为例，说明递归的时间复杂度的一种常用分析方法：递推公式法。
假设计算长度为 nnn 的数组中各个数字之和的时间复杂度是 T(n)T(n)T(n) ，那么计算长度为 n−1n-1n−1 的数组中各个数字之和的时间复杂度就是 T(n−1)T(n-1)T(n−1) 。根据上述算法中的第 5 行，sum(A, n-1) + A[n - 1] 的结果为 sum(A, n) ，而计算 A[n - 1] 的时间复杂度是常数阶，即：
T(n)=T(n−1)+O(1)=T(n−1)+c1(1)T(n) = T(n-1)+O(1)=T(n-1)+c_1tag{1}T(n)=T(n−1)+O(1)=T(n−1)+c1(1)
当到达基准情形时，即计算 sum(A, 0) 时，直接返回 000 ，return 0; ，时间复杂度也是常数阶 O(1)O(1)O(1) ，即：
T(0)=O(1)=c2(2)T(0)=O(1)=c_2tag{2}T(0)=O(1)=c2(2)
其中，（1）式和（2）式中的 c1,c2c_1,c_2c1,c2 均为常数。
由（1）式得：
T(n)=T(n−1)+c1=T(n−2)+c1+c1=T(n−2)+2c1=T(n−3)+c1+2c1=T(n−3)+3c1⋯=T(1)+(n−1)c1=T(0)+c1+(n−1)c1=T(0)+nc1(代入(2)式)=c2+nc1=O(n)begin{split}
T(n)&=T(n-1)+c_1
\&=T(n-2)+c_1+c_1=T(n-2)+2c_1
\&=T(n-3)+c_1+2c_1=T(n-3)+3c_1
\&quadcdots
\&=T(1)+(n-1)c_1
\&=T(0)+c_1+(n-1)c_1=T(0)+nc_1quad(代入(2)式)
\&=c_2+nc_1=O(n)
end{split}T(n)=T(n−1)+c1=T(n−2)+c1+c1=T(n−2)+2c1=T(n−3)+c1+2c1=T(n−3)+3c1⋯=T(1)+(n−1)c1=T(0)+c1+(n−1)c1=T(0)+nc1(代入(2)式)=c2+nc1=O(n)
递推法，是一种常用的方法。
在本节对应的练习题中，可以使用递归公式，对阶乘算法计算其时间复杂度。
2. 递归跟踪分析
对于线性递归而言，对递归过程进行跟踪，并不是很复杂的过程，因此也可以通过跟踪过程分析时间复杂度。
以例题 2.10.1 为例，其算法执行过程如图 2.10.1 所示：
图 2.10.1
- 首先调用参数 nnn ，再转向 n−1,n−1,⋯0n-1,n-1,cdots 0n−1,n−1,⋯0 ，直到参数为 000 ，到达了终止条件，不再递归。
- 将基准情形的解（长度为 0 数组的总和 0）返回给对参数 1 的调用；累加上 A[0] 之后，再返回给对参数 2 的调用；累加上 A[1] 之后，继续返回给对参数 3 的调用；...；如此依次返回，直到最终返回给对参数 n 的调用，此时，只需累加 A[n - 1] 即得到整个数组的总和。
从上述过程可知，每一个递归实例中非递归部分涉及到三类计算：① 判断 nnn 是否为 0；② 累加 sum(n-1) 和 A[n - 1] ；③ 返回当前的和。并且，在一个递归实例中，这三类计算各执行一次。它们也都是基本操作。所以，每个递归实例的运行时间是常数阶 O(1)O(1)O(1) 。
结合图 2.10.1 可知，共计有 n+1n+1n+1 个递归实例，即递归深入为 n+1n+1n+1 ，所以整个算法的时间复杂度是：T(n)=(n+1)×O(1)=O(n)T(n)=(n+1)times O(1)=O(n)T(n)=(n+1)×O(1)=O(n) 。
