(精品)jidao-chap6递归算法设计（1）.ppt

《(精品)jidao-chap6递归算法设计（1）.ppt》由会员分享，可在线阅读，更多相关《(精品)jidao-chap6递归算法设计（1）.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第五章第五章 函数函数-递归递归选自：选自：计算机导论与程序设计基础计算机导论与程序设计基础 第第6章以及第章以及第16章的章的16.1C程序设计教程程序设计教程 5.135.151 1.递归的概念递归的概念2.递归过程递归过程3.递归程序设计递归程序设计提纲提纲2 1.递归的概念递归的概念递归算法递归算法在可计算性理论中占有重要地位，它在可计算性理论中占有重要地位，它是算法设计的有力工具，对于拓展编程思路非是算法设计的有力工具，对于拓展编程思路非常有用。就递归算法而言并不涉及高深数学知常有用。就递归算法而言并不涉及高深数学知识，只不过初学者要建立起递归概念不十分容识，只不过初学者要建立起递

2、归概念不十分容易。易。我们先从一个最简单的例子导入。我们先从一个最简单的例子导入。3 1.递归的概念递归的概念例例1：编写一个函数：编写一个函数fac，计算阶乘，计算阶乘n!按过去按过去的迭代算法的迭代算法，该函数可以写成：，该函数可以写成：int fac(int n)int i,p;p=1;for(i=2;i=n;i+)p=p*i;return p;4 现在换一个角度考虑，现在换一个角度考虑，n！不仅是！不仅是123n,还可以定义成：还可以定义成：int f(int n)if(n=0)return 1;else return n*f(n-1);1 当当n0 n!n(n1)!当当n01.递归的

3、概念递归的概念设设 f(n)=n!1 当当n0则则 f(n)nf(n-1)当当n0根据以上数学定义，函数根据以上数学定义，函数f能否写成能否写成左边所示？左边所示？函数能否调用自身？函数能否调用自身？答案是肯定的答案是肯定的!C系统会保系统会保证调用过程的正确性，这证调用过程的正确性，这就是递归！就是递归！5 递归的定义：递归的定义：u 从程序书写来看，在定义一个函数从程序书写来看，在定义一个函数时，若在函数的功能实现部分又出现时，若在函数的功能实现部分又出现对它本身的调用，则称该函数是递归对它本身的调用，则称该函数是递归的或递归定义的。的或递归定义的。u 从函数动态运行来看，当调用一个函从函

4、数动态运行来看，当调用一个函数数A时，在进入函数时，在进入函数A且还没有退出且还没有退出（返回）之前，又再一次由于调用（返回）之前，又再一次由于调用A本身而进入函数本身而进入函数A，则称之为函数，则称之为函数A的的递归调用。递归调用。int f(int n)if(n=0)return 1;else return n*f(n-1);6 递归可以分为直接递归和间接递归两种。递归可以分为直接递归和间接递归两种。直接递归直接递归：函数体里面发生对自己的调用；：函数体里面发生对自己的调用；间接递归间接递归：函数：函数A A调用函数调用函数B B，而函数而函数B B又直接或又直接或间接地调用函数间接地调用

5、函数A A。1.递归的概念递归的概念A()B();B()A();A()A();直直接接递递归归间间接接递递归归7 1.递归的概念递归的概念不用担心函数不用担心函数A内部又调用函数内部又调用函数A，会使得调用无休无，会使得调用无休无止，肯定存在某个条件，当该条件成立的时候，函数止，肯定存在某个条件，当该条件成立的时候，函数A将不会再调用自身。将不会再调用自身。例如，求例如，求n！时，该结束条件是！时，该结束条件是 if(n=0)int f(int n)if(n=0)return 1;else return n*f(n-1);8 1.递归的概念递归的概念2.递归过程递归过程3.递归程序设计递归程序

6、设计提纲提纲9 2.递归过程递归过程求求f（2）的）的 递归调用过程？递归调用过程？#include int f(int);main()int i=2;printf(“%d”,f(i);system(“pause”);int f(int n)/递归函数：求递归函数：求n!if(n=0)return 1;else return n*f(n-1);10 2.递归过程递归过程int f(int n)if(n=0)return 1;else return n*f(n-1);调用调用调用调用11返回返回211 2.递归过程递归过程请思考：请思考：发出发出f(2)调用时，将调用时，将2赋值给形参赋值给形参

