C语言递归课件(精品).ppt

《C语言递归课件(精品).ppt》由会员分享，可在线阅读，更多相关《C语言递归课件(精品).ppt（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、7.6 函数的递归调用在调用一个函数的过程中又出现直接或间接直接或间接地调用该函数本身，称为函数的递归调用。语言的特点之一就在于允许函数的递归调用。例如：int f（int x）int y，；f（y）；return（2*）；在调用函数f的过程中，又要调用f函数，这是直接调用本函数，见图7.9。下面是间接调用本函数。在调用f1函数过程中要调用f2函数，而在调用f2函数过程中又要调用f1函数，这两种递归调用都是无终止的自身调用。显然，程序中不应出现这种无终止的递归调用，而只应出现有限次数的、有终止的递归调用，这可以用if语句来控制，只有在某一条件成立时才继续执行递归调用，否则就不再继续。例7.7

2、有5个人坐在一起，问第5个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第3个人，又说比第2个人大2岁。问第2个人，说比第1个人大2岁。最后问第1个人，他说是10岁。请问第5个人多大。显然，这是一个递归问题。要求第5个人的年龄，就必须先知道第4个人的年龄，而第4个人的年龄也不知道，要求第4个人的年龄必须先知道第3个人的年龄，而第3个人的年龄又取决于第2个人的年龄，第2个人的年龄取决于第1个人的年龄。而且每一个人的年龄都比其前1个人的年龄大2。即 age（5）age（4）2age（4）age（3）2age（3）age（2）2age（2）age（1）2age（1）10可以

3、用式子表述如下：age（n）10（n1）age（n1）2 （n1）可以看到，当n1时，求第n个人的年龄的公式是相同的。因此可以用一个函数表示上述关系。图7.11表示求第5个人年龄的过程。图7.11从图可知，求解可分成两个阶段：第一阶段是“回推”，即将第n个人的年龄表示为第（n1）个人年龄的函数，而第（n1）个人的年龄仍然不知道，还要“回推”到第（n2）个人的年龄直到第1个人年龄。此时age（1）已知，不必再向前推了。然后开始第二阶段，采用递推方法，从第1个人的已知年龄推算出第2个人的年龄（12岁），从第2个人的年龄推算出第3个人的年龄（14岁）一直推算出第5个人的年龄（18岁）为止。也就是说，

4、一个递归的问题可以分为“回推”和“递推”两个阶段。要经历许多步才能求出最后的值。显而易见，如果要求递归过程不是无限制进行下去，必须具有一个结束递归过程的条件。例如，age（1）10，就是使递归结束的条件。#include int age(int n)int c;if(n=1)c=10;elsec=age(n-1)+2;return(c);void main()printf(%dn,age(5);main函数中只有一个语句。图图7.12从图7.12可以看到：age函数共被调用5次，即age（5）、age（4）、age（3）、age（2）、age（1）。其中age（5）是main函数调用的，其余4

5、次是在age函数中调用的，即递归调用4次。请读者仔细分析调用的过程。应当强调说明的是在某一次调用age函数时并不是立即得到age（n）的值，而是一次又一次地进行递归调用，到age（1）时才有确定的值，然后再递推出age（2）、age（3）、age（4）、age（5）。请读者将程序和图7.11、图7.12结合起来认真分析。例7.8用递归方法求n！。求n！也可以用递归方法，即5！等于4！5，而4！3！41！1。可用下面的递归公式表示：n！1（n0，1）n（n1）！（n1）#include float fac(int n)float f;if(n0)printf(n0，data error！);f=

6、-1;elseif(n=0|n=1)f=1;else f=fac(n-1)*n;return(f);void main()int n;float y;printf(input a integer);scanf(%d,&n);y=fac(n);printf(%d!=%15.0fn,n,y);例7.9hanoi（汉诺）塔问题。这是一个古典的数学问题，是一个只有用递归方法（而不可能用其他方法）解决的问题。问题是这样的：古代有一个梵塔，塔内有3个座A、B、C，开始时座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把这64个盘子从座移到座，但每次只允许移动一个盘，且在移动过程中每3个座

