1.3 迭代与递归

数组求和 - 迭代
问题：计算任意n个整数之和
实现：逐一取出每个元素进行累加

int sum(int arr[], int n) {
    int result = 0;
    for (int i = 0; i < n; i++)
        result += arr[i];
    return result;
}

T(n) = O(n²)

Decrease-and-conquer，为求解一个大规模的问题，可以将其划分为两个子问题，一为平凡，一为规模缩减，分别求解子问题，由子问题的解，得到原问题的解。

数组求和 - 线性递归

int sum(int arr[], int n)
    return (n < 1) ? 0 : sum(arr, n - 1) + arr[n - 1];

递归跟踪(recursion trace)分析，检查每个递归实例累计所需时间（调用语句本身，计入对应子实例），总和即算法执行时间。
求解sum(arr, n)，需递归求解规模为n - 1的问题sum(arr, n - 1)，并累加arr[n - 1]。递归基sum(arr, 0)。
T(n) = T(n - 1) + O(1)
T(0) = O(1)
T(n) = O(1) * (n + 1) = O(n)

数组倒置
将任意数组arr[0, n)倒置

void reverse(int* arr, int lo, int hi);

// 递归，问题规模奇偶性不变，需要两个递归基
if (lo < hi) {
    swap(arr[lo], arr[hi]);
    reverse(arr, lo + 1, hi - 1);
}

// 迭代
while (lo < hi) {
    swap(arr[lo++], arr[hi--]);
}

Divide-and-conquer，为求解一个大规模的问题，将其划分为若干规模相当的子问题分别求解，由子问题的解得到原问题的解。

数组求和：二分递归

sum(int[] arr, int lo, int hi) {
    if (lo == hi)
        return arr[lo]
    int mi = (lo + hi) >> 1;
    return sum(arr, lo, mi) + sum(arr, mi + 1, hi);
}

T(n) = O(1) * (2^{logn + 1} - 1) = O(n)
求解sum(arr, lo, hi)，需递归求解sum(arr, lo, mi)与sum(arr, mi + 1, hi)，并将子问题的解累加。递归基sum(arr, lo, lo)。
T(n) = 2 * T(n / 2) + O(1)
T(1) = O(1)

Max2问题
求数组区间arr[lo, hi)中最大的两个整数arr[x1]与arr[x2]

// 迭代
void max2(int[] arr, int lo, int hi, int &x1, int &x2) { // 1 < n = hi - lo
    for (x1 = lo, int i = lo + 1; i < hi; i++) // 扫描arr[lo, hi)，得到arr[x1]
        if (arr[x1] < arr[i])
            x1 = i; // hi - lo - 1 = n - 1
    for (x2 = lo, int i = lo + 1; i < x1; i++) // 扫描arr[lo, x1)
        if (arr[x2] < arr[i])
            x2 = i; // x1 - lo - 1
    for (int i = x1 + 1; i < hi; i++) // 扫描[x1, hi)，得到arr[x2]
        if (arr[x2] < arr[i])
            x2 = i; // hi - x1 - 1
}

// 迭代
void max2(int[] arr, int lo, int hi, int &x1, int &x2) { // 1 < n = hi - lo
    if (arr[x1 = lo] < arr[x2 = lo + 1]
        swap(x1, x2);
    for (int i = lo + 2; i < hi; i++)
        if (arr[x2] < arr[i])
            if (arr[x1] < arr[x2 = i])
                swap(x1, x2);
}

// 递归
void max2(int[] arr, int lo, int hi, int &x1, int &x2) {
    if (lo + 2 == hi) {
        /* 仅有2个元素 */
        x1, x2 = (arr[lo] > arr[hi - 1]) ? (lo, hi - 1) : (hi - 1, lo);
        return;
    }
    if (lo + 3 == hi) {
        /* 仅有3个元素 */
        x1, x2 = (arr[lo] > arr[lo + 1]) ? (lo, lo + 1) : (lo + 1, lo);
        if (arr[x2] < arr[hi - 1]) {
            x2 = hi - 1;
            if (arr[x1] < arr[x2])
                swap(x1, x2);
        }
        return;
    }
    int mi = (lo + hi) /2;
    int x1L, x2L;
    max2(A, lo, mi, x1L, x2L);
    int x1R, x2R;
    max2(A, mi, hi, x1R, x2R);
    if (arr[x1L] > arr[x1R]) {
        x1 = x1L;
        x2 = (arr[x2L] > arr[x1R]) ? x2L : x1R;
    } else {
        x1 = x1R;
        x2 = (arr[x1L] > arr[x2R]) ? x1L : x2R;
    }
}