目录

递归与分治策略递归的概念定义举例应用 分治法基本思想举例应用

递归与分治策略

本章节主要涉及如下问题：

递归的原理与应用

1.n的阶乘问题 2.斐波那契数列 3.全排列问题 4.汉诺塔问题

分治法与递归的结合

1.二分搜索 2.棋盘覆盖 3.合并排序 4.快速排序 5.线性时间选择

递归的概念

定义

直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。使用递归技术往往会使代码更简洁，使算法的描述更清晰且容易理解。

举例

例 1：阶乘函数 阶乘函数递归的定义为： $$n!=\{\begin{array}{ll}1& n=0\\ n(n-1)!& n>0\end{array}$$ 当n=0时，n!=1，这是这个函数的初始条件，是非递归定义的，是此递归函数的退出条件。这个递归函数在执行时，会不断的调用自身，寻找自身的值减一后的阶乘值，直到自身值减一为0时，此时函数递归到了最后一层（即非递归定义的退出条件），这时n=0的阶乘为1，然后层层回滚，计算出n=1的阶乘的值后，再去计算n=2时阶乘的值，这样一直不断的计算n+1阶乘的值，直到回滚到初始的n的阶乘的值。

每一个递归函数都要有非递归定义的初始值，不然无法退出函数调用的循环。

代码如下：

#include<iostream> using namespace std; int sum = 0; //定义全局变量sum，用于记录函数调用自身的次数 //使用 long long 类型的返回值，防止n的阶乘的值过大，超出了int型的范围 long long fac(int n) { sum++; if (n == 0 ) return 1; else return n * fac(n - 1); } int main() { int n; cin >> n; cout << n << "的阶乘为：" << fac(n) << endl; cout << "函数调用的次数为：" << sum; return 0; }

运行结果： 结果分析： 最开始传值的时候即n=8时进入函数，sum自增后为1。此后，进入else分支，进行递归，再次进入函数时n=7。依此类推，最后一次进入函数时n=0，而n=0恰好是此递归函数的初始条件，自此不再调用自身。故此可以看出初始条件是递归函数所必需的要有的，不然无法退出循环。当n=8,7,6,5,4,3,2,1,0时都进入过函数，故sum累加值为9。

例 2：斐波那契数列 无穷数列 1， 1， 2， 3， 5 ，…称为斐波那契数列，它具有前两项之和等于后一项的特点。它可以递归的定义为： $$F(n)=\{\begin{array}{ll}1& n=0\\ 1& n=1\\ F(n-1)+F(n-2)& n>1\end{array}$$

代码如下：

#include<iostream> using namespace std; int sum = 0; //记录函数调用的次数 int Fibonacci(int n) { sum++; if(n == 0) return 1; if(n == 1) return 1; if(n > 1) return Fibonacci(n - 1) + Fibonacci(n - 2); } int main() { int n; cin >> n; cout << "斐波那契数列的第" << n <<"项为：" << Fibonacci(n) <<endl; cout << "函数调用的次数为：" << sum; return 0; }

运行结果： 结果分析： n=3时进入函数一次（sum=1），执行递归项为Fibonacci(1)和Fibonacci(2)。执行Fibonacci(1)时(sum=2)，直接返回结果1，不再递归。而执行Fibonacci(2)时(此时sum=3)，执行递归项Fibonacci(1)和Fibonacci(0)，执行完后sum=3+2=5。故共调用函数5次。

应用

例 1：全排列问题 设*R={r₁,r₂,…,r_n}*是要进行排列的n个元素，要求输出这些元素的所有排列组合。

案例： 输入 3 (数组元素个数） 1 2 3 （数组中的元素） 输出 1 2 3 1 3 2 2 1 3 2 3 1 3 2 1 3 1 2

代码如下:(点击此处查看详细解析)

#include<iostream> using namespace std; template<typename T> void Swap(T &a, T &b) { T tem; tem = a; a = b; b = tem; } template<typename T> void Perm(T list[], int p, int q) { if (p == q) { for (int i = 0; i <=q; i++) cout << list[i] ; cout << endl; } else { for (int i = p; i <= q; i++) { Swap(list[i], list[p]); Perm(list, p + 1, q); Swap(list[i], list[p]); } } } int main() { int n; cin >> n; int *p = new int[n]; for(int i=0;i<n;i++) cin >> p[i]; Perm(p,0,n-1); return 0; }

例 2：汉诺塔问题 有a, b, c三座塔，在a塔上有n个圆盘，这些圆盘自上而下，从小到大的叠放在一起，现在要把圆盘从a移到b上，每次只能移动一个圆盘，并且任何时刻都不能将大的圆盘压在小的圆盘上，请输出移动的步骤及移动的次数（圆盘自上而下编号为1, 2, … ,n）。

案例： 输入 3 （圆盘的个数） 输出 move 1 from a to b move 2 from a to c move 1 from b to c move 3 from a to b move 1 from c to a move 2 from c to b move 1 from a to b 移了7次

代码如下：(点击查看详细解析)

#include<iostream> using namespace std; int sum = 0; //记录移动次数 void move(int n, char a, char b) { sum++; cout << "move " << n << " from " << a << " to " << b << endl; } void hanoi(int n, char a, char b, char c) { if (n > 0) { hanoi(n - 1, a, c, b); move(n, a, b); hanoi(n - 1, c, b, a); } } int main() { int n; cin >> n; char a = 'a', b = 'b', c = 'c'; hanoi(n, a, b, c); cout << "移了"<<sum<<"次"; return 0; }

分治法

基本思想

将一个规模为n的问题分解成为k个规模较小的子问题，这些子问题相互独立且与原问题相同。我们可以递归的解决这些子问题，然后将各个子问题的解合并就可以得到原问题的解。

举例

例 1：二分搜索 假定有n个元素的数组a已经排好序（从小到大的顺序排列），从中找出一个特定的元素x，若找到则输出它的下标值，否则输出"not found"。

解题思路： 若数组的左边界下标值为left,右边界下标值为right，数组中间元素的下标值为mid=(left+right)/2

把x与数组中间的元素作比较，若x较小，则x在数组的左半边，否则x在数组的右半边。若x在左半边，则将数组的右边界为mid，重复上面步骤。若x在左半边，将左边界赋值为mid，重复上面步>骤。若x==a[mid]则返回mid。 代码如下： #include<iostream> using namespace std; int BinarySearch(int a[], int left, int right， int x) { int l = left, r = right; while(l<=r) { int mid = (l+r)/2; if(x == a[mid]) return mid; if(x > a[mid]) l = mid + 1; if(x < a[mid]) r = mid - 1; } return -1; } int main() { int n; //数组大小 cin>>n; int *a = new int[n]; for(int i=0;i<n;i++) cin>>a[i]; //输入数组元素 int x; //要找的值 cin>>x; int j = BinarySearch(a,0,n-1，x); if(j==-1) cout<<"not found"; else cout<<j; return 0; }

运行结果：

例 2：棋盘覆盖问题

代码如下：

#include <iostream> using namespace std; const int BOARD_SZ = 8; static int tile = 1; static int board[BOARD_SZ][BOARD_SZ] = { 0 }; void chess_board(int tr, int tc, int dr, int dc, int size) { if (size == 1) return; int t = tile++; //tile means 瓦片，基石，覆盖的步骤 int sz = size / 2; //每次进行划分 //cover top left corner 判断左上角棋盘 if (dr < tr + sz && dc < tc + sz) //notice < < //注意一共四种情况，<>=这几个符号要控制好边界 chess_board(tr, tc, dr, dc, sz); else { board[tr + sz - 1][tc + sz - 1] = t; chess_board(tr, tc, tr + sz - 1, tc + sz - 1, sz); } //cover top right corner 判断右上角棋盘 if (dr < tr + sz && dc >= tc + sz) //notice < >= chess_board(tr, tc + sz, dr, dc, sz); else { board[tr + sz - 1][tc + sz] = t; chess_board(tr, tc + sz, tr + sz - 1, tc + sz, sz); } //cover lower left corner 判断左下角棋盘 if (dr >= tr + sz && dc < tc + sz) //notice >= < chess_board(tr + sz, tc, dr, dc, sz); else { board[tr + sz][tc + sz - 1] = t; chess_board(tr + sz, tc, tr + sz, tc + sz - 1, sz); } //cover lower right corner 判断右下角棋盘 if (dr >= tr + sz && dc >= tc + sz) //notice >= >= chess_board(tr + sz, tc + sz, dr, dc, sz); else { board[tr + sz][tc + sz] = t; //标记一个假设的特殊点 chess_board(tr + sz, tc + sz, tr + sz, tc + sz, sz); //递归该部分 } } void print_chess_board() { cout.setf(ios::left); //左对齐 for (int i = 0; i < BOARD_SZ; ++i) { for (int j = 0; j < BOARD_SZ; ++j) { cout.width(3); //打印宽度为3 cout << board[i][j]<<' '; } cout << endl<<endl; } } int main() { chess_board(0, 0, 3, 4, BOARD_SZ); print_chess_board(); return 0; }

运行结果：

应用

例 1：合并排序 基本思想：将待排序元素分成大小大致相同的两个子集和，分别对两个子集合进行排序，最终将排好序的子集合合并成要求的排好序的集合。

点击此处查看完整代码

例 2：快速排序 步骤为：

从数列中挑出一个元素，称为“基准”（pivot）。重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。递归到最底部时，数列的大小是零或一，也就是已经排序好了。

点击此处查看完整代码

例 3：线性时间选择

点击此处查看详解