文档介绍：递归与分治策略1*递归一个直接或间接地调用自身的算法称为递归算法。一个使用函数自身给出定义的函数称为递归函数。递归使到函数的定义和算法的描述简捷且易于理解。*例阶乘函数边界条件递归方程*边界条件与递归方程是递归函数的二个要素递归函数只有具备了这两个要素,才能在有限次计算后得出结果。*intFactorial(intn){ if(n==0)return1; returnn*Factorial(n–1);}*例Hanoi塔问题设a,b,c是3个塔座。开始时,在塔座a上有一叠共n个圆盘,这些圆盘自下而上,由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上,并仍按同样顺序叠置。*在移动圆盘时应遵守以下移动规则:规则1:每次只能移动1个圆盘;规则2:任何时刻都不允许将较大的圆盘压在较小的圆盘之上;规则3:在满足移动规则1和2的前提下,可将圆盘移至a,b,c中任一塔座上。*在问题规模较大时,较难找到一般的方法,因此我们尝试用递归技术来解决这个问题。当n=1时,问题比较简单。此时,只要将编号为1的圆盘从塔座a直接移至塔座b上即可。当n>1时,需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c,然后,将剩下的最大圆盘从塔座a移至塔座b,最后,再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。由此可见,n个圆盘的移动问题可分为2次n-1个圆盘的移动问题,这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题的递归算法如下。递归解法voidhanoi(intn,inta,intb,intc){if(n>0){hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);}}*例整数划分问题将正整数n表示成一系列正整数之和:n=n1+n2+…+nk,其中n1≥n2≥…≥nk≥1,k≥1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。*例如正整数6有如下11种不同的划分:6;5+1;4+2,4+1+1;3+3,3+2+1,3+1+1+1;2+2+2,2+2+1+1,2+1+1+1+1;1+1+1+1+1+1。