第3章 递归与分治策略

1 递归1.1 递归定义1.2 递归函数的2个要素1.3 案例1.3.1 阶乘函数1.3.2 Fibonacci数列1.3.3 全排列问题1.3.4 整数划分问题1.3.5 Hanoi塔问题 1.4 递归优缺点1.4.1 递归优点1.4.2 递归缺点 1.5 消除递归的方法 2 分治2.1 分治思想2.2 案例2.2.1 合并排序（1）递归方式（2）非递归方式 2.2.2 二分搜索技术2.2.3 大整数乘法2.2.4 Strassen矩阵乘法2.2.5 棋盘覆盖问题2.2.6 快速排序2.2.7 线性时间选择2.2.8 最接近点对问题2.2.9 循环赛日程表问题 2.3 分治法适用条件 3 递归与分治的关系

1 递归

1.1 递归定义

1、递归函数：用函数自身给出定义的函数 2、递归算法：直接或间接地调用自身的算法

1.2 递归函数的2个要素

1、边界条件 2、递归方程

1.3 案例

1.3.1 阶乘函数

$$n!=\{\begin{array}{ll}1& \text{，n=0【边界条件】}\\ n(n-1)!& \text{，n>0【递归方程】}\end{array}$$

int factorial(int n){ if(n < 0) return false; if(n == 0) return 1; if(n > 0) return n*factorial(n - 1); }

1.3.2 Fibonacci数列

$$F(n)=\{\begin{array}{ll}1& \text{，n=0或1【边界条件】}\\ F(n-1)+F(n-2)& \text{，n>1【递归方程】}\end{array}$$

int Fibonacci(int n){ if(n < 0) return false; if(n == 0 || n == 1) return 1; if(n > 1) return Fibonacci(n - 1) + Fibonacci(n - 2); }

1.3.3 全排列问题

全排列$A_n^n$：n个不同元素按照一定的顺序排列起来 全排列数：$f(n)=n!$ 大佬写的算法.

1.3.4 整数划分问题

讲正整数n表示成一系列正整数之和

p(n)：正整数n的划分数 = q(n,n) q(n,m)：最大加数不大于m的划分个数

$$q(n,m)=\{\begin{array}{ll}1& \text{；n=1，m=1}\\ q(n,n)& \text{；n<m}\\ 1+q(n,n-1)& \text{；n=m}\\ q(n,m-1)+q(n-m,m)& \text{；n>m>1}\end{array}$$ 其中，$q(n-m,m)$为最大加数为m的划分个数

int q(int n,int m){ if(n == 1 || m == 1) return 1; if(n < m) return q(n,n); if(n == m) return 1 + q(n,n - 1); if(n > m && m > 1) return q(n,m - 1) + q(n - m,m); }

1.3.5 Hanoi塔问题

有a、b、c三个塔座，塔座a上自下而上、由大到小叠有n个圆盘，圆盘由小到大编号为1、2、···、n。现要将这n个圆盘从塔座a上转到塔座c上，并按同样顺序堆叠。

移动规则： （1）每次只能移动1个圆盘； （2）任何时刻都不允许将较大的圆盘压在较小的圆盘之上； （3）在满足移动规则（1）和（2）的前提下，可将圆盘移至塔座a、b、c中任一塔座上。

void move(int n, char a, char b) { printf("圆盘%d：%c->%c\n", n, a, b); } void hanoi(int n, char a, char b, char c) { if (n == 1) move(n, a, c); //只有一个圆盘，直接将它从塔座a移到塔座c else { hanoi(n - 1, a, c, b); //除最底下那个最大的圆盘，其他n-1个圆盘从塔座a经过塔座c中转到塔座b move(n, a, c); //圆盘n从塔座a移到塔座c hanoi(n - 1, b, a, c); //将塔座b上的n-1个圆盘移到塔座c } } int main() { hanoi(4, 'a', 'b', 'c'); return 0; }

1.4 递归优缺点

1.4.1 递归优点

使得算法简洁且易于理解。

1.4.2 递归缺点

使得算法运行效率较低。

1.5 消除递归的方法

1、定义栈（本质还是递归）； 2、用递推来实现递归函数； 3、通过Cooper、反演变换能将一些递归转化为尾递归，从而迭代求出结果。

2 分治

2.1 分治思想

分而治之 凡治众如治寡，分数是也。——孙子兵法 1° 将原始问题划分或者归结为规模较小的子问题； 2° 递归或迭代求解每个子问题； 3° 将子问题的解综合得到原问题的解。

2.2 案例

2.2.1 合并排序

（1）递归方式

#define length 10 typedef int ElemType; //数组数据类型 /*对数组a中的数据进行不减序排序*/ void mergeSort(ElemType a[], int left, int right) { ElemType* b = (ElemType*)malloc(sizeof(ElemType)* length); //临时数组 if (left == right) merge(a, b, left, 1, right); //合并 else if (left < right) { int i = (left + right) / 2; //取中点 mergeSort(a, left, i); //前半段排序 mergeSort(a, i + 1, right); //后半段排序 merge(a, b, left, i, right); //合并，保存到临时数组 copy(a, b, left, right); //将临时数组中的数据回存到a中 } } void merge(ElemType a[], ElemType b[], int left, int mid, int right) { int i = left; int j = mid + 1; int t = 0; while (i <= mid && j <= right) { if (a[i] < a[j]) b[t++] = a[i++]; else b[t++] = a[j++]; } while (i <= mid) b[t++] = a[i++]; while (j <= right) b[t++] = a[j++]; } void copy(ElemType a[], ElemType b[], int left, int right) { int t = 0; while (left < right) a[left++] = b[t++]; }

（2）非递归方式

void mergeSort(ElemType a[]) { ElemType* b = (ElemType*)malloc(sizeof(ElemType) * length); //临时数组 int s = 1; //子数组长度初始为1 while (s < length) { mergePass(a, b, s); //合并到数组b s += s; mergePass(b, a, s); //合并到数组a } } /*合并大小为s的相邻子数组*/ void mergePass(ElemType a[], ElemType b[], int s) { int i = 0; while (i <= length - 2 * s) { merge(a, b, i, i + s - 1, i + 2 * s - 1); //合并大小为s的相邻2段子数组 i = i + 2 * s; //为一下相邻2段子数组的合并做准备 } if (i + s < length) merge(a, b, i, i + s - 1, length - 1); //仍然有2组 else for (int j = i; j < length; j++) //只有一组了 b[j] = a[j]; } void merge(ElemType a[], ElemType b[], int left, int mid, int right) { int i = left; int j = mid + 1; int t = left; while (i <= mid && j <= right) { if (a[i] < a[j]) b[t++] = a[i++]; else b[t++] = a[j++]; } while (i <= mid) b[t++] = a[i++]; while (j <= right) b[t++] = a[j++]; }

2.2.2 二分搜索技术

问题：给定已排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x 二分搜索：将n个元素分成个数大致相同的两半，取a[n/2]与x进行比较 如果 x = a[n/2]，则找到x，算法终止 如果 x < a[n/2]，则只要在数组a的左半部继续搜索x 如果 x > a[n/2]，则只要在数组a的右半部继续搜索x

int binarySearch(int a[], int x, int n) { //在 a[0] <= a[1] <= …… <= a[n-1]中搜索 x //找到x时返回其在数组中的位置，否则返回-1 int left = 0; int right = n - 1; while (left <= right) { int middle = (left + right) / 2; if (x == a[middle]) return middle; if (x > a[middle]) left = middle + 1; else right = middle - 1; } return -1; //未找到x }

2.2.3 大整数乘法

大佬写的算法.

2.2.4 Strassen矩阵乘法

大佬写的.

2.2.5 棋盘覆盖问题

$2^k\times 2^k$个方格组成的特殊棋盘中，恰有一个特殊方格与其他方格不同。 用4种不同形态的L型骨牌覆盖除特殊方格以外的所有方格 且任何2个L型骨牌不得重叠覆盖

#define MAXSIZE 8 static int tile = 1; //表示L型骨牌的编号 static int board[MAXSIZE][MAXSIZE]; //表示棋盘 //处理带有特殊棋子的棋盘 //tr、tc分别表示棋盘入口即左上角的行列号 //dr、dc分别表示特殊棋子的行列位置 //size表示棋盘的行数或列数 void chessBoard(int tr, int tc, int dr, int dc, int size) { if (size == 1) return; //一格，没啥好处理的 int t = tile++; //存放L型骨牌号 int s = size / 2; //分割棋盘 /*覆盖左上角子棋盘*/ if (dr < tr + s && dc < tc + s) chessBoard(tr, tc, dr, dc, s); //特殊方格在此棋盘中 else { //此棋盘中无特殊方格 //用t号L型骨牌覆盖右下角 //由于骨牌有四种，处理过程中同一级设置的特殊棋子用相同的骨牌覆盖 board[tr + s - 1][tc + s - 1] = t; //覆盖其余方格 chessBoard(tr, tc, tr + s - 1, tc + s - 1, s); //假设右下角是特殊方格 } /*覆盖右上角子棋盘*/ if (dr < tr + s && dc >= tc + s) chessBoard(tr, tc + s, dr, dc, s); //特殊方格在此棋盘中 else { //此棋盘中无特殊方格 //用t号L型骨牌覆盖左下角 board[tr + s - 1][tc + s] = t; //覆盖其余方格 chessBoard(tr, tc + s, tr + s - 1, tc + s, s); //假设左下角是特殊方格 } /*覆盖左下角子棋盘*/ if (dr >= tr + s && dc < tc + s) chessBoard(tr + s, tc, dr, dc, s); //特殊方格在此棋盘中 else { //用t号L型骨牌覆盖右上角 board[tr + s][tc + s - 1] = t; //覆盖其余方格 chessBoard(tr + s, tc, tr + s, tc + s - 1, s); //假设右上角是特殊方格 } /*覆盖右下角子棋盘*/ if (dr >= tr + s && dc >= tc + s) chessBoard(tr + s, tc + s, dr, dc, s); //特殊方格在此棋盘中 else { //用t号L型骨牌覆盖左上角 board[tr + s][tc + s] = t; //覆盖其余方格 chessBoard(tr + s, tc + s, tr + s, tc + s, s); //假设左上角是特殊方格 }

2.2.6 快速排序

【参考】王道 没图，硬讲。（因为学过了，所以就提一下思想，如果下一次复看的时候不会，再贴图）

快速排序是对冒泡排序的一种改进方法   冒泡排序：每次都能确定最后一个元素   快速排序：每次都能确定中间那个元素 快速排序步骤： 1° 先选取基准枢轴元素pivot，一般取待排序序列a的首个元素 2° i指向待排序序列首，j指向待排序序列末 3° j往前遍历，直到遇到比pivot小的元素，然后a[i]=a[j] 4° j往后遍历，直到遇到比pivot大的元素，然后a[j]=a[i] 5° pivot填到中间那个位置

void QuickSort(ElemType A[], int low, int high) { if (low < high) { //递归跳出的条件 int pivotpos = Partition(A, low, high); //划分 QuickSort(A, low, pivotpos - 1); //依次对两个子表进行递归排序 QuickSort(A, pivotpos + 1, high); } } int Partition(ElemType A[], int low, int high) { ElemType pivot = A[low]; //将当前表中第一个元素设为枢轴，对表进行划分 while (low < high) { //循环跳出条件 while (low < high && A[high] >= pivot) --high; A[low] = A[high]; //将比枢轴小的元素移动到左端 while (low < high && A[low] <= pivot) --low; A[high] = A[low]; //将比枢轴大的元素移动到右端 } A[low] = pivot; //枢轴元素存放到最终位置 return low; //返回存放枢轴的最终位置

2.2.7 线性时间选择

给定线性序列中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素 大佬写的算法.

2.2.8 最接近点对问题

大佬写的算法.

2.2.9 循环赛日程表问题

n个选手 （1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能赛一次； （3）当n为偶数时，循环赛进行n-1天；当n为奇数时，循环赛进行n天。

static int a[SIZE][SIZE]; void match(int n) { /*选手从0开始计数*/ if (n == 2) { a[0][0] = 0; a[0][1] = 1; a[1][0] = 1; a[1][1] = 0; } else if (n % 2 == 0) match(n / 2); //偶数个选手 else { n += 1; //奇数个选手，增加一个虚拟选手，即为n号选手 match(n / 2); } Makecopy(n); //合并 } /*n为偶数*/ void Makecopy(int n) { if ((n / 2) % 2 == 0) copy(n); //n/2为偶数的情况 else copyodd(n); //n/2为奇数的情况 } /*n为偶数，n/2为奇数*/ void copy(int n) { int m = n / 2; for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) { a[i + m][j] = a[i][j] + m; //第3部分 a[i][j + m] = a[i + m][j]; //第2部分 a[i + m][j + m] = a[i][j]; //第4部分 } } /*n为偶数，n/2为奇数*/ void copyodd(int n) { int m = n / 2; /*第3部分，即解决第i+1号选手到第n-1号选手的前m+1天的比赛*/ for (int i = 0; i < m; i++) for (int j = 0; j <= m; j++) { if (a[i][j] >= m) { //表示上半区i号选手轮空 //对应下半区i+m号选手也轮空 a[i][j] = m + i; a[m + i][j] = i; } else a[m + i][j] = a[i][j] + m; //相应位置各加m } /*第2、4部分，即解决所有选手后面天的比赛*/ for (int i = 0; i < m; i++) for (int j = 1; j < m; j++) { a[i][m + j] = (i + j) % m + m; //按此规律给出相应的对手号，解决第2部分 a[(i + j) % m + m][m + j] = i; //按此规律给出相应的对手号，解决第4部分 } }

2.3 分治法适用条件

（1）问题的规模缩小到一定程序可以容易地解决； （2）问题具有最优子结构性质：问题可以分解为若干个规模较小地相同问题； （3）利用问题分解出地子问题的解可以合并为该问题的解； （4）问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

3 递归与分治的关系

递归作为一种工具，在实现分治时经常被使用。