算法设计与分析—递归算法ppt课件

1、第6章 递归算法16.1 6.1 递归的概念递归的概念6.2 6.2 递归算法的执行过程递归算法的执行过程6.3 6.3 递归算法的设计方法递归算法的设计方法6.4 6.4 递归过程和运转时栈递归过程和运转时栈6.5 6.5 递归算法的效率分析递归算法的效率分析6.6 6.6 递归算法到非递归算法的转换递归算法到非递归算法的转换6.7 6.7 设计举例设计举例6.1递归的概念一、在日常生活中，递归一词较常用于描画以一、在日常生活中，递归一词较常用于描画以自类似方法反复事物的过程。自类似方法反复事物的过程。例如，当两面镜子相互之间近似平行时，镜中例如，当两面镜子相互之间近似平行时，镜中嵌套的图像

2、是以无限递归的方式出现的。嵌套的图像是以无限递归的方式出现的。 2德罗斯特效应英语：德罗斯特效应英语：Droste effectDroste effect是递归的一是递归的一种视觉方式。图中女性手持种视觉方式。图中女性手持的物体中有一幅她本人手持的物体中有一幅她本人手持同一物体的小图片，进而小同一物体的小图片，进而小图片中还有更小的一幅她手图片中还有更小的一幅她手持同一物体的图片，依此类持同一物体的图片，依此类推。推。3二、在数学与计算机科学中，递归是指在函数二、在数学与计算机科学中，递归是指在函数的定义中运用函数本身的方法。的定义中运用函数本身的方法。例：第例：第5 5个人的年龄比第个人的年

3、龄比第4 4个的年龄大个的年龄大2 2岁，有岁，有4 4个人的年龄比第个人的年龄比第3 3个的年龄大个的年龄大2 2岁，有岁，有3 3个人的个人的年龄比第年龄比第2 2个的年龄大个的年龄大2 2岁，有岁，有2 2个人的年龄比个人的年龄比第第1 1个的年龄大个的年龄大2 2岁，第岁，第1 1个的年龄个的年龄1010岁。岁。4例：阶乘的定义。例：阶乘的定义。5时当时当01.) 1(01!nnnnn6在下面二种情况中存在算法调用本人的情况：在下面二种情况中存在算法调用本人的情况：1 1问题的定义是递推的问题的定义是递推的阶乘函数的常见定义是：阶乘函数的常见定义是：时当时当01.) 1(01!nnnn

4、n7也可定义为：也可定义为：写成函数方式，那么为：写成函数方式，那么为： 这种函数定义的方法是用阶乘函数本人本身定义了这种函数定义的方法是用阶乘函数本人本身定义了阶乘函数，称上式为阶乘函数的递推定义式。阶乘函数，称上式为阶乘函数的递推定义式。时当时当0)!1(01!nnnnn时当时当0) 1(*01)(nnfnnnf82问题的解法存在自调用问题的解法存在自调用 一个典型的例子是在有序数组中查找一个数据元素能否一个典型的例子是在有序数组中查找一个数据元素能否存在的折半查找算法。存在的折半查找算法。 如下例中查找元素如下例中查找元素1717。第一次第一次:下标下标01234567元素值元素值134

5、517183133lowmidhighxamid第二次第二次:下标下标01234567元素值元素值134517183133lowmidhighxamid第三次第三次:下标下标01234567元素值元素值134517183133lowhighx=amidmidBSrch=4mid=(low+high)/296.2递归算法的执行过程 例例6-1 6-1 给出按照阶乘函数的递推定义式计算阶乘函数的给出按照阶乘函数的递推定义式计算阶乘函数的递归算法，并给出递归算法，并给出n = 3n = 3时递归算法的执行过程。时递归算法的执行过程。 设计：按照阶乘函数的递推定义式计算阶乘函数的递归设计：按照阶乘函数

6、的递推定义式计算阶乘函数的递归算法如下：算法如下： long int Fact(int n) int x; long int y; if(n 0) /n high) return -1;/查找不胜利查找不胜利 mid = (low + high) / 2;if(x = amid)return mid; /查找胜利查找胜利else if(x amid) return BSearch(a, x, low, mid-1);/在下半区查找在下半区查找elsereturn BSearch(a, x, mid+1, high);/在上半区查找在上半区查找14测试代码设计如下：测试代码设计如下：# incl

