递归与分治算法思想

一、递归的本质

1.1 什么是递归

函数调用自身，将大问题分解为相似的子问题。

1.2 递归三要素

1. 终止条件：何时停止递归
2. 递归关系：问题如何分解为子问题
3. 返回值：子问题的解如何组合

1.3 递归的执行过程

f(n) → f(n-1) → f(n-2) → ... → f(1) → 返回
   ↑        ↑         ↑              ↑
  组合    组合      组合           基础解

二、递归的数学基础

2.1 递推关系

[ T(n) = a \cdot T(n/b) + f(n) ]

2.2 主定理(Master Theorem)

用于分析分治算法的时间复杂度：

若 ( T(n) = aT(n/b) + O(n^d) )

[ T(n) = \begin{cases} O(n^d) & \text{if } d > \log_b a \ O(n^d \log n) & \text{if } d = \log_b a \ O(n^{\log_b a}) & \text{if } d < \log_b a \end{cases} ]

2.3 应用示例

• 归并排序：( T(n) = 2T(n/2) + O(n) )，( a=2, b=2, d=1 )，( T(n) = O(n \log n) )
• 二分查找：( T(n) = T(n/2) + O(1) )，( T(n) = O(\log n) )

三、递归 vs 迭代

特性	递归	迭代
代码	简洁	可能较复杂
空间	栈空间 ( O(n) )	常数或自定义
效率	有函数调用开销	通常更快
适用	树、分治、回溯	线性遍历

3.1 尾递归优化

// 普通递归
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

// 尾递归
int factorialTail(int n, int acc) {
    if (n <= 1) return acc;
    return factorialTail(n - 1, n * acc);
}

尾递归可被编译器优化为迭代，避免栈溢出。

四、分治算法框架

4.1 通用模板

Result divideAndConquer(Problem problem) {
    if (problem is small enough) {
        return solveDirectly(problem);
    }
    
    // 分解
    List<Problem> subProblems = divide(problem);
    
    // 解决
    List<Result> subResults = new ArrayList<>();
    for (Problem sub : subProblems) {
        subResults.add(divideAndConquer(sub));
    }
    
    // 合并
    return merge(subResults);
}

五、经典分治问题

5.1 归并排序

已在前文详述，分治三步：分、排序、合并。

5.2 快速排序

分治三步：选pivot、分区、递归排序。

5.3 求数组中的最大子数组和

public int maxSubArray(int[] nums) {
    return maxSubArray(nums, 0, nums.length - 1);
}

int maxSubArray(int[] nums, int left, int right) {
    if (left == right) return nums[left];
    
    int mid = left + (right - left) / 2;
    int leftMax = maxSubArray(nums, left, mid);
    int rightMax = maxSubArray(nums, mid + 1, right);
    int crossMax = maxCrossingSum(nums, left, mid, right);
    
    return Math.max(Math.max(leftMax, rightMax), crossMax);
}

int maxCrossingSum(int[] nums, int left, int mid, int right) {
    int sum = 0, leftSum = Integer.MIN_VALUE;
    for (int i = mid; i >= left; i--) {
        sum += nums[i];
        leftSum = Math.max(leftSum, sum);
    }
    
    sum = 0;
    int rightSum = Integer.MIN_VALUE;
    for (int i = mid + 1; i <= right; i++) {
        sum += nums[i];
        rightSum = Math.max(rightSum, sum);
    }
    
    return leftSum + rightSum;
}

( O(n \log n) )，优化后可用动态规划做到 ( O(n) )。

六、递归常见问题

6.1 栈溢出

递归深度过大导致StackOverflowError。

• 解决：转换为迭代，或增加栈大小

6.2 重复计算

斐波那契递归存在大量重叠子问题。

• 解决：记忆化搜索或动态规划

6.3 记忆化搜索

int[] memo;

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

七、总结

递归是算法的核心思想之一，分治是其最重要的应用。理解递归的数学基础（递推关系、主定理），掌握分治的三步框架（分解-解决-合并），能够系统化解决复杂问题。对于存在重叠子问题的递归，记忆化搜索是优化关键。