第2章 递归与分治策略
2.1 递归的概念
直接或间接调用自身为递归。
采用递归的目的（思路）是将一个较大（或较复杂）的问题分解成较小的相同问题。
使用递归方法时，一定要设置结束递归的边界条件。
递归的实现的关键是建立递归调用工作栈。（但使用时并不需要我们去建立，系统自动进行这个操作。）
递归的优点是形式简单，缺点是运行效率低（多次调用函数耗费大量时间、空间，问题规模较大时无法在规定时间内完成）。
【例-阶乘】 阶乘函数 n!
可用递归函数定义：
n! = 1 ,n=0
n(n-1)! ,n>0
递归函数必须有非递归定义（直接给定）的初始值。
第一式给出初始值，第二式给出用较小自变量表示较大自变量的函数值的式子。
用C++表示:
int factorial(int n) { if( n == 0) return 1; else return n*factorial(n-1); }
【例-斐波那契数列】
数列1,1,2,3,5,8,13,21,...为斐波那契数列。
F(n) = 1 , n = 0或1
F(n) = F(n-1)+F(n-2) n>1
C++表示:
int fibonacci(int n){ if (n<=1) return 1; else return fibonacci(n-1)+fibonacci(n-2); }
【例-Hanoi塔问题】
汉诺塔问题是一个经典的可用递归解决的问题。
问题简述：
设有3个塔座，记为a,b,c
开始时a上一共叠有n个圆盘，圆盘从下到上，由大到小地叠在一起。
要求把a上的n个圆盘移到b上，仍按照上小下大的顺序叠放。
规则是每次只能移动一个盘子，且大盘子不能压在小盘子上。
使用递归方法分析这个问题：
当n=1时，将这个盘子放在b上即可
n>1时，先把n-1个盘子放在c上，再把最大的那个放在b上，接着把n-1个盘子放在b上。
void hanoi(int n, int a, int b, int c) { //把a上的n个圆盘移到b上 if(n>0){ //n>0，（有盘子时执行下面操作，n=0就放完了，结束） hanoi(n-1,a,c,b); //把a上的n-1个圆盘移到c上，b是中转站 move(a,b); //移动剩下的那个大圆盘 hanoi(n-1,c,b,a); //将c上的n-1个圆盘移到b上，a是中转站 } }
2.2 分治法的基本思想
分治法的基本思想是将一个规模为n的问题 分解为 k个规模较小的子问题。子问题相互独立且与原问题相同。
递归地解这些子问题，然后将各子问题地解合并得到原问题的解。
【例-二分搜索技术】
给定以排序的n个元素a[0,n-1]，要在这n个元素里找一特定元素x。
若使用顺序搜索方法逐个比较x和a[]中的元素，最坏情况下要对比完所有的n个元素，时间复杂度O(n)。
使用二分搜索可在O(logn)时间完成搜索。基本思想如下：
将n个元素分为个数相当的两半，取a[n/2]与x比较，
若x= a[n/2]，找到x，算法终止；
若x<a[n/2]，则x在a[n/2]左侧，在a[n/2]左侧搜索；
若a>[n/2]，x在a[n/2]右侧，在a[n/2[右侧搜索。
template<class Type> int BinarySearch(Type a[],const Type& x,int n){ 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; if(x<a[middle]) right = middle-1; } return -1; }
