一.递归的概念：直接或间接地调用自身的算法成为递归算法。用函数自身给出定义的函数成为递归函数。
1.1递归解决阶乘函数。定义=(n是非负整数，n的阶乘是n*(n-1)......2*1)
int factorial(int n)
{
if(n == 0)return 1;
return n * factorial(n - 1);
}
1.2递归解决Fibonacci（斐波那契）数列。定义=当n〉时，数列的第n项是他前面两项之和，初始值F（0）和F（1）都==1。
int fibonacci(int n)
{
if(n <= 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
1.3递归解决排列问题。R的全排列定义=当n=1时，全排列Perm（R） = （r），其中r是集合R中唯一的元素；
当n>1时，Perm（R）由（r1）Perm(R1),(r2)Perm(R2),...,(rn)Perm(Rn）构成
template<class Type>
void Perm(Type list[], int k, int m)//k是待排列数组的起始位，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++)//递归调用时，对剩下的k->m之间的数，继续排列。
{
Swap(list[k], list[i]);
Perm(list, k + 1, m);
Swap(list[k], list[i]);
}
}
}
void Swap(Type &a, Type &b)
{
Type temp = a;a = b; b = temp;
}
1.4递归解决Hanoi塔问题。定义=有a,b,c三个塔座，a上自下而上，由大到小叠有n个圆盘。要求将塔座a上的所有圆盘移动b上，并仍按同样顺序叠置。移动过程中遵循的规则：1）每次只能移动一个圆盘2）任何时刻都不允许小的圆盘上有大的3）满足1）2)的前提下，可将圆盘移到a，b,c中任一塔座上。
基本解决思路：移动过程中，奇数次移动，将最小的顺时针（a->b->c->a）移到下一塔座；偶数次移动，最小的不动，其他两个塔座间，次小的移到另一个塔座上。
递归解决思路：n=1时，直接移动。n>1时，设法将n-1个较小的移到c上，然后将剩下的最大的从a移到b上；在设法将c上n-1个较小的从c移到b。
void hanoi(int n, int a,int b,int c)//a,b,c可看做三个塔座a,b,c;n是n个圆盘
{
if（n > 0）
{
hanoi(n - 1, a, c, b);
move(a,b);
//模拟移动动作
hanoi(n - 1, c, b, a);
}
}
二.分治法的基本思想：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题，互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
一个分治法，将规模为n的问题分成k个规模为n/m的子问题去解。为方便起见，设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。另外，再设将原问题分解为k个子问题及用merge将k个子问题的解合并为原问题的解需用f（n）个单位时间。如果用T（n）表示该分治法divide-and-conquer（P）解规模为|P|=n的问题所需的计算时间，则有T（n）=O（1） n=1；T（n）=kT(n/m) + f(n).
它的一般的算法设计模式如下：
divide-and-conquer(P)
{
if(|P| <= n0) adhoc(P);
divide P into small subinstances P1,P2,···,Pk;
for(int i = 1; i <= k; i++)
{
yi = divide-and-conquer(Pi);
return merge(y1,y2,···，yk);
}
}
2.1分治法解决二分搜索技术。定义=给定已经排好序的n个元素a[a:n-1],现在要在这n个元素中找出一特定元素x。采用分治策略，最坏情况下用O(logn)时间完成搜索任务。
基本思路：将n个元素分成个数大致相同的两半，取a[n/2]与x比较。如果，x=a[n/2],则找到x，算法终止；如果x<a[n/2],则只要在数组a的左半部继续搜索x；如果x>a[n/2],则只要在数组a的右半部继续搜索x。
template<class Type>
int BinarySearch(Type a[], const Type&, int n)
{//在a[0]到a[n-1]中搜索x
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分治法解决大整数的乘法。定义=需要处理的数无法在计算机硬件对整数的表示范围内直接处理，就必须用软件的方法来实现大整数的算术运算，如果将每两个一位数的乘法或加法看做一步运算，这种方法要进行O(n~2)步才能求出乘积XY。用分治法来设计将更有效地解决这个问题。X=A2~(n/2) + B,Y=C2~（n/2） +D.按此式相乘几乎没有改进算法。写成另外一种形式：XY=AC2~n + ((A-B)(D-C) +AC + BD)2~(n/2) +BD,此式看似复杂，但对于计算机运算来说，效率有了很大改进，T(n)由O(n~2)变为O(n~1.59).
2.3分治法解决Strassen矩阵乘法。定义=对于A和B的乘积矩阵C，每计算一个元素c（ij），需要做n次乘法和n-1次加法。因此，求出矩阵C的n~2个元素所需的计算时间是O(n~3)。
分治法解决思路：假设n是2的幂，将矩阵A，B，C中每一矩阵都分块成4个大小相等的子矩阵，每个子矩阵都是n/2 * n/2的方阵,对这个小方阵，改进一下，则2阶方阵用少于原来8次的乘法运算7次，但增加了加、减法的运算次数。用此法改进了算法，T(n)=O(n~2.81).
2.4分治法解决合并排序。定义=合并排序算法是用分治策略实现对n个元素进行排序的算法
基本思想：将待排序元素分成大小大致相同的两个子集合，分别对两个子集合进行排序，最终将排好序的子集合合并成所要求的排好序的集合。
合并排序算法可递归地描述如下：
template<class Type>
void MergerSort(Type a[], int left, int right)
{
if(left < right)//至少有2个元素
{
int middle = (left + right)/2;//取中点
MergeSort(a, left, middle);
MergerSort(a, middle + 1, right);
Merge(a, b, left, middle, right);//合并到数组b
Copy(a, b, left, right);//赋值回数组a
}
}
template<class Type>
void Merge(Type c[], Type d[], int n, int m, int r)
{//合并c[n:m]和c[m+1:r]到d[n:r]
int i = n, j = m + 1, k = n;
while((i <= m) && (j <= r))
{
if(c[i] <= c[j]) d[k++] = d[i++];
else d[k++] = c[j++];
}
if(i > m)
for(; j <= r; j++) d[k++] = c[j];
else for(; i <= m; i++) d[k++] = c[i];
}
消去递归后的合并排序算法可描述如下：
此处略去。
2.5分治法解决快速排序。定义=快速排序算法是基于分治策略的另一个排序算法那。
基本思想：对于输入的子数组a[p:r]，按以下三个步骤进行排序。
1）分解：以a[p]为基准，分数组为两部分，左边的均小于a[p],右边的均大于a[p]。
2）递归求解：通过递归调用快速排序法分别对a[p:q-1]和a[q+1:r]进行排序。
3）合并：对两部分排好序后，不需要任何计算，a[p:r]就已经排好序了。
template<class Type>
void QuickSort(Type a[], int p, int r)
{
if(p < r)
{
int q = Partition(a,p,r);
QuickSort(a, p, q - 1);//对左半段排序
QuickSort(a, q + 1, r);//对右半段排序
}
}
tempplate<class Type>
int Partition(Type a[], int p, int r)
{
int i = p,j = r + 1;
Type x = a[p];
//将小于x的元素交换到左边区域
//将大于x的元素交换到右边区域
while(true)
{
while(a[++i] < x && i < r);
while(a[--j] >);
if(i >= j) break;
Swap(a[i], a[j]);
a[j] = x;
return j;
}
}