7、ude # include main(void)main(void) int a = 1, 3, 4, 5, 17, int a = 1, 3, 4, 5, 17, 18, 31, 33;18, 31, 33; int x = 17; int x = 17; int bn; int bn; bn = BSearch(a, x, 0,7); bn = BSearch(a, x, 0,7); if(bn = -1) printf(x if(bn = -1) printf(x不在不在数组数组a a中中);); else printf(x else printf(x在数组在数组a a的下的下标标%d%

8、d中中, bn);, bn); 15BSearch(a, x, 0,7)BSearch(a, x, 0,7)的递归调用过程如以下图所示，的递归调用过程如以下图所示，其中，实箭头表示过程调用，虚箭头表示过程的前往值。其中，实箭头表示过程调用，虚箭头表示过程的前往值。 BSearch(a, x, 0, 7) mid=3 return BSearch(a, x, 4, 7)main() x=17 bn = BSearch(a, x, 0, 7)BSearch(a, x, 4, 7) mid=5 return BSearch(a, x, 4, 4)BSearch(a, x, 4, 4) mid=4 r

9、eturn 4444166.3递归算法的设计方法 递归算法既是一种有效的算法设计方法，递归算法既是一种有效的算法设计方法，也是一种有效的分析问题的方法。递归算法求也是一种有效的分析问题的方法。递归算法求解问题的根本思想是：对于一个较为复杂的问解问题的根本思想是：对于一个较为复杂的问题，把原问题分解成假设干个相对简单且类同题，把原问题分解成假设干个相对简单且类同的子问题，这样较为复杂的原问题就变成了相的子问题，这样较为复杂的原问题就变成了相对简单的子问题；而简单到一定程度的子问题对简单的子问题；而简单到一定程度的子问题可以直接求解；这样，原问题就可递推得到解。可以直接求解；这样，原问题就可递推得

10、到解。17 并不是每个问题都适宜于用递归算法求解。适宜并不是每个问题都适宜于用递归算法求解。适宜于用递归算法求解的问题的充分必要条件是：于用递归算法求解的问题的充分必要条件是：1 1问题具有某种可借用的类同本身的子问题描画的问题具有某种可借用的类同本身的子问题描画的性质；性质；2 2某一有限步的子问题也称作本原问题有直接某一有限步的子问题也称作本原问题有直接的解存在。的解存在。18 当一个问题存在上述两个根本要素时，设计该问当一个问题存在上述两个根本要素时，设计该问题的递归算法的方法是：题的递归算法的方法是：1 1把对原问题的求解设计成包含有对子问题求解的把对原问题的求解设计成包含有对子问题求

11、解的方式。方式。2 2设计递归出口。设计递归出口。19 例例6-3 6-3 设计模拟汉诺塔问题求解过程的算法。汉设计模拟汉诺塔问题求解过程的算法。汉诺塔问题的描画是：设有诺塔问题的描画是：设有3 3根标号为根标号为A A，B B，C C的柱子，的柱子，在在A A柱上放着柱上放着n n个盘子，每一个都比下面的略小一点，个盘子，每一个都比下面的略小一点，要求把要求把A A柱上的盘子全部移到柱上的盘子全部移到C C柱上，挪动的规那么是：柱上，挪动的规那么是：1 1一次只能挪动一个盘子；一次只能挪动一个盘子；2 2挪动过程中大盘挪动过程中大盘子不能放在小盘子上面；子不能放在小盘子上面；3 3在挪动过程

