C语言递归课件

7.6函数的递归调用在调用一个函数的过程中又出现直接或间接地调用该函数本身，称为函数的递归调用。Ｃ语言的特点之一就在于允许函数的递归调用。例如：intf（intx）｛inty，ｚ；ｚ＝f（y）；return（2*ｚ）；｝在调用函数f的过程中，又要调用f函数，这是直接调用本函数，见图7.9。下面是间接调用本函数。在调用f1函数过程中要调用f2函数，而在调用f2函数过程中又要调用f1函数，这两种递归调用都是无终止的自身调用。显然，程序中不应出现这种无终止的递归调用，而只应出现有限次数的、有终止的递归调用，这可以用if语句来控制，只有在某一条件成立时才继续执行递归调用，否则就不再继续。例7.7有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可以用式子表述如下：age（n）＝10（n＝1）age（n－1）＋2（n＞1）可以看到，当n＞1时，求第n个人的年龄的公式是相同的。因此可以用一个函数表示上述关系。图7.11表示求第5个人年龄的过程。图7.11从图可知，求解可分成两个阶段：第一阶段是“回推”，即将第n个人的年龄表示为第（n－1）个人年龄的函数，而第（n－1）个人的年龄仍然不知道，还要“回推”到第（n－2）个人的年龄……直到第1个人年龄。此时age（1）已知，不必再向前推了。然后开始第二阶段，采用递推方法，从第1个人的已知年龄推算出第2个人的年龄（12岁），从第2个人的年龄推算出第3个人的年龄（14岁）……一直推算出第5个人的年龄（18岁）为止。也就是说，一个递归的问题可以分为“回推”和“递推”两个阶段。要经历许多步才能求出最后的值。显而易见，如果要求递归过程不是无限制进行下去，必须具有一个结束递归过程的条件。例如，age（1）＝10，就是使递归结束的条件。#includestdio.hintage(intn){intc;if(n==1)c=10;elsec=age(n-1)+2;return(c);}voidmain(){printf(%d\n,age(5));}main函数中只有一个语句。图7.12从图7.12可以看到：age函数共被调用5次，即age（5）、age（4）、age（3）、age（2）、age（1）。其中age（5）是main函数调用的，其余4次是在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！×4…1！＝1。可用下面的递归公式表示：n！＝1（n＝0，1）n·（n－1）！（n＞1）#includestdio.hfloatfac(intn){floatf;if(n0){printf(n＜0，dataerror！);f=-1;}elseif(n==0||n==1)f=1;elsef=fac(n-1)*n;return(f);}voidmain(){intn;floaty;printf(inputainteger);scanf(%d,&n);y=fac(n);printf(%d!=%15.0f\n,n,y);}例7.9hanoi（汉诺）塔问题。这是一个古典的数学问题，是一个只有用递归方法（而不可能用其他方法）解决的问题。问题是这样的：古代有一个梵塔，塔内有3个座A、B、C，开始时Ａ座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把这64个盘子从Ａ座移到Ｃ座，但每次只允许移动一个盘，且在移动过程中每3个座上都始终保持大盘在下，小盘在上。在移动过程中可以利用Ｂ座，要求编程序打印出移动的步骤。(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个和尚将62个盘子从C座移到B座。再进行一次递归。如此“层层下放”，直到后来找到第63个和尚，让他完成将2个盘子从一个座移到另一座，进行到此，问题就接近解决了。最后找到第64个和尚，让他完成将1个盘子从一个座移到另一座，至此，全部工作都已落实，都是可以执行的。可以看出，递归的结束条件是最后一个和尚只需移一个盘子。否则递归还要继续进行下去。应当说明，只有第64个和尚的任务完成后，第63个和尚的任务才能完成。只有第2到第64个和尚任务完成后，第1个和尚的任务才能完成。我们先分析将Ａ座上3个盘子移到Ｃ座上的过程：(1)将Ａ座上2个盘子移到Ｂ座上（借助Ｃ）；(2)将Ａ座上1个盘子移到Ｃ座上；(3)将Ｂ座上2个盘子移到Ｃ座上（借助Ａ）。其中第2步可以直接实现。第1步又可用递归方法分解为：1．1将Ａ上1个盘子从Ａ移到Ｃ；1．2将Ａ上1个盘子从Ａ移到Ｂ；1．3将Ｃ上1个盘子从Ｃ移到Ｂ。第3步可以分解为：3．1将Ｂ上1个盘子从Ｂ移到Ａ上；3．2将Ｂ上1个盘子从Ｂ移到Ｃ上；3．3将Ａ上1个盘子从Ａ移到Ｃ上。将以上综合起来，可得到移动3个盘子的步骤为Ａ→Ｃ，Ａ→Ｂ，Ｃ→Ｂ，Ａ→Ｃ，Ｂ→Ａ，Ｂ→Ｃ，Ａ→Ｃ。共经历7步。由此可推出：移动n个盘子要经历2n-1步。如移4个盘子经历15步，移5个盘子经历31步，移64个盘子经历264-1步。由上面的分析可知：将n个盘子从Ａ座移到Ｃ座可以分解为以下3个步骤：(1)将Ａ上n－1个盘借助Ｃ座先移到Ｂ座上。(2)把Ａ座上剩下的一个盘移到Ｃ座上。(3)将n－1个盘从Ｂ座借助于Ａ座移到Ｃ座上。上面第1步和第3步，都是把n－1个盘从一个座移到另一个座上，采取的办法是一样的，只是座的名字不同而已。为使之一般化，可以将第1步和第3步表示为：#includestdio.h/*将n个盘从one座借助two座，移到three座*/voidhanoi(intn,charone,chartwo,charthree){if(n==1)printf(%c----＞%c\n,one,three);else{hanoi(n-1,one,three,two);printf(%c----＞%c\n,one,three);hanoi(n-1,two,one,three);}}voidmain(){intm;printf(inputthenumberofdiskes：);scanf(%d,&m);printf(Thesteptomoving%3ddiskes：\n,m);hanoi(m,'a','b','c');}#includestdio.h//方法2voidmove(charx,chary){printf(%c－－＞%c\n,x,y);}voidhanoi(intn,charone,chartwo,charthree)/*将n个盘从one座借助two座，移到three座*/{if(n==1)move(one,three);else{hanoi(n-1,one,three,two);move(one,three);hanoi(n-1,two,one,three);}}voidmain(){intm;printf(inputthenumberofdiskes：);scanf(%d,&m);printf(Thesteptomoving%3ddiskes：\n,m);hanoi(m,'a','b','c');}方法2结果为：inputthenumberofdiskes：3Thesteptomoving3diskesa－－＞ca－－＞bc－－＞ba－－＞cb－－＞ab－－＞ca－－＞c方法1结果为：inputthenumberofdiskes：3Thesteptomoving3diskes：a----＞ca----＞bc----＞ba----＞cb----＞ab----＞ca----＞c#includestdio.h//利用递归完成求n的m次方floatf(intn,intm){floaty;if(m==0)y=1;elseif(m0)y=f(n,m-1)*n;elsey=f(n,m+1)/n;returny;}voidmain(){intn=2;intm=-3;printf(请输入n和m的值：);scanf(%d%d,&n,&m);printf(n的m次方为:%f,f(n,m));}