递归

  1. 效率上并非最佳方案
    但逻辑方面比迭代简洁
  2. 减而治之：将大的问题平凡与缩减成子问题
    平凡产生的子问题就是可以直接求解的简单问题
    缩减产生的子问题可以使用递归继续平凡与缩减，直到产生最小的平凡问题无法缩减 (递归基)
  3. 分而治之：将大的问题分为若干个子问题，规模大致相当
    分别求解子问题

递归跟踪

检查每个递归实例，累计所需时间 (递归调用语句本身计入对应的子实例)

// 数组倒置 递归版
void reverse(int* A, int lo, int hi) {
    if (lo < hi) {
        swap(A[lo], A[hi]);
        reverse(A, lo+1, hi-1);
    }
}

// 数组倒置 迭代版
void reverse(int* A, int lo, int hi) {
    while (lo < hi)
        swap(A[lo++], A[hi--]);
}

递推方程

// 数组求和
int sum(int A[], int n) {
    return (n < 1) ? 0 : sum(A, n-1) + A[n-1];
}

$$\begin{cases}T(n)=T(n-1)+O(1) \ T(0) = O(1) \end{cases}$$

两侧同时减 $n$，$$T(n) - n = T(n-1) - (n-1) = … = T(1) - 1 = T(0)$$

故 $$T(n) = O(1) + n = O(n)$$