12、中盘子可在挪动过程中盘子可以放在以放在A A，B B，C C的恣意一个柱子上。的恣意一个柱子上。问题分析：可以用递归方法求解问题分析：可以用递归方法求解n n个盘子的汉诺塔问个盘子的汉诺塔问题。题。20根本思想：根本思想：1 1个盘子的汉诺塔问题可直接挪动。个盘子的汉诺塔问题可直接挪动。n n个盘子的汉诺塔个盘子的汉诺塔问题可递归表示为，首先把上边的问题可递归表示为，首先把上边的n-1n-1个盘子从个盘子从A A柱移柱移到到B B柱，然后把最下边的一个盘子从柱，然后把最下边的一个盘子从A A柱移到柱移到C C柱，最柱，最后把移到后把移到B B柱的柱的n-1n-1个盘子再移到个盘子再移到C C柱

13、。柱。4 4个盘子汉诺塔问题的递归求解表示图如以下图所示。个盘子汉诺塔问题的递归求解表示图如以下图所示。 21n-1n原柱原柱 A 辅助柱辅助柱 B 目的柱目的柱 C 22 算法设计：首先，盘子的个数算法设计：首先，盘子的个数n n是必需的一个输入参是必需的一个输入参数，对数，对n n个盘子个盘子, ,我们可从上至下依次编号为我们可从上至下依次编号为1,2,n1,2,n；其；其次，输入参数还需有次，输入参数还需有3 3个柱子的代号个柱子的代号, ,我们令我们令3 3个柱子的参个柱子的参数名分别为数名分别为fromPegfromPeg，auxPegauxPeg和和toPegtoPeg；最后，汉诺

14、塔问题；最后，汉诺塔问题的求解是一个处置过程，因此算法的输出是的求解是一个处置过程，因此算法的输出是n n个盘子从柱个盘子从柱子子fromPegfromPeg借助柱子借助柱子auxPegauxPeg挪动到柱子挪动到柱子toPegtoPeg的挪动步骤，的挪动步骤，我们设计每一步的挪动为屏幕显示如下方式的信息：我们设计每一步的挪动为屏幕显示如下方式的信息：Move Disk i from Peg X to Peg YMove Disk i from Peg X to Peg Y这样，汉诺塔问题的递归算法可设计如下：这样，汉诺塔问题的递归算法可设计如下： 23void towers(int n, c

15、har fromPeg, char toPeg, char auxPeg) if(n=1)/递归出口递归出口 printf(%s%c%s%cn, move disk 1 from peg , fromPeg, to peg , toPeg); return; /把把n-1个圆盘从个圆盘从fromPeg借助借助toPeg移至移至auxPeg towers(n-1,fromPeg,auxPeg,toPeg); /把圆盘把圆盘n由由fromPeg直接移至直接移至toPeg printf(%s%d%s%c%s%cn, move disk , n, from peg , fromPeg, to peg

16、, toPeg); /把把n-1个圆盘从个圆盘从auxPeg借助借助fromPeg移至移至toPeg towers(n-1,auxPeg,toPeg,fromPeg);24测试代码如下：测试代码如下：#include #include void main(void)void main(void) Towers(4, A, C, B); Towers(4, A, C, B); 程序运转的输出信息如下：程序运转的输出信息如下：25Move Disk 1 from Peg A to Peg BMove Disk 2 from Peg A to Peg CMove Disk 1 from Peg B

17、to Peg CMove Disk 3 from Peg A to Peg BMove Disk 1 from Peg C to Peg AMove Disk 2 from Peg C to Peg BMove Disk 1 from Peg A to Peg BMove Disk 4 from Peg A to Peg CMove Disk 1 from Peg B to Peg CMove Disk 2 from Peg B to Peg AMove Disk 1 from Peg C to Peg AMove Disk 3 from Peg B to Peg CMove Disk 1 f

18、rom Peg A to Peg BMove Disk 2 from Peg A to Peg CMove Disk 1 from Peg B to Peg C26结合本节和结合本节和6.26.2节的讨论，我们可总结如节的讨论，我们可总结如下：递归算法的执行过程是不断地自调用，直下：递归算法的执行过程是不断地自调用，直到到达递归出口才终了自调用过程；到达递归到到达递归出口才终了自调用过程；到达递归出口后，递归算法开场按最后调用的过程最先出口后，递归算法开场按最后调用的过程最先前往的次序前往；前往到最外层的调用语句时前往的次序前往；前往到最外层的调用语句时递归算法执行过程终了。递归算法执行过程终

