第5章递归：分治法

5.3.2 分治法

分治法（Divide and Conquer）是一种极为重要且应用广泛的策略。它的核心思想，正如其名“分而治之”，是将一个难以直接解决的复杂问题，分解成若干个规模更小、结构相同的子问题，分别解决这些子问题，最后再将它们的解合并，从而得到原问题的解。

1. 什么是分治法

分治法是一种自顶向下的问题求解范式。假设要完成一项庞大而复杂的工程，很自然地会将其分解为多个独立的子任务，分配给不同的小组去完成，最后再将所有小组的成果汇总，形成最终的工程结果。分治法的思想与此如出一辙。在计算机科学中，许多经典算法都体现了分治思想，例如：

• 归并排序：将数组一分为二，对两个子数组分别排序，然后将两个有序的子数组合并成一个大的有序数组。
• 快速排序：选取一个基准元素，将数组分为两部分，一部分所有元素都小于基准，另一部分都大于基准，然后对这两部分递归地进行快速排序。
• 二分搜索：在有序数组中查找元素，每次都将搜索范围缩小一半。

2. 分治法的基本原理与实施步骤

一个问题如果能够用分治法解决，通常需要满足以下几个特征：

1. 规模缩小易解：问题的规模缩小到一定程度后，可以非常容易地直接求解。这构成了递归的“出口”或“边界条件”。
2. 可分解与最优子结构：问题可以被分解为若干个规模较小的、与原问题结构相同的子问题。并且，原问题的解可以通过子问题的解合并得到。
3. 子问题相互独立：分解出的各个子问题之间是独立的，没有交叉或重叠的部分。这是分治法与动态规划（Dynamic Programming）的一个关键区别，动态规划通常用于解决子问题有重叠的情况。

分治算法的实施流程严格遵循以下三个步骤：

1. 分解（Divide）：将原问题 P 分解成 k 个规模更小、结构相同的子问题 P1, P2, …, Pk。最常见的情况是二分递归，即将问题一分为二。
2. 解决（Conquer）：递归地求解这些子问题。当子问题的规模小到足以直接解决时（即达到递归边界），就直接求解。
3. 合并（Merge）：将所有子问题的解 S1, S2, …, Sk 合并起来，构建出原问题 P 的解 S。这一步是分治法的关键，合并操作的效率直接影响整个算法的性能。

3. 使用分治法解决括号匹配问题

在第 4 章的 4.4.2 节曾以栈解决括号匹配问题，此处用分支算法来解决这个问题。

一个有效的括号字符串 S，其结构必然满足以下两种情况之一：

• 情况 A（包裹结构）：S 是由一个有效的括号字符串 S2 两边加上一对括号构成的，即 S = (S2)。例如 “(())”，其中 S2 = “()”。
• 情况 B（并列结构）：S 是由两个或多个有效的括号字符串 S1 和 S3 拼接而成的，即 S = S1 + S3。例如 “()()”，其中 S1 = “()”，S3 = “()”。

基于此，制定如下分治策略：

• 分解（Divide）：对于给定的字符串 S，找到一个“分割点”，将其分解成更小的子问题。一个有效的分割点是第一个使得括号平衡计数回到 0 的位置。从左到右遍历字符串，用一个计数器 balance 记录括号的平衡度（遇到 ( 加一，遇到 ) 减一）。
  • 如果遍历到字符串末尾，balance 才刚好回到 0（并且中途从未小于0），说明整个字符串是包裹结构（S2）。可以递归地去判断内部的 S2 是否有效。
  • 如果在中途某处 balance 回到了 0，说明找到了一个完整的、有效的子串 S1，那么原问题就分解成了判断 S1 和剩余部分 S3 是否都有效，即并列结构。
