递归：
1. 减而治之：
要解决大规模问题，一个是平凡，另一个是缩减
分别求解子问题
从子问题的解中，得到原问题的解
相加：线性递归
intsum(inta (，int n ) ) return ) n1？ 0:sum(a，n-1 ) A[n-1]； }
反转数组：
给定数组A[0，n]，前后相反
统一接口： voidreverse(int*a，int lo，int hi ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) )。
voidreverse(int*a，int lo，int hi ) if ) lohi ) swap ) A[hi]，A[hi]； reverse(a，lo 1，hi - 1 )； (} //else暗示了两个递归基。 其余元素为最小偶数0或最小基数3358www.Sina.com/
为了求一个大问题，可以将其分成几个(通常为两个)子问题，规模大致为2. 分而治之
分别求解子问题
从子问题的解中，得到原问题的解
加法：二分递归
intsum(inta (，int lo，int hi ) if ) lo==hi ) /递归基returna )； intmi=(lohi )/2； returnsum(a，lo，mi ) sum ) a，mi 1，hi )； }
相当
从排列区间迭代：中找到最大的两个整数A[x1]和A[x2]
voidmax2(inta[]，int lo，int hi，int x1，int x2 ) ) for ) x1=lo，int i=lo 1； i hi； I () if ) a[x1]a[I] ) x1=i； }for(x2=lo，int i=lo 1； i x1； I () if ) a[x2]a[I] ) x2=i； }for(intI=x11； i hi； I () if ) a[x2]a[I] ) x2=i； }复杂度分析：
比较次数一定为2n - 3；
改进1 :
voidmax2(inta (，int lo，int hi，int x1，int x2 ) ) if ) a ) x2=lo ) a ) x1 ) x1=lo1 ) ) swap ) x1，x2 )； for(intI=lo2； i hi； I () if ) a[x1]a[I] ) if ) a[x2]a[x1=I] ) swap ) x1，x2 )； }最佳案例：1(n-2 )1=n - 1； *
最坏情况：1(n-2 )2=2n - 3； //没有实质性的改善
改进A[lo, hi)递归分治
递归：分别找出左右2个区间的最大值和第二大的值，通过比较这4个值的大小，决定数组整体的最大值和第二大的值
区间要素连续或为三个的情况。
voidmax2(inta )、int lo、int hi、int x1、int x2 ) /仅两个元素时if(lo1==hi ) (if ) a(lo ) a ) hi ) ) x1=a ) ) 返回； } else { x1=A[hi]； x2=A[lo]； 返回； () /只有三个元素时if ) lo2==hi ) if ) a[lo]a[lo1] ) { x1=A[lo]； x2=A[lo 1]； if(a ) hi ) x2 ) { x1=x2； x2=A[hi]； 返回； (else ) if ) a[hi]a[lo] ) { x1=A[hi]； 返回； } } } else { x1=A[lo 1]； x2=A[lo]； if(a ) hi ) x2 ) { x1=x2； x2=A[hi]； 返回； (else ) if ) a[hi]x1 ) { x1=A[hi]； 返回； }}//**4个以上元素按分治递归分为以上2种情况**intmid=(lohi )/2； int x1L、x2L、x1R、x2R； max2(a，lo，mid，x1L，x2L )； max2(a，mid 1，hi，x1R，x2R )； if(a ) x2L ) a(x2R ) ) { x2=x2L； x1=A[x1L] A[x2R]？ x1L : x2R； 返回； } else { x2=x2R； x1=A[x1R] A[x2L]？ x1R : x2L； 返回； }