7、n。然后发出。然后发出f(1)调用，将调用，将1赋值给形参赋值给形参n。接着发出。接着发出f(0)调用，将调用，将0赋值给形参赋值给形参n。后。后来赋给形参来赋给形参n的值会不会覆盖原来赋给的值会不会覆盖原来赋给n的值（如值的值（如值1覆盖覆盖原来的值原来的值2）？为什么？）？为什么？不会，每一次函数调用会在栈顶分配新的活动记录。不会，每一次函数调用会在栈顶分配新的活动记录。对递归函数的每一次调用结束返回时，为何能回到调用前对递归函数的每一次调用结束返回时，为何能回到调用前的程序运行状态？如的程序运行状态？如f(1)调用结束返回调用结束返回f(2)时，时，n的值为的值为2。函数访问的永远是栈顶

8、的活动记录。当函数访问的永远是栈顶的活动记录。当f(1)调用结束时，调用结束时，位于栈顶的位于栈顶的f(1)的活动记录将出栈，此时位于栈顶的将是的活动记录将出栈，此时位于栈顶的将是f(2)的函数活动记录。的函数活动记录。12 回顾函数调用过程函数调用过程2.递归过程递归过程 被调用函数中被调用函数中的数据的数据 现场信息，用现场信息，用于调用结束能于调用结束能正确返回并执正确返回并执行行13 f(0)返返回值回值1f(1)返返回值回值1f(2)返返回值回值2调用调用f(2)调用调用f(1)调用调用f(0)5.printf(“%d”,f(i);8.int f(int n)9.10.if(n=0)

9、11.return 1;12.else13.return n*f(n-1);14.1.int f(int);2.main()3.4.int i=2;5.printf(“%d”,f(i);6.system(“pause”);7.8.int f(int n)/递归函数：求递归函数：求n!9.10.if(n=0)11.return 1;12.else13.return n*f(n-1);14.14 求求f(6)的递归调用过程的递归调用过程递递推推阶阶段段回回归归阶阶段段返回返回15 2.递归过程递归过程可见，可见，递归算法的执行过程分递归算法的执行过程分递推递推和和回归回归两个阶两个阶段段。当递推时

10、，并没有求值的计算操作，实际的当递推时，并没有求值的计算操作，实际的计算操作是在回归过程实现的。计算操作是在回归过程实现的。递推阶段：递推阶段：递推递推阶段是个不断简化问题的阶段：把对较复阶段是个不断简化问题的阶段：把对较复杂问题（规模为杂问题（规模为n）的求解转化为比原问题）的求解转化为比原问题简单简单一些的问题（规模小于一些的问题（规模小于n）的求解）的求解。例如对。例如对f(6)的求解转化为的求解转化为f(5)的求解，的求解，对对f(5)的求解转化为的求解转化为f(4)的求解的求解直到转化为对直到转化为对f(0)的求解。的求解。当递推到当递推到最简单的不用再简化的问题时最简单的不用再简化

11、的问题时，递推，递推终止。如终止。如f函数中，函数中，n=0的情况。的情况。就象剥一颗圆白菜，从外向里，一层层剥下来，到就象剥一颗圆白菜，从外向里，一层层剥下来，到了菜心，就不再继续剥了。了菜心，就不再继续剥了。16 2.递归过程递归过程回归阶段：回归阶段：在在回归阶段回归阶段，当获得最简单情况的解后，逐，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解级返回，依次得到稍复杂问题的解。如在得。如在得到到f(1)的解后，又依次得到的解后，又依次得到f(2)、f(3)直到直到f(6)的值。的值。就像将剥下来的白菜叶又从里往外一叶一叶就像将剥下来的白菜叶又从里往外一叶一叶合起来，直到最外层菜

12、叶。合起来，直到最外层菜叶。17 2.递归过程递归过程思考：递归思考：递归与迭代的比较与迭代的比较(以求阶乘为例以求阶乘为例)。迭代迭代:从已知的初始条件出发，逐次去求所需从已知的初始条件出发，逐次去求所需要的阶乘值，这相当于从要的阶乘值，这相当于从菜心菜心“推到推到”（通（通过循环）最外层的过循环）最外层的菜叶菜叶。f(0)=1f(1)=1*f(0)=1f(2)=2*f(1)=2递归：先从最外层的递归：先从最外层的菜叶菜叶“递推递推”到到菜心菜心(递递归函数调用归函数调用)，再从，再从菜心菜心“回归回归”到最外面的到最外面的菜叶菜叶（递归函数返回）。（递归函数返回）。18 2.递归过程递归过

13、程递归递归算法的出发点不放在初始条件上，而放在求解的算法的出发点不放在初始条件上，而放在求解的目标上，是从所求的未知项出发逐次调用本身的求解目标上，是从所求的未知项出发逐次调用本身的求解过程，直到递归的边界（即初始条件）。过程，直到递归的边界（即初始条件）。就求阶乘而言，读者会认为递归算法可能是多余的，就求阶乘而言，读者会认为递归算法可能是多余的，费力而不讨好。费力而不讨好。但许多实际问题不可能或不容易找到但许多实际问题不可能或不容易找到显而易见的迭代关系，这时递归算法就表现出了明显显而易见的迭代关系，这时递归算法就表现出了明显的优越性。的优越性。下面我们将会看到，下面我们将会看到，递归算法比

14、较符合人的思维方式，递归算法比较符合人的思维方式，逻辑性强，可将问题描述得简单扼要，具有良好的可逻辑性强，可将问题描述得简单扼要，具有良好的可读性，易于理解，读性，易于理解，许多看来相当复杂，或难以下手的许多看来相当复杂，或难以下手的问题，如果能够使用递归算法就会使问题变得易于处问题，如果能够使用递归算法就会使问题变得易于处理。理。19 1.递归的概念递归的概念2.递归过程递归过程3.递归程序设计递归程序设计提纲提纲20 什么样的问题可以用递归解决？什么样的问题可以用递归解决？如果解决问题的方法是把该问题分解成小的子如果解决问题的方法是把该问题分解成小的子问题，并且这些小的子问题可以用同样的算

15、法问题，并且这些小的子问题可以用同样的算法解决，这样不断分解，直到子问题比较简单、解决，这样不断分解，直到子问题比较简单、可以直接解决时分解过程即终止，那么就可以可以直接解决时分解过程即终止，那么就可以用递归。用递归。递归的思想就是将一个问题先转化为与原问题递归的思想就是将一个问题先转化为与原问题性质相同、但规模小一级的子问题，然后再重性质相同、但规模小一级的子问题，然后再重复这样的转化，直到问题的规模减小到我们很复这样的转化，直到问题的规模减小到我们很容易解决为止。容易解决为止。3.递归程序设计递归程序设计21 u一般来说，递归需要有边界条件、递归前进段和递一般来说，递归需要有边界条件、递归

16、前进段和递归返回段。当边界条件不满足时，递归前进；当边界归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归逐级返回。条件满足时，递归逐级返回。u如何设计递归算法如何设计递归算法:1）对所求解的问题、要计算的函数书写递归）对所求解的问题、要计算的函数书写递归 定义；定义；注意一定要有终止条件和对应的操作。注意一定要有终止条件和对应的操作。2）正确地设计递归函数的参数。）正确地设计递归函数的参数。注意：递归算法最外层肯定采用的是选择结构！为注意：递归算法最外层肯定采用的是选择结构！为什么？什么？3.递归程序设计递归程序设计22 例例2.求浮点数求浮点数x的的n次幂次幂(n0)。函数。函

17、数 递归定义递归定义:1 当当n0 x*当当n0float power(float x，int n)if(n=0)return 1;else return x*power(x,n-1);递归程序设计举例递归程序设计举例23 递归程序设计举例递归程序设计举例例例3.设计递归函数求任意正整数的位数。设计递归函数求任意正整数的位数。num=1234int length(int num)if(num/10=0)return 1;else return length(num/10)+1;int length(int num)int len;len=0;if(num/10=0)len=1;else/从最低

18、位开始，依次从从最低位开始，依次从n中砍掉各位中砍掉各位while(num 0)num=num/10;/去掉最低位去掉最低位 len+;/*分解出一位数字，长度加分解出一位数字，长度加1*/return len;1 if num/10=length(num)=length(num/10)+1 if num/100024 递归程序设计举例递归程序设计举例调用调用调用调用返回值返回值325 递归程序设计举例递归程序设计举例例例4.求任意正整数的逆置数。求任意正整数的逆置数。num=1234递归思路递归思路1 1：将除最高位之外的数先逆置。：将除最高位之外的数先逆置。例如：例如：reverse(12

19、34)=1reverse(234）10思路思路1递归定义：递归定义：reverse(num)=num if num长度为长度为1 highBit+reverse(restNum)10 if num长度大于长度大于1其中：其中：highBit=num/power(10,len-1);restNum=num%power(10,len-1);len=num的长度；的长度；递归函数参数设计考虑：递归函数参数设计考虑：len作为递归函数的参数传入作为递归函数的参数传入26 递归设计思路递归设计思路1：num=1234 reverse(1234,4)1+reverse(234,3)*10 reverse(

20、234,3)=2+reverse(34,2)*10 reverse(34,2)=3+reverse(4,1)*10 reverse(4,1)=4返回返回4返回返回3+4*10=43返回返回2+43*10=432返回返回1+432*10=4321递归程序设计举例递归程序设计举例27 递归程序设计举例递归程序设计举例int reverse(int num,int len)int restNum,highBit;if(len=1)/如果如果num是个位数则递归结束是个位数则递归结束 return num;else highBit=num/power(10,len-1);/得到最高位得到最高位 res

21、tNum=num%power(10,len-1);/得到剩余位得到剩余位 /递归调用，并形成逆置数递归调用，并形成逆置数 return highBit+reverse(restNum,len-1)*10;num=1234自定义自定义power函数：函数：int power(int x,int y)28 递归程序设计举例递归程序设计举例例例4.求任意正整数的逆置数。求任意正整数的逆置数。num=1234递归思路递归思路2 2：将除最低位之外的数先逆置。：将除最低位之外的数先逆置。例如：例如：reverse(1234)=4*1000+reverse(123)递归定义递归定义1：reverse(nu

22、m)=num if num长度为长度为1 lowBit*power(10,len-1)+reverse(restNum)if num长度大于长度大于1其中：其中：lowBit=num%10;restNum=num/10;len=num的长度；的长度；29 递归程序设计举例递归程序设计举例递归设计思路递归设计思路2：num=1234 reverse(1234,4)4*1000+reverse(123,3)reverse(123,3)=3*100+reverse(12,2)reverse(12,2)=2*10+reverse(1,1)reverse(1)=1 返回返回1返回返回2*10+1=21返

23、回返回3*100+21=321返回返回4*1000+321=432130 递归程序设计举例递归程序设计举例int reverse(int num,int len)int restNum;int lowBit;if(len=1)/余数为余数为0，作为递归的结束条件，作为递归的结束条件 return num;else lowBit=num%10;/保留最低位保留最低位 restNum=num/10;/得到除去最低位后的余数得到除去最低位后的余数 /递归调用，并形成逆置数递归调用，并形成逆置数 return lowBit*power(10,len-1)+reverse(restNum,len-1);

24、num=123431 递归程序设计举例递归程序设计举例例例5.5.输入输入n n个整数，求最大数。个整数，求最大数。15 30 34 1015 30 34 10 89 89 设函数设函数findMax(nfindMax(n)为读取为读取n n个数，求最大值个数，求最大值 函数函数Maximum(x,yMaximum(x,y)为求两个数为求两个数x x和和y y的最大值的最大值则则findMax(nfindMax(n)递归定义递归定义1 1：findMax(1)=NfindMax(1)=N1 1 当当 n n值为值为1 1findMax(nfindMax(n)=Maximum(findMax(n

25、-1),N)=Maximum(findMax(n-1),Nn n)当当n1n1求前求前n(n1)个数的最大值，分解为个数的最大值，分解为3步：步：第第1步：读取前步：读取前n-1个数，求出最大值个数，求出最大值max；第第2步：读取第步：读取第n个数个数num；第第3步：返回步：返回num和和max之间的最大值之间的最大值32 递归程序设计举例递归程序设计举例/读取读取n n个数，求最大值个数，求最大值int findMax(int n)int max;/记录前记录前n-1个数中的最大值个数中的最大值 int num;/读取的第读取的第n个值个值 if(n=1)/求前求前1个数中的最大值个数中

26、的最大值 scanf(%d,&num);return num;else max=findMax(n-1);/第第1步：步：读取前读取前n-1个数，求出最大值个数，求出最大值max；scanf(%d,&num);/第第2步：读取第步：读取第n个数个数num；return nummax?num:max;/*第第3步：步：计算计算并返回并返回num和和 max之间的最大值之间的最大值*/15 30 34 10 89 33 findMax(4)findMax(3)，findMax(3)findMax(2)，findMax(2)findMax(1)findMax(1)读取第读取第1个数个数1515 30

27、 34 10返回返回15返回返回30返回返回34返回返回34mainint findMax(int n)int max,num;if(n=1)/求前求前1个数中的最大值个数中的最大值 scanf(%d,&num);return num;else max=findMax(n-1);scanf(%d,&num);return nummax?num:max;读取第读取第2个数个数30读取第读取第3个数个数34读取第读取第4个数个数1034 调用调用调用调用35 例例5 5.输入输入n n个整数，求最大数。个整数，求最大数。递归设计思路递归设计思路2：15 30 34 10 89 设函数设函数find

28、Max(nfindMax(n)为读取为读取n n个数，求最大值个数，求最大值 函数函数Maximum(x,yMaximum(x,y)为求两个数为求两个数x x和和y y的最大值的最大值则则findMax(nfindMax(n)递归定义递归定义1 1：findMax(1)=NfindMax(1)=N1 1 当当 n n值为值为1 1findMax(nfindMax(n)=Maximum(N)=Maximum(N1 1,findMax(n-1),findMax(n-1)当当n1n1求前求前n(n1)个数的最大值，分解为个数的最大值，分解为3步：步：第第1步：读入第步：读入第1个数个数num 第第2

29、步：调用递归函数，读取后续步：调用递归函数，读取后续n-1个数，求最大数个数，求最大数max 第第3步：返回步：返回num和和max中的最大值中的最大值36 int findMax(int n)/求求n个数的最大值个数的最大值 int num,max;if(n=1)scanf(%d,&num);/*第第1步：读入第一个数步：读入第一个数num*/return num;/*若是最后一个数，则将其本身作为最大值并返回若是最后一个数，则将其本身作为最大值并返回*/else scanf(%d,&num);/*第第1步：读入第一个数步：读入第一个数num*/max=findMax(n-1);/*第第2步

30、：调用递归函数读取并求出后续步：调用递归函数读取并求出后续n-1个个 数的最大值数的最大值max*/return nummax?num:max;/*第第3步：返回步：返回num和和max中的最大值中的最大值*/15 30 34 10 89 37 findMax(4)读读15，调用调用findMax(3)findMax(3)读读30，调用，调用findMax(2)findMax(2)读读34，调用，调用findMax(1)findMax(1)读读1015 30 34 10main返回返回10返回返回34返回返回34返回返回34int findMax(int n)int num,max;if(n=

31、1)scanf(%d,&num);return num;else scanf(%d,&num);max=findMax(n-1);return nummax?num:max;38 例例6：用函数：用函数fib求斐波那契数列的第求斐波那契数列的第n项。斐波那契数项。斐波那契数列为：列为：0、1、1、2、3、。函数。函数fib定义如下：定义如下：0 当当n1 fib(n)1 当当n2 fib(n-2)+fib(n-1)当当n=3long fib(long n)if(n=1|n=2)return n-1;else return fib(n-2)+fib(n-1);请分析该问题是否可以用递归算法解决？

32、请分析该问题是否可以用递归算法解决？若可以，请写出该递归算法。若可以，请写出该递归算法。请画出求请画出求fib(4)的递归调用过程图示的递归调用过程图示39 1.#include2.main()3.4.printf(“%ld”,f(3);5.system(“pause”);6.return 0;7.8.long fib(long n)9.10.if(n=1|n=2)11.return n-1;12.else13.return fib(n-2)+fib(n-1);14.40 3.递归程序设计递归程序设计每求一项数，需要递归调用每求一项数，需要递归调用2次该函数；计算次该函数；计算斐波那契数列第斐

33、波那契数列第30项的递归调用次数是项的递归调用次数是2的的30次方（大约次方（大约10亿次！）亿次！）可见递归的思想特别符合人们的思维习惯，便可见递归的思想特别符合人们的思维习惯，便于问题解决和编程实现。但递归的程序设计方于问题解决和编程实现。但递归的程序设计方法比较占用系统资源，效率也较低。法比较占用系统资源，效率也较低。课下请改写课下请改写fib函数，使用迭代算法实现函数，使用迭代算法实现long fib(long n),计算斐波那契数列第计算斐波那契数列第n项。项。41 三、递归问题举例例例7、汉诺塔问题、汉诺塔问题 传说印度布拉马圣殿（传说印度布拉马圣殿（Temple of Brahm

34、a）的教的教士们有一黄铜烧铸的平台，上立三根金刚石柱士们有一黄铜烧铸的平台，上立三根金刚石柱子。子。A柱上堆放了柱上堆放了64个金盘子，每个盘子都比个金盘子，每个盘子都比其下面的盘子略小一些。当教士们将盘子全部其下面的盘子略小一些。当教士们将盘子全部从从A柱移到柱移到C柱以后，世界就到了末日。当然，柱以后，世界就到了末日。当然，这个问题还有一些特定的条件，那就是在柱子这个问题还有一些特定的条件，那就是在柱子之间之间只能移动一个盘子只能移动一个盘子并且并且任何时候大盘子都任何时候大盘子都不能放到小盘子上不能放到小盘子上。教士们当然还在忙碌着，。教士们当然还在忙碌着，因为这需要因为这需要264-1

35、次移动。如果一次移动需要一次移动。如果一次移动需要一秒钟，那么全部操作需要秒钟，那么全部操作需要5000亿年以上时间。亿年以上时间。42 怎样编写这种程序？从思路上还是先从最简单的情况分怎样编写这种程序？从思路上还是先从最简单的情况分析起，搬一搬看，慢慢理出思路。析起，搬一搬看，慢慢理出思路。1 1、在、在A A柱上只有一只盘子，假定盘号为柱上只有一只盘子，假定盘号为1 1，这时只需将该盘，这时只需将该盘从从A A搬至搬至C C，一次完成，记为，一次完成，记为 move 1 from A to Cmove 1 from A to C43 2 2、在、在A A柱上有二只盘子，柱上有二只盘子，1

36、1为小盘，为小盘，2 2为大盘。为大盘。第（第（1 1）步将）步将1 1号盘从号盘从A A移至移至B B，这是为了让，这是为了让2 2号盘能移动；号盘能移动；第（第（2 2）步将）步将2 2号盘从号盘从A A移至移至C C；第（第（3 3）步再将）步再将1 1号盘从号盘从B B移至移至C C；这三步记为：这三步记为：move 1 from A to B;move 1 from A to B;move 2 from A to C;move 2 from A to C;move 1 from B to C;move 1 from B to C;A B C 1 3 2 可见，移动可见，移动2个盘个盘

37、子从子从A柱到柱到C柱需柱需要借助于要借助于B柱。因柱。因此，在构思搬移此，在构思搬移过程的参数时，过程的参数时，要把要把3个柱子都用个柱子都用上。上。44 3、在、在A柱上有柱上有3只盘子，从小到大分别为只盘子，从小到大分别为1号，号，2号，号，3号号第第(1)步将步将1号盘和号盘和2号盘视为一个整体；先将二者作为整号盘视为一个整体；先将二者作为整体从体从A移至移至B，给，给3号盘创造能够一次移至号盘创造能够一次移至C的机会。这的机会。这一步记为一步记为move(2,A,C,B)意思是将上面的意思是将上面的2只盘子作为整体从只盘子作为整体从A借助借助C移至移至B。第第(2)步将步将3号盘从号

38、盘从A移至移至C，一次到位。记为，一次到位。记为 move 3 from A to C第第(3)步处于步处于B上的作为一个整体的上的作为一个整体的2只盘子，再移至只盘子，再移至C。这一步记为这一步记为 move(2,B,A,C)意思是将意思是将2只盘子作为整体从只盘子作为整体从B借助借助A移至移至C。45 ABC1234、从题目的约束条件看，大盘上可以随便摞小盘，相反、从题目的约束条件看，大盘上可以随便摞小盘，相反则不允许。在将则不允许。在将1号和号和2号盘当整体从号盘当整体从A移至移至B的过程中的过程中move(2,A,C,B)实际上是分解为以下三步实际上是分解为以下三步第第1步：步：mov

39、e 1 from A to C;第第2步：步：move 2 from A to B;第第3步：步：move 1 from C to B;经过以上步骤，将经过以上步骤，将1号和号和2号盘作为整体从号盘作为整体从A移至移至B，为，为3号号盘从盘从A移至移至C创造了条件。同样，创造了条件。同样，3号盘一旦到了号盘一旦到了C，就，就要考虑如何实现将要考虑如何实现将1号和号和2号盘当整体从号盘当整体从B移至移至C的过程的过程了。实际上了。实际上move(2,B,A,C)也要分解为三步：也要分解为三步：第第1步：步：move 1 from B to A;第第2步：步：move 2 from B to C;

40、第第3步：步：move 1 from A to C;ABC12346 同同理理，将将n n个个圆圆盘盘从从A A柱柱移移到到C C柱柱move(n,A,B,C)可分解为可分解为3步步：第第1 1步步.将将A A柱柱上上面面的的从从上上往往下下数数的的（n n1 1）个个圆圆盘盘移移到到B B柱柱上上，中中间间通通过过C C柱柱为为辅辅助助。这这是是一一个个（n n1 1）个圆盘的问题：个圆盘的问题：move(n-1,A,C,B)move(n-1,A,C,B)；第第2 2步步.将将A A柱上的最后一个圆盘，直接移到柱上的最后一个圆盘，直接移到C C柱上；柱上；第第3 3步步.再再将将B B柱柱上

41、上的的（n n1 1）个个圆圆盘盘移移到到C C柱柱上上，中中间间以以A A柱柱为为辅辅助助。这这又又是是一一个个（n n1 1）个个圆圆盘的问题盘的问题:move(n-1,B,A,C)move(n-1,B,A,C)；ABCABC47 这里显然是一种递归定义，将问题分解成若干同这里显然是一种递归定义，将问题分解成若干同样类型的小问题。当解样类型的小问题。当解move(n-1,A,C,B)时又时又可想到，将其分解为可想到，将其分解为3步：步：第第1步：将上面的步：将上面的n-2只盘子作为一个整体从只盘子作为一个整体从A经经B到到C，move(n-2,A,B,C)；第第2步：第步：第n-1号盘子从

42、号盘子从A直接移至直接移至B，即，即n-1:A to B；第第3步：再将上面的步：再将上面的n-2只盘子作为一个整体从只盘子作为一个整体从C经经A移至移至B，move(n-2,C,A,B)；48 这这这这样样样样移移移移动动动动n n n n个个个个盘盘盘盘子子子子的的的的问问问问题题题题被被被被简简简简化化化化成成成成了了了了移移移移动动动动n n n n1 1 1 1个个个个盘盘盘盘子子子子的的的的问问问问题题题题，移移移移动动动动n-1n-1n-1n-1个个个个盘盘盘盘子子子子的的的的问问问问题题题题又又又又被被被被简简简简化化化化成成成成移移移移动动动动n-2n-2n-2n-2个个个个

43、盘盘盘盘子子子子 这这这这一一一一过过过过程程程程反反反反复复复复进进进进行行行行下下下下去去去去直直直直到到到到只只只只剩剩剩剩下下下下1 1 1 1个个个个盘盘盘盘子子子子时时时时将将将将其其其其移移移移动动动动。移移移移动动动动1 1 1 1个个个个盘子的简单操作就是终止条件。盘子的简单操作就是终止条件。盘子的简单操作就是终止条件。盘子的简单操作就是终止条件。49 将将n个盘子从个盘子从from柱移动到柱移动到to柱，借助于柱，借助于med柱。柱。1.将（将（n1）个盘子从柱个盘子从柱from移到柱移到柱med，借助于柱，借助于柱to；2.将柱将柱from上的最后一个盘子直接移动到柱上的

44、最后一个盘子直接移动到柱to；3.将（将（n1）个盘子从柱个盘子从柱med，移到柱移到柱to，借助于柱，借助于柱from；函数接口设计函数接口设计：void move(int n,int from,int med,int to)功能功能：将：将n个盘子从个盘子从from柱移动到柱移动到to柱，中间借助于柱，中间借助于 med柱。柱。参数参数：n：要移动的盘子数；要移动的盘子数；from：源柱，：源柱，med：辅助的柱辅助的柱子，子，to：目标柱目标柱frommedtofrommedto50 void move(int n,int from,int med,int to)if(n=1)print

45、f(“%d-%d n,from,to);else move(n-1,from,to,med);printf(“%d-%d n,from,to);move(n-1,med,from,to);将将n个盘子从个盘子从from柱移动到柱移动到to柱，借助于柱，借助于med柱。柱。1.将（将（n1）个盘子从柱个盘子从柱from移到柱移到柱med，借助于柱，借助于柱to；2.将柱将柱from上的最后一个盘子直接移动到柱上的最后一个盘子直接移动到柱to；3.将（将（n1）个盘子从柱个盘子从柱med，移到柱移到柱to，借助于柱，借助于柱from；51 主函数部分：主函数部分：#includevoid move

46、(int n,int a,int b,int c);main()int num；printf(the number of plate is:);scanf(%d,&num);move(num,1,2,3);system(“pause”);return 0;【程序运行演示】52 移动移动3个盘子的递归调用过程见个盘子的递归调用过程见计算机导论计算机导论与程序设计基础与程序设计基础261页页注意分析注意分析为何调用能正确返回为何调用能正确返回为何每次调用访问的是正确的函数运行空间为何每次调用访问的是正确的函数运行空间53 移动三个盘子的运行结果移动三个盘子的运行结果the number of pl

47、ate is:31-31-23-21-32-12-31-332132132132132132132132154 递归小结递归小结递归程序好看、好读，风格优美，但执行效率递归程序好看、好读，风格优美，但执行效率低；低；任何能用递归解决的问题都能用迭代（循环）任何能用递归解决的问题都能用迭代（循环）的方法去解决（不过有些问题可能很难写）。的方法去解决（不过有些问题可能很难写）。终结条件。程序必须要有终结条件，不可能无终结条件。程序必须要有终结条件，不可能无限递归下去。限递归下去。55 例例8 8.输入任意个整数，以输入任意个整数，以-1结束，求最大数结束，求最大数。例例8 8.输入任意个整数，以输

48、入任意个整数，以-1结束，求最大数结束，求最大数。递归定义怎么写？递归定义怎么写？问题问题findMax10,20,-15,-1可简化成：可简化成：Maximum(10,findMax20,-15,-1)56 例例8 8.输入任意个整数，以输入任意个整数，以-1结束，求最大数结束，求最大数递归设计思路：递归设计思路：第一步：读入一个数第一步：读入一个数num;第二步：读入后续以第二步：读入后续以-1结束的数，求出最大值结束的数，求出最大值 max（递归调用）（递归调用）;第三步：求出第三步：求出num和和max中的最大值并返回中的最大值并返回;57 例例8 8.输入任意个整数，以输入任意个整数

49、，以-1结束，求最大数结束，求最大数/findMax：求本次读入数据以及后续读入数据的最大值：求本次读入数据以及后续读入数据的最大值int findMax()int num,max;scanf(%d,&num);/读入一个数读入一个数num if(num=-1)return?;/此处怎么写？此处怎么写？else max=findMax();/求出剩下要读入的数的最大值求出剩下要读入的数的最大值max return nummax?num:max;/返回返回num和和max中的最大值中的最大值 58 findMax()20,-15,-1调用调用调用调用59 例例8 8.输入任意个整数，以输入任意个

50、整数，以-1结束，求最大数结束，求最大数问题问题1：当本次递归调用读入的数据是：当本次递归调用读入的数据是-1时，应返回什么时，应返回什么值？值？分析：分析：求求findMax10,20,-15,-1，该问题可以简化为求，该问题可以简化为求findMax20,-15,-1，而，而findMax20,-15,-1可以简化为可以简化为求求findMax-15,-1。此时已经能得到答案。此时已经能得到答案-15，因此递，因此递归调用此时应该结束。因此当递归调用读入的是归调用此时应该结束。因此当递归调用读入的是-1时，时，应该返回应该返回-15。问题问题2：当递归调用读入的是：当递归调用读入的是-1时