算法总体思想
对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
分治法的设计思想是:将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
递归的概念
直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。
由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。
分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
示例：
例1阶乘函数
阶乘函数可递归地定义为：
n! = 1 n = 0 (边界条件)
n! = n(n-1)! n > 0 (递归方程)
边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。
实现：
/* 主题：阶乘使用递归和非递归实现* 作者：chinazhangjie* 邮箱：chinajiezhang@gmail.com* 开发语言：C++* 开发环境：Code::Blocks 10.05* 时间: 2010.10.05*/#include <iostream>using namespace std;// factorial implement by recursivelong factorial_recursive(long n){ if (n == 0) return 1; return n * factorial_recursive(n-1);}// factorial implement by looplong factorial_loop(long n){ long result = 1; for (int i = n; i > 0; -- i) result *= i; return result;}int main(){ for (int i = 0; i < 10; i ++ ) { cout << i << "!" << " = " << factorial_recursive(i) << "," << factorial_loop(i) << endl; } return 0;}
例2 Fibonacci数列
无穷数列1，1，2，3，5，8，13，21，34，55，……，称为Fibonacci数列。它可以递归地定义为：
F(n) = 1 n = 0 (边界条件)
F(n) = 1 n = 1 (递归方程)
F(n) = F(n - 1) + F(n - 2) n > 2 (递归方程)
实现：
/* 主题：fibonacci数列使用递归和非递归实现* 作者：chinazhangjie* 邮箱：chinajiezhang@gmail.com* 开发语言：C++* 开发环境：Code::Blocks 10.05* 时间: 2010.10.05*/#include <iostream>using namespace std;// fibonacci implement by recursivelong fibonacci_recursive(long n){ if (n <= 1 ) return 1; return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);}// fibonacci implement by looplong fibonacci_loop(long n){ if (n == 0 || n == 1) return 1; long f1 = 1; long f2 = 1; long result = 0; for (long i = 1; i < n ; ++ i) { result = f1 + f2; f1 = f2; f2 = result; } return result;}int main(){ cout << "fibonacci implement by recursive: " << endl; for (long i = 0; i <= 20; ++ i) cout << fibonacci_recursive(i) << " " ; cout << endl << endl; cout << "fibonacci implement by loop: " << endl; for (long i = 0; i <= 20; ++ i) cout << fibonacci_loop(i) << " " ; cout << endl; return 0;}
例3 Ackerman函数
当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。
Ackerman函数A(n，m)定义如下：
A(1,0) = 2
A(0,m) = 1 m >= 0
A(n,0) = n + 2 n >= 2
A(n,m) = A(A(n-1,m),m-1) n,m >= 1
前2例中的函数都可以找到相应的非递归方式定义：
n! = 1 * 2 * 3 * ... * (n - 1) * n
本例中的Ackerman
函数却无法找到非递归的定义。
A(n，m)的自变量m的每一个值都定义了一个单变量函数：
M = 0时，A(n,0)=n+2
M = 1时，A(n,1)=A(A(n-1,1),0) = A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*n
M = 2时，A(n,2) = A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 2^n。
M = 3时，类似的可以推出
M = 4时，A(n,4)
的增长速度非常快，以至于没有适当的数
学式子来表示这一函数。
实现：
/* 主题：ackerman函数使用递归实现* 作者：chinazhangjie* 邮箱：chinajiezhang@gmail.com* 开发语言：C++* 开发环境：Code::Blocks 10.05* 时间: 2010.10.05*/#include <iostream>using namespace std;// ackerman implementlong ackerman(long n,long m){ if (n == 1 && m == 0) return (long)2; if (n == 0) return 1; if (m == 0) return n + 2; return ackerman( ackerman(n-1,m) , m-1);}int main(){ cout << "m = 0 : " << endl; cout << "ackerman(1,0) = " << ackerman(1,0) << endl; cout << "ackerman(2,0) = " << ackerman(2,0) << endl; cout << "ackerman(3,0) = " << ackerman(3,0) << endl; cout << "ackerman(4,0) = " << ackerman(4,0) << endl; cout << "m = 1 : " << endl; cout << "ackerman(1,1) = " << ackerman(1,1) << endl; cout << "ackerman(2,1) = " << ackerman(2,1) << endl; cout << "ackerman(3,1) = " << ackerman(3,1) << endl; cout << "ackerman(4,1) = " << ackerman(4,1) << endl; cout << "m = 2 : " << endl; cout << "ackerman(1,2) = " << ackerman(1,2) << endl; cout << "ackerman(2,2) = " << ackerman(2,2) << endl; cout << "ackerman(3,2) = " << ackerman(3,2) << endl; cout << "ackerman(4,2) = " << ackerman(4,2) << endl; cout << "m = 3 : " << endl; cout << "ackerman(1,3) = " << ackerman(1,3) << endl; cout << "ackerman(2,3) = " << ackerman(2,3) << endl; cout << "ackerman(3,3) = " << ackerman(3,3) << endl; cout << "ackerman(4,3) = " << ackerman(4,3) << endl; return 0;}
例4排列问题
设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。
设R={r1,r2,…,rn}是要进行排列的n个元素，
Ri=R-{ri}
。
集合X中元素的全排列记为perm(X)。
(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下：
当n=1时，perm(R)=(r)，其中r是集合R
中唯一的元素；
当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。
/* 主题：全排列使用递归和非递归实现* 作者：chinazhangjie* 邮箱：chinajiezhang@gmail.com* 开发语言：C++* 开发环境：Code::Blocks 10.05* 时间: 2010.10.07*/#include <iostream>#include <vector>#include <iterator>using namespace std;/* 使用递归实现* 递归产生所有前缀是list[0:k-1]，* 且后缀是list[k,m]的全排列的所有排列* 调用算法perm(list,0,n-1)则产生list[0:n-1]的全排列*/template <class T>void perm_recursion(T list[],int k,int m){ // 产生list[k:m]的所有排列 if (k == m) { for (int i = 0; i <= m; i ++) cout << list[i] << " "; cout << endl; } else { // 还有多个元素，递归产生排列 for (int i = k; i <= m; ++ i) { swap(list[k],list[i]); perm_recursion(list,k+1,m); swap(list[k],list[i]); } }}// 非递归实现（可参照STL next_permutation源码）template <class T>void perm_loop(T list[],int len){ int i,j; vector<int> v_temp(len); // 初始排列 for(i = 0; i < len ; i ++) v_temp[i] = i; while (true) { for (i = 0; i < len; i ++ ) cout << list[v_temp[i]] << " "; cout << endl; // 从后向前查找，看有没有后面的数大于前面的数的情况，若有则停在后一个数的位置。 for(i = len - 1;i > 0 && v_temp[i] < v_temp[i-1] ; i--); if (i == 0) break; // 从后查到i，查找大于 v_temp[i-1]的最小的数，记入j for(j = len - 1 ; j > i && v_temp[j] < v_temp[i-1] ; j--); // 交换 v_temp[i-1] 和 v_temp[j] swap(v_temp[i-1],v_temp[j]); // 倒置v_temp[i]到v_temp[n-1] for(i = i,j = len - 1 ; i < j;i ++,j --) { swap(v_temp[i],v_temp[j]); } }}int main(){ int list[] = {0,1,2}; cout << "permutation implement by recursion: " << endl; perm_recursion(list,0,2); cout << endl; cout << "permutation implement by loop: " << endl; perm_loop(list,3); cout << endl; return 0;}
参考资料：《算法设计与分析基础》王晓东 编著
授课教师： 张阳教授
原文链接: https://www.cnblogs.com/chinazhangjie/archive/2010/10/07/1845034.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/15839
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