19、了。 276.4递归过程和运转时栈 对于非递归函数，调用函数在调用被调用函对于非递归函数，调用函数在调用被调用函数前，系统要保管以下两类信息：数前，系统要保管以下两类信息： 1 1调用函数的前往地址从而能执行下一调用函数的前往地址从而能执行下一语句；语句； 2 2调用函数的部分变量值。调用函数的部分变量值。 当执行完被调用函数，前往调用函数前，系当执行完被调用函数，前往调用函数前，系统首先要恢复调用函数的部分变量值，然后前往统首先要恢复调用函数的部分变量值，然后前往调用函数的前往地址。调用函数的前往地址。递归函数被调用时，系统要做的任务和非递递归函数被调用时，系统要做的任务和非递归函数被调用时

20、系统要作的任务在方式上类同，归函数被调用时系统要作的任务在方式上类同，但保管信息的内容和方法不同。但保管信息的内容和方法不同。28保管内容：保管内容： 每一层递归调用所需求保管的信息构成一个任务记录，每一层递归调用所需求保管的信息构成一个任务记录，通常包括如下内容：通常包括如下内容： 1 1本次递归调用中的部分变量值；本次递归调用中的部分变量值； 2 2前往地址，即本次递归过程调用语句的后继语前往地址，即本次递归过程调用语句的后继语句的地址；句的地址； 3 3本次调用中与形参结合的实参值，包括函数名、本次调用中与形参结合的实参值，包括函数名、援用参数与数值参数等。援用参数与数值参数等。29保管

21、方法保管方法: : 递归函数被调用时，系统在运转递归函数前也要保管上递归函数被调用时，系统在运转递归函数前也要保管上述两类信息。但由于递归的函数的运转特点，是最后被调用述两类信息。但由于递归的函数的运转特点，是最后被调用的函数要最先被前往，假设按非递归函数那样保管信息，显的函数要最先被前往，假设按非递归函数那样保管信息，显然要出错。然要出错。 由于堆栈的后进先出特性正好与递归函数调用和前往的由于堆栈的后进先出特性正好与递归函数调用和前往的过程吻合，因此，高级程序设计言语利用堆栈保管递归函数过程吻合，因此，高级程序设计言语利用堆栈保管递归函数调用的信息，系统用于保管递归函数调用信息的堆栈称为运调

22、用的信息，系统用于保管递归函数调用信息的堆栈称为运转时栈。转时栈。 运转时栈表示图运转时栈表示图栈顶栈顶栈底栈底局部变量局部变量m 返回地址返回地址m 参参 数数m局部变量局部变量2返回地址返回地址2参参 数数2局部变量局部变量1返回地址返回地址1参参 数数130 递归函数被调用时，在每进入下一层递归调用时，系递归函数被调用时，在每进入下一层递归调用时，系统就建立一个新的任务记录，并把这个任务记录进栈成为统就建立一个新的任务记录，并把这个任务记录进栈成为运转时栈新的栈顶；每前往一层递归调用，就退栈一个任运转时栈新的栈顶；每前往一层递归调用，就退栈一个任务记录。务记录。 由于栈顶的任务记录必定是

23、当前正在运转的递归函数由于栈顶的任务记录必定是当前正在运转的递归函数的任务记录，所以栈顶的任务记录也称为活动记录。的任务记录，所以栈顶的任务记录也称为活动记录。 任务记录任务记录活动记录活动记录运转时栈表示图运转时栈表示图栈顶栈顶栈底栈底局部变量局部变量m 返回地址返回地址m 参参 数数m局部变量局部变量2返回地址返回地址2参参 数数2局部变量局部变量1返回地址返回地址1参参 数数1我们以计算阶乘的递归函数为例，阐明递归函数调用我们以计算阶乘的递归函数为例，阐明递归函数调用时运转时栈中任务记录的变化过程。时运转时栈中任务记录的变化过程。31long Fact( int n) int x; lo

