线性递归模式，往往对应于减而治之（decrease-and-conquer）的算法策略：
递归每深入一层，待求解问题的规模都缩减一个常数，直至最终蜕化为平凡小的问题。
案例1：数组求和之线性递归
算法实现：
int sum(int n)
{
if(n == 0)
return 0;
return sum(n - 1) + n;
}
算法分析：
- 时间复杂度：
O(n) - 空间复杂度：
O(n)
案例2：数组倒置
问题描述：
考查数组倒置问题， 也就是将数组中各元素的次序前后翻转。 比如，若输入数组为：
A[] = { 3, 1, 4, 1, 5, 9, 2, 6 }
则倒置后为：
A[] = { 6, 2, 9, 5, 1, 4, 1, 3 }
算法思路：
为得到整个数组的倒置，可以先对换其首、末元素，然后递归地倒置除这两个元素以外的部分。
算法实现：
#include <iostream>
using namespace std;
void reverse(int *A, int lo, int hi)
{
if(lo < hi)
{
int t = A[lo];
A[lo] = A[hi];
A[hi] = t;
reverse(A, lo + 1, hi - 1);
}
}
void reverse(int *A, int n)
{
reverse(A, 0, n - 1);
}
int main()
{
int A[8] = { 3, 1, 4, 1, 5, 9, 2, 6 };
int n = 8;
reverse(A, n);
for(int i = 0; i < n; i++)
cout << A[i] <<" ";
cout << endl;
return 0;
}
算法分析：
- 时间复杂度：
递归跟踪法：
递归跟踪图
从中可以清楚地看出，每递归深入一层，入口参数lo和hi之间的差距必然缩小2，因此递归深度（亦即时间复杂度）为：(hi - lo) / 2 = n/2 = O(n)
递推方程法：
- 将处理长度为n的数组所需时间成本记为T(n)。
- 为解决长度为n的数组，需递归解决长度为n - 2的数组，以及两个元素的交换。
可得一般性的递推关系：
T(n) = T(n - 2) + O(1) = T(n - 2) + c ，其中c为常数 - 抵达递归基时，求解平凡问题需要常数时间（返回），即可获得如下边界条件：
T(1) = T(0) = O(1) = c'， 其中c'为常数
T(n) = T(n - 2) + c （1）
T(1) = c' （2）//n为奇数
使用 n - 2 替换(1)式中的 n，得：
T(n - 2) = T(n - 4) + c （3）
T(n) + c = T(n - 2) + 2c
T(n) + c = T(n - 4) + c + 2c //使用(3)式做等价替换
T(n) + c = T(n - 4) + 3c = T(n - 6) + 4c = T(n - 8) + 5c
T(n) + c = ...
T(n) + c = T(1) + [(n - 1)/2 + 1]c
T(n) + c = c' + [(n + 1)/2]c
T(n) = [(n - 1)/2]c + c'
T(n) = O(n)
- 空间复杂度：
O(1)
