第十九章：递归与分治——拆解复杂问题的利器

递归这东西，我刚开始学的时候也觉得挺绕的。明明一个循环能搞定的事，干嘛要自己调用自己？直到我在项目中遇到一个多层嵌套的JSON解析问题，用循环写出来又臭又长，改用递归后，代码量直接砍掉三分之二。嗯，从那以后我就明白了——递归不是炫技，是实实在在的工程利器。

19.1 递归的概念与实现

说白了，递归就是函数调用自身。但有个关键点：必须要有终止条件。没有终止条件的递归，就是死循环，栈溢出等着你。

来看个最经典的例子——阶乘计算。你想想看，n! = n * (n-1)!，这不就是天然的递归结构吗？

// 递归实现阶乘
int factorial(int n) {
    // 终止条件：0! = 1
    if (n == 0 || n == 1) {
        return 1;
    }
    // 递归调用：n! = n * (n-1)!
    return n * factorial(n - 1);
}

这段代码看着简单，但执行过程其实挺有意思。假设调用 factorial(4)：

1. factorial(4) 调用 factorial(3)，等待结果
2. factorial(3) 调用 factorial(2)，等待结果
3. factorial(2) 调用 factorial(1)，等待结果
4. factorial(1) 返回 1
5. factorial(2) 得到 1，计算 2*1=2，返回 2
6. factorial(3) 得到 2，计算 3*2=6，返回 6
7. factorial(4) 得到 6，计算 4*6=24，返回 24

这个过程就像剥洋葱，一层层剥进去，再一层层返回来。我个人习惯把递归调用想象成「先递进，再回归」，这样好理解一些。

19.2 分治策略

分治，说白了就是「分而治之」。把一个大问题拆成几个小问题，分别解决，再把结果合并。递归是实现分治最自然的工具。

分治策略的通用步骤：

1. 分解：把原问题拆成若干个规模更小的子问题
2. 解决：递归地解决每个子问题
3. 合并：把子问题的解合并成原问题的解

最典型的分治算法就是归并排序。我记得第一次手写归并排序时，被它的递归过程绕得头晕。但后来画了个图，一下子就清晰了。

// 归并排序的分治实现
void mergeSort(int arr[], int left, int right) {
    // 终止条件：只有一个元素时，自然有序
    if (left >= right) {
        return;
    }
    
    // 分解：找到中间位置
    int mid = left + (right - left) / 2;
    
    // 解决：递归排序左右两半
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    
    // 合并：将两个有序子数组合并
    merge(arr, left, mid, right);
}

你想想看，归并排序为什么稳定？因为它在合并时，如果遇到相等的元素，总是先把左边的放进去。这个细节，我在面试时经常拿来考察候选人。

19.3 递归算法分析

分析递归算法，核心就是分析它的时间复杂度。常用的方法有两种：递推公式法和递归树法。

递推公式法：

以归并排序为例，它的递推公式是：T(n) = 2T(n/2) + O(n)。

怎么解？我教你一个口诀：「一层一层往下代，直到边界再回算」。

T(n) = 2T(n/2) + n
= 2[2T(n/4) + n/2] + n = 4T(n/4) + 2n
= 4[2T(n/8) + n/4] + 2n = 8T(n/8) + 3n
= ...
= 2^k * T(n/2^k) + k * n

当 n/2^k = 1 时，即 k = log₂n，T(1) = O(1)。
所以 T(n) = n * O(1) + n * log₂n = O(n log n)。

递归算法的空间复杂度：

这个很多人会忽略。递归调用会占用栈空间，每次调用都要压栈。所以递归深度决定了空间复杂度。比如阶乘的递归深度是 n，空间复杂度就是 O(n)。而归并排序的递归深度是 log n，空间复杂度就是 O(log n)。

19.4 递归转非递归

为什么要转非递归？两个原因：一是避免栈溢出，二是提高性能（函数调用有开销）。

递归转非递归的通用方法：用栈模拟函数调用栈。

来看个例子，把阶乘的递归改成非递归：

// 非递归实现阶乘
int factorial_iterative(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

这个简单，因为阶乘是尾递归，直接改成循环就行。但有些递归不是尾递归，比如二叉树的遍历，就需要用栈来模拟。

来看二叉树的先序遍历，递归版本：

void preorder(TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->val);  // 访问根节点
    preorder(root->left);      // 遍历左子树
    preorder(root->right);     // 遍历右子树
}

非递归版本，用栈模拟：

void preorder_iterative(TreeNode* root) {
    if (root == NULL) return;
    
    Stack* stack = createStack();
    push(stack, root);
    
    while (!isEmpty(stack)) {
        TreeNode* node = pop(stack);
        printf("%d ", node->val);
        
        // 注意：先压右子树，再压左子树
        // 因为栈是后进先出，要保证左子树先被访问
        if (node->right) push(stack, node->right);
        if (node->left) push(stack, node->left);
    }
    
    destroyStack(stack);
}

我曾经在优化一个XML解析器时，把深度优先的递归遍历改成了非递归。性能提升了40%，而且再也不用担心XML嵌套太深导致栈溢出了。嗯，这就是工程实践中的取舍。