【数据结构与算法】第46篇：算法思想（一）：递归与分治

一、递归的本质

1.1 什么是递归

递归就是函数调用自身。一个递归函数通常包含两部分：

• 终止条件：什么时候停止递归

• 递推公式：如何将大问题转化为小问题

c

// 阶乘的递归实现 int factorial(int n) { if (n <= 1) return 1; // 终止条件 return n * factorial(n - 1); // 递推公式 }

1.2 递归的底层原理：系统栈

每次函数调用，系统都会在栈上分配空间，存储：

• 函数的参数

• 局部变量

• 返回地址

当函数调用结束时，栈帧被弹出，程序回到调用点继续执行。

以 factorial(3) 为例：

text

调用 factorial(3): 栈: [fact(3)] 调用 factorial(2): 栈: [fact(3), fact(2)] 调用 factorial(1): 栈: [fact(3), fact(2), fact(1)] 返回 1 栈: [fact(3), fact(2)] 计算 2 * 1 = 2，返回 栈: [fact(3)] 计算 3 * 2 = 6，返回 栈: []

递归深度：栈中最多同时存在的栈帧数量。深度过大（如递归10000次）会导致栈溢出。

1.3 递归 vs 迭代

二、递归的经典问题：汉诺塔

2.1 问题描述

有三根柱子（A、B、C），A柱上有n个大小不同的圆盘，大的在下，小的在上。要求把所有圆盘从A移动到C，每次只能移动一个圆盘，且大圆盘不能放在小圆盘上面。求移动步骤。

2.2 递归思路

要把n个盘子从A移到C：

1. 先把上面 n-1 个盘子从A移到B（借助C）

2. 把最大的盘子从A移到C

3. 再把 n-1 个盘子从B移到C（借助A）

text

终止条件：n == 1 时，直接移动

2.3 代码实现

c

#include <stdio.h> // 汉诺塔递归实现 void hanoi(int n, char from, char to, char aux) { if (n == 1) { printf("移动 1 号盘: %c -> %c\n", from, to); return; } // 将 n-1 个盘子从 from 移到 aux hanoi(n - 1, from, aux, to); // 移动最大的盘子 printf("移动 %d 号盘: %c -> %c\n", n, from, to); // 将 n-1 个盘子从 aux 移到 to hanoi(n - 1, aux, to, from); } int main() { int n = 3; printf("汉诺塔 %d 个盘子移动步骤:\n", n); hanoi(n, 'A', 'C', 'B'); return 0; }

运行结果：

text

汉诺塔 3 个盘子移动步骤: 移动 1 号盘: A -> C 移动 2 号盘: A -> B 移动 1 号盘: C -> B 移动 3 号盘: A -> C 移动 1 号盘: B -> A 移动 2 号盘: B -> C 移动 1 号盘: A -> C

复杂度：移动次数 = 2ⁿ - 1，时间复杂度 O(2ⁿ)

三、分治法（Divide and Conquer）

3.1 分治法的三步骤

分治法将大问题分解成若干个相同的小问题，递归解决后合并结果。

3.2 典型应用

3.3 归并排序（分治法经典）

c

#include <stdio.h> #include <stdlib.h> // 合并两个有序子数组 void merge(int arr[], int left, int mid, int right, int temp[]) { int i = left, j = mid + 1, k = left; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while (i <= mid) temp[k++] = arr[i++]; while (j <= right) temp[k++] = arr[j++]; for (i = left; i <= right; i++) { arr[i] = temp[i]; } } // 归并排序（分治） void mergeSort(int arr[], int left, int right, int temp[]) { if (left >= right) return; // 终止条件：只有一个元素 int mid = left + (right - left) / 2; // 分解 mergeSort(arr, left, mid, temp); mergeSort(arr, mid + 1, right, temp); // 合并 merge(arr, left, mid, right, temp); } int main() { int arr[] = {8, 3, 5, 1, 6, 2, 7, 4}; int n = sizeof(arr) / sizeof(arr[0]); int *temp = (int*)malloc(n * sizeof(int)); printf("原数组: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); mergeSort(arr, 0, n - 1, temp); printf("排序后: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); free(temp); return 0; }

四、递归的优化：尾递归与记忆化

4.1 尾递归

尾递归是指递归调用是函数的最后一个操作，编译器可以优化为迭代，避免栈溢出。

c

// 普通递归阶乘（不是尾递归，因为最后还有乘法） int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); } // 尾递归阶乘 int factorialTail(int n, int result) { if (n <= 1) return result; return factorialTail(n - 1, n * result); }

4.2 记忆化递归（避免重复计算）

斐波那契数列的普通递归有大量重复计算，用记忆化优化。

c

#define MAX 100 int memo[MAX]; 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]; }

五、递归的常见陷阱

5.1 栈溢出

递归深度过大时，系统栈空间耗尽。

c

// 递归深度10000，可能导致栈溢出 void deepRecursion(int n) { if (n <= 0) return; deepRecursion(n - 1); }

解决方案：

• 改用迭代

• 增加栈大小（编译器选项）

• 使用尾递归（部分编译器优化）

5.2 重复计算

斐波那契普通递归的重复计算问题。

5.3 终止条件错误

忘记终止条件或条件错误会导致无限递归。

c

// 错误：n==0时没有正确返回 int badFactorial(int n) { return n * badFactorial(n - 1); // n=0时永远不停止 }

六、递归与分治的应用场景

七、小结

这一篇我们学习了递归与分治：

递归思考模板：

text

function(问题): if (问题足够小): 直接解决 else: 分解成子问题 递归解决子问题 合并子问题的解

下一篇我们讲动态规划。

八、思考题

1. 递归函数的空间复杂度为什么等于递归深度？

2. 汉诺塔问题中，移动 n 个盘子需要多少步？为什么？

3. 如何判断一个问题适合用递归解决？递归的缺点是什么？

4. 用递归实现二分查找，并分析其空间复杂度。

欢迎在评论区讨论你的答案。