• 解决（Conquer）：
  • 递归边界：
    1. 一个空字符串 "" 是有效的。这是最重要的递归出口。
    2. 如果字符串长度为奇数，或者以 ) 开头，或者以 ( 结尾，那么它必定是无效的。
  • 递归调用：根据分解策略，进行相应的递归调用。
• 合并（Merge）：在分治法中，合并步骤是显式的。但在这个问题里，合并操作是隐式的，体现在逻辑判断中。例如，对于并列结构 S1 + S3，原问题 S 有效的条件是 “S1 有效并且S3 有效”。这个逻辑“与”（AND）操作就是合并的过程。

好的，我们现在将上一篇文章中讨论的分治递归算法，用类 C 语言的伪代码来呈现，并对其执行过程进行详细的分析。

【算法描述】

/** 函数功能: 使用分治递归法检查 s 的子串 s[start...end] 是否为有效的括号匹配* @param s: 原始输入字符串* @param start: 当前处理子串的起始索引* @param end: 当前处理子串的结束索引* @return: 如果子串有效则返回 true，否则返回 false*/
boolean isValidParentheses(string s, int start, int end) {// 计算当前子串的长度int length = end - start + 1;// --- 解决 (Conquer): 递归边界条件 ---// 1. 空字符串是有效的if (length <= 0) {return true;}// 2. 长度为奇数，或首字符为')'，或尾字符为'('，则必无效if (length % 2 != 0 || s[start] == ')' || s[end] == '(') {return false;}// --- 分解 (Divide): 寻找分割点 ---int balance = 0;int split_point = -1; // 初始化分割点为-1（表示未找到）for (int i = start; i <= end; i++) {if (s[i] == '(') {balance++;} else {balance--;}// 如果在遍历过程中 balance 小于 0，说明右括号在左括号之前出现，无效if (balance < 0) {return false;}// 找到了一个平衡点，并且它不是整个字符串的结尾// 这意味着我们找到了一个并列结构 S = S1 + S3if (balance == 0 && i < end) {split_point = i;break; // 找到第一个分割点即可}}// --- 合并 (Merge): 根据分解结果进行递归求解 ---if (split_point != -1) {// 情况B (并列结构): S = S1 + S3// S1 是 s[start...split_point], S3 是 s[split_point+1...end]// 原问题解是两个子问题解的 "逻辑与"return isValidParentheses(s, start, split_point) && isValidParentheses(s, split_point + 1, end);} else {// 情况A (包裹结构): S = (S2)// 此时 balance 在遍历到 end 时才归零，未找到中间分割点// 原问题解等价于其内部子串 S2 s[start+1...end-1] 的解return isValidParentheses(s, start + 1, end - 1);}
}// 主调用函数
boolean check(string s) {return isValidParentheses(s, 0, s.length() - 1);
}

【执行过程】

以字符串 s = "(())()" 为例，来追踪上述算法执行流程。主函数调用 check("(())()")，触发 isValidParentheses("(())()", 0, 5)。

调用栈层级 1: isValid(s, 0, 5) (处理子串 "(())()")

1. 边界检查: length = 6，不满足任何边界退出条件。
2. 寻找分割点:
   • i = 0, s[0] = '(', balance = 1
   • i = 1, s[1] = '(', balance = 2
   • i = 2, s[2] = ')', balance = 1
   • i = 3, s[3] = ')', balance = 0
   • 此时 balance == 0 且 i < end (即 3 < 5)。条件满足，找到分割点。
   • 设置 split_point = 3，并 break 循环。
3. 递归求解：
   • split_point 不等于 -1，执行并列结构逻辑。
   • 返回 isValid(s, 0, 3) && isValid(s, 4, 5)。
   • 程序现在需要分别计算这两个调用的结果。

调用栈层级 2 (左分支): isValid(s, 0, 3) (处理子串 "(())")

1. 边界检查: length = 4，不满足退出条件。
2. 寻找分割点：
   • i = 0, s[0] = '(', balance = 1
   • i = 1, s[1] = '(', balance = 2
   • i = 2, s[2] = ')', balance = 1
   • i = 3, s[3] = ')', balance = 0
   • 此时 balance == 0，但 i == end (即 3 == 3)。i < end 条件不满足，循环继续直到结束。
   • 循环结束后，split_point 仍然是 -1。
3. 递归求解：
   • split_point 等于 -1，执行包裹结构逻辑。
   • 返回 isValid(s, 1, 2)。

调用栈层级 3 (左分支): isValid(s, 1, 2)（处理子串 "()"）

1. 边界检查: length = 2，不满足退出条件。
2. 寻找分割点:
   • i = 1, s[1] = '(', balance = 1
   • i = 2, s[2] = ')', balance = 0
   • 此时 balance == 0，但 i == end (即 2 == 2)。循环结束，split_point 仍然是 -1。
3. 递归求解：
   • split_point 等于 -1，执行包裹结构逻辑。
   • 返回 isValid(s, 2, 1)。

调用栈层级 4 (左分支): isValid(s, 2, 1)（处理空范围）

1. 边界检查：length = 1 - 2 + 1 = 0。
2. length <= 0 条件满足，直接返回 true。

• 现在，返回值开始向调用栈上层传递：
  • isValid(s, 1, 2) 接收到 true，因此它也返回 true。
  • isValid(s, 0, 3) 接收到 true，因此它也返回 true。
• 至此，isValid(s, 0, 5) 调用中的左半部分 isValid(s, 0, 3) 已计算完毕，结果为 true。现在程序开始执行右半部分。

调用栈层级 2 (右分支): isValid(s, 4, 5) (处理子串 "()")

1. 这个调用的执行过程与调用栈层级 3 完全相同，只是索引不同。它最终会调用 isValid(s, 5, 4)。
2. isValid(s, 5, 4) 会因为 length = 0 而返回 true。
3. 因此，isValid(s, 4, 5) 也 返回 true。

返回调用栈层级 1: isValid(s, 0, 5)

1. 现在，左右两个递归调用的结果都已获得。
2. 表达式 isValid(s, 0, 3) && isValid(s, 4, 5) 变为 true && true。
3. 计算结果为 true。
4. 最终，isValid(s, 0, 5) 返回 true，整个过程结束。

通过上述分析，可以清晰地看到分治法如何将一个看似整体的问题，通过寻找结构上的分割点，分解为独立的、更小的子问题，并通过递归触达最简单的基础情况（空字符串），最后将子问题的解（true 或 false）通过逻辑运算（&&）合并起来，得到原问题的最终答案。

注意：如果将上述方法扩展到多种括号匹配问题，会让实现会变得更复杂，并且在效率上会达到 $O(n^2)$ 程度。但是，如果用栈解决此类问题，则更简单高效（即 4.4.2 节的方法）。

例 5.3.2 利用二分递归算法，计算数组中 $n$ 个整数的和，并分析该算法的时间复杂度。

【解】

【例 5.3.1】中已经给出了一种数组元素求和的算法，本题要求根据分治算法的思想，用二分递归实现计算。

【算法步骤】

1. 以居中的元素为界将数组一分为二；
2. 递归地对子数组分别求和；
3. 最后，子数组之和相加即为原数组的总和。

【算法描述】

int sum(int A[], int low, int high ) { //数组求和算法(二分递归版，入口为sum(A, 0, n - 1)) if ( low == high )        //基准情形(区间长度已降至1)，则return A[low];        //直接返回该元素else{int mid = (low + high) / 2;    //以居中单元为界，将原区间一分为二//递归对各个子数组求和，再用加法合并return sum(A, low, mid) + sum(A, mid+1, high); }
}

【算法分析】

$♡$ 方法 1：跟踪递归过程

不妨假设数组的长度 $n=2^m$ ，例如 $n=8$ ，即计算 $0+1+\cdots +7$ ，如图 5.3.2 所示，借用二叉树，给出了执行 sum(A, 0, 7) 的递归过程。

图 5.3.2 sum(A, 0, 7) 的递归过程

由图 5.3.2 的递归过程可知，从上向下，每下降一层，每个递归实例 sum(low, high) 都分裂为一对更小的实例 sum(low, mid) 和 sum(mid + 1, high) 。也就是，每经过一次递归调用，子问题对应的数组区间长度 high - low + 1 都减半，对应二叉树中的一个结点。

• 叶子结点共有 n 个，对应每个元素，即递归终止条件（low == high）。
• 非叶子结点共计 $n-1$ 个（图 5.3.2 所示的二叉树是一个满二叉树，根据二叉树的性质可知 $n_0=n_2+1$ ，本问题中 $n_0=n$ ，$n_2$ 表示度为 2 的结点数量，即非叶子结点，可得 $n_2=n-1$）。

所以，总的结点数是 $2n-1$ 。每个结点表示一个递归实例，每一个递归实例中的非递归计算所需要的时间是常数，所以算法的时间复杂度是 $(2n-1)\times c$，即 $O(n)$。

$♡$ 方法 2：利用递推公式

设数组长度为 $n=high-low+1$，时间复杂度为 $T(n)$。根据算法逻辑：

• 基准情形（$n=1$）：直接返回元素，时间复杂度为常数，令 $T(1)=1$。
• 递归情形（$n>1$）：
  1. 将数组分为两个子区间，规模为 $\lfloor n/2\rfloor$和 $\lceil n/2\rceil$。
  2. 递归计算两个子区间的和，时间复杂度为 $T(\lfloor n/2\rfloor )+T(\lceil n/2\rceil )$。
  3. 合并结果（一次加法操作），时间复杂度为常数阶 $O(1)$ 。

所以，得到递推式为：
$$T(n)=\{\begin{array}{ll}1& \text{if }n=1,\\ T(\lfloor n/2\rfloor )+T(\lceil n/2\rceil )+1& \text{if }n>1.\end{array}$$
逐层展开递推式：
$$\begin{array}{rl}T(n)& =2T\left(\frac{n}{2}\right)+1\\ & =2\left[2T\left(\frac{n}{4}\right)+1\right]+1=4T\left(\frac{n}{4}\right)+2+1\\ & =4\left[2T\left(\frac{n}{8}\right)+1\right]+3=8T\left(\frac{n}{8}\right)+4+3\\ & ⋮\\ & =2^{k}T\left(\frac{n}{2^k}\right)+(2^k-1).\end{array}$$
当 $n=2^k$ 时，递归终止于 $T(1)=1$，代入得：
$$T(n)=2^k\cdot 1+(2^k-1)=2^{k+1}-1=2n-1$$
所以，时间复杂度是 $O(n)$ 。

例 5.3.3 斐波那契数列

斐波那契数列于公元1150年被印度数学家发现，而后意大利人斐波那契（Leonardo Fibonacci, 1175－1250）在描述兔子生长的数目时用上了这数列：

• 第一个月初有一对刚诞生的兔子；
• 第二个月之后（第三个月初）它们可以生育；
• 每月每对可生育的兔子会诞生下一对新兔子；
• 兔子永不死。

假设在 $n$ 月有兔子总共 $a$ 对， $n+1$ 月总共有 $b$ 对。在 $n+2$ 月必定总共有 $a+b$ 对：因为在 $n+2$ 月的时候，前一月（ $n+1$ 月）的 $b$ 对兔子可以存留至第 $n+2$ 月（在当月属于新诞生的兔子尚不能生育）。而新生育出的兔子对数等于所有在 $n$ 月就已存在的 $a$ 对。

斐波纳契数是帕斯卡三角形的每一条红色对角线上数字的和。

用递归方式定义斐波那契数列：
$$fib(n)=\{\begin{array}{ll}1& (n=0或n=1)\\ fib(n-1)+fib(n-2)& (n>1)\end{array}$$
根据以上表达式，相应的算法描述如下，要求分析此程序的时间复杂度。

long fib(long n){if(n == 1 || n == 2) return 1;else return fib(n-1) + fib(n-2);
}

【解】

假设计算 fib(n) 的时间是 $T(n)$ ，按照题目中的算法，先花费 $T(n-1)$ 时间计算 fib(n-1) ；再花费 $T(n-2)$ 时间计算 fib(n-2) ；最后用 1 个时间单元将二者相加。由此写出 $T(n)$ 的递推式：
$$T(n)=\{\begin{array}{ll}1& (n\le 1)\\ T(n-1)+T(n-2)+1& (\text{others})\end{array}$$
令 $S(n)=\frac{T(n)+1}{2}$ ，则上式可以写成：
$$S(n)=\{\begin{array}{ll}1& (n\le 1)\\ S(n-1)+S(n-2)& (\text{others})\end{array}$$
将此式与斐波那契数列的函数式对比：
$$fib(n)=\{\begin{array}{ll}1& (n=0或n=1)\\ fib(n-1)+fib(n-2)& (n>1)\end{array}$$
$S(n)$ 与 $fib(n)$ 在形式上基本一样，只是起始项不同，有归纳可得：
$$\begin{array}{rl}S(0)& =1=fib(1)\\ S(1)& =1=fib(2)\\ & ⋮\\ S(n)& =fib(n-1)\end{array}$$
根据 $fib(n)$ 可以解得（求解过程参考博客：https://cslab.blog.csdn.net/article/details/145847032）：
$$fib(n)=\frac{1}{\sqrt{5}}\left[{\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n\right],(n=0,1,2,\cdots )$$
令 $\phi =\frac{1+\sqrt{5}}{2}$ （黄金比例），则 $fib(n)=\frac{1}{\sqrt{5}}[{\phi }^n-(1-\phi {)}^n]$ 。

所以：
$$\begin{array}{rl}& S(n)=fib(n+1)=\frac{1}{\sqrt{5}}[{\phi }^{(n+1)}-(1-\phi {)}^{(n+1)}]\\ & \therefore T(n)=2S(n)-1=2\cdot fib(n+1)-1=O({\phi }^{n+1})\end{array}$$
由此可知，以递归方式实现的斐波那契数列的时间复杂度为指数级，不是一个有价值的算法。根据 $fib(n)$ 的递归函数，追踪调用过程，当第一次调用 $fib(n-1)$ 时，$fib(n-2)$ 实际上已经计算了，在后面还要再计算 $fib(n-2)$ 。即同一个实例，在递归过程中，重复计算，从而导致运行时间暴增。

例 5.3.4 有以下算法：

void fun(int a[], int n, int k){ //数组 a 共有 n 个元素int i;if(k == n-1){for(i = 0; i < n; i++)printf("%d/n", a[i]);} else {for(i = k; i < n; i++)a[i] = a[i] + i * i;fun(a, n, k+1);}
}

调用上述算法的语句为 fun(a, n, 0) ，求其空间复杂度。

【解】

本题是对递归算法空间复杂度的估算，也可以使用之前估算递归算法的时间复杂度的方法。

根据题目中的算法描述可知，在 if 分支下的程序仅需要临时变量，故将其所用辅助空间记作 1 ；在 else 分支下，递归调用函数 fun(a, n, k+1) 需要用到递归栈，即为所需要的辅助空间。

设 fun(a, n, k) 的辅助空间为 $S_1(n,k)$ ，fun(a, n, 0) 的辅助空间为 $S_1(n,0)$ ，显然有 $S(n)=S_1(n,0)$ 。

于是可得本题算法的辅助空间递推式：
$$S_1(n,k)=\{\begin{array}{ll}1& (k=n-1)\\ 1+S_1(n,k+1)& \text{others}\end{array}$$
于是可得：
$$\begin{array}{rl}S(n)=S_1(n,0)& =1+S_1(n,1)(\because S_1(n,0)=1+S_1(n,0+1)\\ & =1+1+S_1(n,2)(\because S_1(n,1)=1+S_1(n,1+1))\\ & ⋮\\ & =\begin{array}{cc}\underbrace{1+1+\cdots +1}& +S_1(n,n-1)\\ (n-1)个1& \end{array}\\ & =\begin{array}{c}\underbrace{1+1+\cdots +1}\\ n个1\end{array}(\because S_1(n,n-1)=1)\\ & =n\end{array}$$
所以，调用 fun(a, n, 0) 的空间复杂度是 $O(n)$ 。

由以上分析可知，递归算法的空间复杂度主要由递归深度决定，并且每个递归调用需要一定的额外空间来保存局部变量和返回地址等信息。