24、ng y; If n = 0 return 1; else x = n-1; y = Fact(x); return n * y; 由于函数的地址是系统动态分配的，调用函数的前往地址因此由于函数的地址是系统动态分配的，调用函数的前往地址因此也是动态变化的，不好给出详细数值，故以下图中没有给出调用函也是动态变化的，不好给出详细数值，故以下图中没有给出调用函数的前往地址。数的前往地址。32 栈顶栈顶 3 2 1栈底栈底 0nxyFact初始时初始时运转时栈的变化过程运转时栈的变化过程 栈顶栈顶 321栈底栈底 03*nxyFact调用调用Fact(3) 栈顶栈顶 3212*栈底栈底 032*nxy

25、Fact调用调用Fact(2) 栈顶栈顶 321*121*栈底栈底 032*nxyFact调用调用Fact(1) 栈顶栈顶 30*1210121*栈底栈底 032*nxyFact调用调用Fact(0) 栈顶栈顶 321011121*栈底栈底 032*nxyFact返回返回Fact(0) 栈顶栈顶 3212112栈底栈底 032*nxyFact返回返回Fact(1) 栈顶栈顶 321栈底栈底 03226nxyFact返回返回Fact(2) 栈顶栈顶 3 2 1栈底栈底 0nxyFact返回返回Fact(3)long Fact( int n) int x; long y; If n = 0 ret

26、urn 1; else x = n-1; y = Fact(x); return n * y; 336.5递归算法的效率分析 我们先以斐波那契我们先以斐波那契(Fibonacci)(Fibonacci)数列递归算法数列递归算法的执行效率为例来讨论递归算法的执行效率问题。的执行效率为例来讨论递归算法的执行效率问题。 斐波那契数列斐波那契数列Fib(n)Fib(n)的递推定义是：的递推定义是：如如Fib(0)=0,Fib(1)=1,Fib(2)=1,Fib(3)=2,Fib(0)=0,Fib(1)=1,Fib(2)=1,Fib(3)=2,Fib(4)=3,Fib(5)=5,Fib(n)=Fib(4

27、)=3,Fib(5)=5,Fib(n)=时当时当时当12)-Fib(1)-Fib(1100)(Fibnnnnnnnn2512515134求第求第n n项斐波那契数列的递归函数过程如下：项斐波那契数列的递归函数过程如下： long Fib(int n) if(n = 0 | n = 1) return n; /递归出口递归出口 else return Fib(n-1) + Fib(n-2); /递归调用递归调用35 求求Fib(5)Fib(5)的递归计算过程如下图。的递归计算过程如下图。 Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)

28、Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)斐波那契数列斐波那契数列Fib(5)Fib(5)的递归调用树的递归调用树36 为了计算为了计算Fib(5)，需求先计算，需求先计算Fib(4)和和Fib(3)；而计算而计算Fib(4)又需求计算又需求计算Fib(3)再一次计算和再一次计算和Fib(2)， . 由上图可知，为了计算由上图可知，为了计算Fib(5)，需求计算，需求计算1次次Fib(4)，2次次Fib(3)，3次次Fib(2)，5次次Fib(1)，3次次Fib(0). 加上加上Fib(5)1次，一切的递归调用次数到达次，一切的递归调用次数到达15次。图中次。图中

29、15个点表示个点表示15次运算次运算 更普通地，设更普通地，设Fib(n)需求总的递归调用次数为需求总的递归调用次数为NumCall(n)，那么，那么NumCall(n)等于多少？等于多少？NumCall(n)= NumCall(n-1)+ NumCall(n-2)+1NumCall(0)=1, NumCall(1)=1 可以求得可以求得NumCall的通项。也可以由下面的关系得的通项。也可以由下面的关系得到到NumCall的通项。的通项。NumCall(n) = 2*Fib(n+1) - 1。 可以证明，计算斐波那契数列的递归函数可以证明，计算斐波那契数列的递归函数Fib(n)的的时间复杂度