7、上都始终保持大盘在下，小盘在上。在移动过程中可以利用座，要求编程序打印出移动的步骤。(1)命令第2个和尚将63个盘子从A座移到B座；(2)自己将1个盘子（最底下的、最大的盘子）从A座移到C座；(3)命令第2个和尚将63个盘子从B座移到C座。至此，全部任务完成了。这就是递归方法。但是，有一个问题实际上未解决：第2个和尚怎样才能将63个盘子从A座移到B座？为了解决将63个盘子从A座移到B座，第2个和尚又想：如果有人能将62个盘子从一个座移到另一座，我就能将63个盘子从A座移到B座，他是这样做的：(1)命令第3个和尚将62个盘子从A座移到C座；(2)自己将1个盘子从A座移到B座；(3)命令第3个和尚

8、将62个盘子从C座移到B座。再进行一次递归。如此“层层下放”，直到后来找到第63个和尚，让他完成将2个盘子从一个座移到另一座，进行到此，问题就接近解决了。最后找到第64个和尚，让他完成将1个盘子从一个座移到另一座，至此，全部工作都已落实，都是可以执行的。可以看出，递归的结束条件是最后一个和尚只需移一个盘子。否则递归还要继续进行下去。应当说明，只有第应当说明，只有第64个和尚的任务完成后，个和尚的任务完成后，第第63个和尚的任务才能完成。只有第个和尚的任务才能完成。只有第2到第到第64个和尚任务完成后，第个和尚任务完成后，第1个和尚的任务才能完个和尚的任务才能完成。成。我们先分析将座上我们先分析

9、将座上3个盘子移到座上的过个盘子移到座上的过程：程：(1)将座上将座上2个盘子移到座上（借助）；个盘子移到座上（借助）；(2)将座上将座上1个盘子移到座上；个盘子移到座上；(3)将座上将座上2个盘子移到座上（借助）。个盘子移到座上（借助）。其中第其中第2步可以直接实现。第步可以直接实现。第1步又可用递归步又可用递归方法分解为：方法分解为：11将上将上1个盘子从移到；个盘子从移到；12将上将上1个盘子从移到；个盘子从移到；13将上将上1个盘子从移到。个盘子从移到。第第3步可以分解为：步可以分解为：31将上将上1个盘子从移到上；个盘子从移到上；32将上将上1个盘子从移到上；个盘子从移到上；33将上

10、将上1个盘子从移到上。个盘子从移到上。将以上综合起来，可得到移动将以上综合起来，可得到移动3个盘子的步骤为个盘子的步骤为，。共经历7步。由此可推出：移动n个盘子要经历2n-1步。如移4个盘子经历15步，移5个盘子经历31步，移64个盘子经历264-1步。由上面的分析可知：将n个盘子从座移到座可以分解为以下3个步骤：(1)将上n1个盘借助座先移到座上。(2)把座上剩下的一个盘移到座上。(3)将n1个盘从座借助于座移到座上。上面第1步和第3步，都是把n1个盘从一个座移到另一个座上，采取的办法是一样的，只是座的名字不同而已。为使之一般化，可以将第1步和第3步表示为：#include/*将将n个盘从个

11、盘从one座借助座借助two座，移到座，移到three座座*/void hanoi(int n,char one,char two,char three)if(n=1)printf(%c-%cn,one,three);elsehanoi(n-1,one,three,two);printf(%c-%cn,one,three);hanoi(n-1,two,one,three);void main()int m;printf(input the number of diskes：);scanf(%d,&m);printf(The step to moving%3d diskes：n,m);hanoi

12、(m,a,b,c);#include/方法2void move(char x,char y)printf(%c%cn,x,y);void hanoi(int n,char one,char two,char three)/*将将n个盘从个盘从one座借助座借助two座，移到座，移到three座座*/if(n=1)move(one,three);elsehanoi(n-1,one,three,two);move(one,three);hanoi(n-1,two,one,three);void main()int m;printf(input the number of diskes：);scan

13、f(%d,&m);printf(The step to moving%3d diskes：n,m);hanoi(m,a,b,c);方法2结果为：input the number of diskes：3The step to moving 3 diskesacabcbacbabcac方法1结果为：input the number of diskes：3The step to moving 3 diskes：a-ca-bc-ba-cb-ab-ca-c#include/利用递归完成求利用递归完成求n的的m次方次方float f(int n,int m)float y;if(m=0)y=1;elseif(m0)y=f(n,m-1)*n;elsey=f(n,m+1)/n;return y;void main()int n=2;int m=-3;printf(请输入请输入n和和m的值：的值：);scanf(%d%d,&n,&m);printf(n的的m次方为次方为:%f,f(n,m);