30、为时间复杂度为O(2n)。37计算斐波那契数列计算斐波那契数列Fib(n)问题，我们也可根据公问题，我们也可根据公式写出循环方式求解的函数如下：式写出循环方式求解的函数如下：3839long Fib2(int n) long int oneBack, twoBack, current; int i; if(n = 0 | n = 1) return n; else oneBack = 1; twoBack = 0; for(i = 2; i = n; i+) current = oneBack + twoBack; twoBack = oneBack; oneBack = current; r

31、eturn current;40 上述循环方式的计算斐波那契数列的函数上述循环方式的计算斐波那契数列的函数Fib2(n)的时间复杂度为的时间复杂度为O(n)。对比循环构造的。对比循环构造的Fib2(n)和递归构造的和递归构造的Fib(n)可发现可发现: 循环构造的循环构造的Fib2(n)算法在计算第算法在计算第n项的斐波那项的斐波那契数列时保管了当前曾经计算得到的第契数列时保管了当前曾经计算得到的第n-1项和第项和第n-2项的斐波那契数列，因此其时间复杂度为项的斐波那契数列，因此其时间复杂度为O(n)； 而递归构造的而递归构造的Fib(n)算法在计算第算法在计算第n项的斐波项的斐波那契数列时，

32、必需首先计算第那契数列时，必需首先计算第n-1项和第项和第n-2项的斐项的斐波那契数列，而某次递归计算得出的斐波那契数列，波那契数列，而某次递归计算得出的斐波那契数列，如如Fib(n-1)、Fib(n-2)等无法保管，下一次要用到等无法保管，下一次要用到时还需求重新递归计算，因此其时间复杂度为时还需求重新递归计算，因此其时间复杂度为O(2n) 。 下面我们再看看汉诺塔的时间复杂度。下面我们再看看汉诺塔的时间复杂度。设挪动设挪动n个盘子的步数为个盘子的步数为H(n)，我们再看看表示，我们再看看表示图。图。4142n-1n这一步这一步实践有实践有H(n-1)步步这只这只需需1步步这一步又需这一步又

33、需求求H(n-1)步步故挪动故挪动n个圆盘的总步数个圆盘的总步数H(n)=H(n-1)+1+H(n-1) =2H(n-1)+1原柱原柱 A 辅助柱辅助柱 B 目的柱目的柱 C 即有即有 H(n)=2H(n-1)+1 S(1)=1可以解得：可以解得：H(n)=2n-1因此汉诺塔的时间复杂度为因此汉诺塔的时间复杂度为O(2n) 。43446.6递归算法到非递归算法的转换 有些问题需求用低级程序设计言语来实现，而低级有些问题需求用低级程序设计言语来实现，而低级程序设计言语如汇编言语普通不支持递归，此时程序设计言语如汇编言语普通不支持递归，此时需求采用问题的非递归构造算法。普通来说，存在如需求采用问题

34、的非递归构造算法。普通来说，存在如下两种情况的递归算法。下两种情况的递归算法。 1 1存在不借助堆栈的循环构造的非递归算法，如存在不借助堆栈的循环构造的非递归算法，如阶乘计算问题、斐波那契数列的计算问题、折半查找阶乘计算问题、斐波那契数列的计算问题、折半查找问题等。问题等。 2 2存在借助堆栈的循环构造的非递归算法，一切存在借助堆栈的循环构造的非递归算法，一切递归算法都可以借助堆栈转换成循环构造的非递归算递归算法都可以借助堆栈转换成循环构造的非递归算法，如汉诺塔问题可以借助堆栈的循环构造实现非递法，如汉诺塔问题可以借助堆栈的循环构造实现非递归算法。归算法。45 对于第一种情况，可以直接选用循环

35、构造对于第一种情况，可以直接选用循环构造的算法。的算法。 对于第二种情况，可以把递归算法转换成对于第二种情况，可以把递归算法转换成相应的非递归算法，此时有两种转换方法：一相应的非递归算法，此时有两种转换方法：一种方法是借助堆栈，用非递归算法方式化模拟种方法是借助堆栈，用非递归算法方式化模拟递归算法的执行过程；另一种方法是根据要求递归算法的执行过程；另一种方法是根据要求解问题的特点，设计借助堆栈的循环构造算法。解问题的特点，设计借助堆栈的循环构造算法。这两种方法都需求运用堆栈，这是由于堆栈的这两种方法都需求运用堆栈，这是由于堆栈的后进先出特点正好和递归函数的运转特点相吻后进先出特点正好和递归函数

36、的运转特点相吻合。合。 通常，一个递归算法的模拟算法的复杂度通常，一个递归算法的模拟算法的复杂度与其本身的复杂度一样。与其本身的复杂度一样。46 例例6-6 6-6 借助堆栈模拟系统的运转时进栈、借助堆栈模拟系统的运转时进栈、出栈过程，把汉诺塔问题的递归算法转化为非出栈过程，把汉诺塔问题的递归算法转化为非递归算法，并分析非递归算法的时间复杂度。递归算法，并分析非递归算法的时间复杂度。476.7设计举例6.7.1 6.7.1 普通递归算法设计举例普通递归算法设计举例 例例6-5 6-5 设计一个输出如下方式数值的递归算法。设计一个输出如下方式数值的递归算法。n n n . nn n n . n.

37、 . 3 3 3 3 3 3 2 22 21 148问题分析：该问题可以看成由两部分组成：一部分是输出一问题分析：该问题可以看成由两部分组成：一部分是输出一行值为行值为n的数值；另一部分是原问题的子问题，其参数为的数值；另一部分是原问题的子问题，其参数为n-1。当参数减到当参数减到0时不再输出任何数据值，因此递归的出口是当时不再输出任何数据值，因此递归的出口是当参数参数n0时空语句前往。时空语句前往。 void Display(int n) int i; for(i = 1; i = n; i+) coutsetw(s)n; cout 0) Display(n - 1);/递归递归 /n=0为

38、递归出口，递归出口为空语句为递归出口，递归出口为空语句 49例例6-6 设计求解委员会问题的算法。委员会问题是：从一个设计求解委员会问题的算法。委员会问题是：从一个有有n个人的团体中抽出个人的团体中抽出k (kn)个人组成一个委员会，计算共个人组成一个委员会，计算共有多少种构成方法。有多少种构成方法。问题分析：从问题分析：从n个人中抽出个人中抽出k(kn)个人的问题是一个组合问个人的问题是一个组合问题。即求组合数公式题。即求组合数公式C(n,k)。由于要所用递归算法。由于要所用递归算法,大家容大家容易想到公式易想到公式:C(n,k)=C(n-1,k-1)+C(n-1,k),这个公式大家可以这样

39、了解这个公式大家可以这样了解:把把n个人固定位置后，从个人固定位置后，从n个人个人中抽出中抽出k个人的问题可分解为两部分之和：第一部分是第一个人的问题可分解为两部分之和：第一部分是第一个人包括在个人包括在k个人中，第二部分是第一个人不包括在个人中，第二部分是第一个人不包括在k个人个人中。对于第一部分，那么问题简化为从中。对于第一部分，那么问题简化为从n-1个人中抽出个人中抽出k-1个个人的问题；对于第二部分，那么问题简化为从人的问题；对于第二部分，那么问题简化为从n-1个人中抽个人中抽出出k个人的问题。个人的问题。50 当当n=k或或k=0时，该问题可直接求解，数值均为时，该问题可直接求解，数值均为1，这是，这是算法的递归出口。因此，委员会问题的递推定义式为：算法的递归出口。因此，委员会问题的递推定义式为： int Comm(int n, int k) if(n 1 | k n) return 0; if(k = 0) return 1; if(n = k) return 1; return Comm(n-1, k-1) + Comm(n-1, k); 其它时当时当)1,-Comm(1)-1,-C