|
7.1 从讲故事开始--函数概述 先讲一个故事，星期天小息一下，去公园转一转。 首先准备东西，然后打辆出租车出发。出租车司机问我们去哪？我们告诉他去公园。之后"开车"的任务就由司机代劳，不需我们亲自动手了，我们只要坐在车里等待。待到公园后，我们的等待过程结束，开始"游览公园"。再后来肚子饿了，找一家餐厅点菜。服务员问吃什么，我们告诉她吃"鱼香鸡丝"。之后"做菜"的任务就由餐厅后厨代劳，也不需我们亲自动手了，我们仍是等待。不巧的是，后厨发现没有葱了，必须先去买葱，则做菜的过程暂停，厨师等待。如何去买葱呢？后厨也打辆出租车并告诉司机"去农贸市场"。待葱买回后厨师的等待结束，做菜继续。而这段时间的我们还是一直在等待。待菜做好后，服务员将做好的菜端给我们，我们的等待过程结束，可以"开吃了"。最后，打车回家，并告诉司机家的地址；然后我们又坐在车里等待，直至到家。 在这个故事中，"我们"是主体，某些事情由我们亲自来做（如"游览"、"吃饭"），但另外的一些事情则可以分别请别人代劳（如"开车"、"做菜"），后者在程序中称为调用，调用类似"派遣"、"指挥"。当我们"调用"别人做一些事的时候，我们自己的状态是"等待"；我们必须等到别人将事情做完之后，自己才能进行下一步的动作。 在C语言中"我们"就是main函数；能够供我们派遣或调用的其他人，就是main外的其他函数。整个程序就是由多个函数组成的程序，如同包含多个自然段的一篇文章： 7.4 函数的嵌套调用和递归调用 7.4.1 函数里的函数--函数的嵌套调用 定义函数不允许嵌套，但调用函数可以嵌套，即在被调函数中又调用其它函数。本章开始"游览公园"的例子中就有函数的嵌套调用：我们调用点菜函数，点菜又调用打车函数。 【程序例7.6】函数的嵌套调用。 #include <stdio.h> void fun1(); void fun2(); main() { fun2(); printf("main\n"); } void fun1() { printf("fun1\n"); } void fun2() { fun1(); printf("fun2\n"); } fun1 fun2 main 该程序执行过程如图7.11。main函数调用fun2，在被调函数fun2中又调用函数fun1，形成函数的嵌套调用。无论在哪个函数中，只要调用其他函数，则这个函数就会暂停，程序转去执行被调函数；待被调函数结束后再回到调用它的上一级函数的断点处继续。需要注意的是，被调函数结束后，只能返回调用它的上一级函数，不能越级返回；例如fun1结束后只能返回到调用它的fun2，不能直接返回到main。 7.4.2 克隆函数--函数的递归调用 我们知道，在一个函数中可以调用其他函数；那么如果在一个函数中调用自己这个函数本身，又会如何呢？在程序设计中，函数自己调用自己不仅是合法的，而且是一个非常重要的程序设计技巧，称为递归。例如： int fun(int x) { …… fun(y); …… } 在函数fun的内部又调用了函数fun，而所调用的函数fun正是它本身，这就是递归。 我们通过一个例子来理解递归。 【程序例7.7】用递归法计算n的阶乘：n! = n * (n-1) * (n-2) * … * 3 * 2 * 1。 由于(n-1)! = (n-1) * (n-2) * … * 3 * 2 * 1，因此n!可用下述公式表示： 图7.12所示的方式是一种"懒人算阶乘"的方式：main要计算4!，向"赵"发出命令。"赵"是懒人，不愿做连乘，他将4!的计算任务转化为4*3!。但3!仍要连乘，如何求得呢？"赵"再找一个人"钱"，让"钱"去做3!。"赵"只等"钱"把3!求出后，再将结果乘4就可以完成任务了。这样连乘的麻烦归到了"钱"的头上，他怎么办呢？"钱"也是懒人，不愿做连乘，他将3!的计算任务转化为3*2!，并再找一个人"孙"去算2!。"孙"也是懒人，再找一个人"李"去算1!……这样一路找下去，并都在等待下一个人的计算结果来完成自己的任务，直到"李"计算1!可直接得出答案1，再将答案按原路一个一个返回去： ◆ "李"立即算出1!的结果为1，并将此结果给"孙"； ◆"孙"直接用"李"的计算结果1去乘2，完成了2!的计算任务，将结果2给"钱"； ◆"钱"直接用"孙"的计算结果2去乘3，完成了3!的计算任务，将结果6给"赵"； ◆"赵"直接用"钱"的计算结果6去乘4，完成了4!的计算任务，将结果24给main。 实际上，"赵"、"钱"、"孙"、"李"尽管是4个人，但他们的想法都是相同的，均是： "我不做连乘。如果有人问我1或0的阶乘，我就直接回答1；如果有人问我1以上数n的阶乘，我就再找一个人去算(n-1)的阶乘，等他算完我再乘n就好了。" 我们可以用一个函数来代表这样的一个人： 求阶乘的人(要算几的阶乘?) { if (问1或0的阶乘) 结果=1; else { 再找个人求(n-1)的阶乘; 结果=n*他算的(n-1)的阶乘; } return 结果; } 如何将上述思路转化为程序呢？其中的语句并不多，但关键是"再找个人求(n-1)的阶乘"如何办到。我们假设：已经将上述思路转化和已经做好了一个函数fact： long fact(int n) { …… } 则fact就可被看做一个"黑箱"，它的功能是求阶乘：只要给它一个参数n，它就能给出n!的结果来。例如fact(1)就可以得到1的阶乘，fact(2)就可以得到2的阶乘，fact(n)就可以得到n的阶乘……那么"求(n-1)的阶乘"就应写为fact(n-1)。把这个结论再写进fact函数体为： long fact(int n) { long r; if (n==0 || n==1) r = 1; else r = n * fact(n-1); return r; } main() { int n; long y; printf("input an integer number:"); scanf("%d", &n); y = fact(n); printf("%d!=%ld", n, y); } 在尚未编写出fact函数时，假设fact函数已经编写好，并使用了fact函数（求n-1的阶乘）来编写fact函数本身，从而"巧妙"地解决了问题，这就是递归的思想。 以上将main函数也一并给出了，是本例的完整程序。其运行结果为： input an integer number:4↓ 4!=24 如何分析递归程序的执行过程呢？显然图7.12的"赵"、"钱"、"孙"、"李"是4个不同的人，而不是一个人；尽管在程序中都用同一个函数fact代表。因此分析递归程序的关键是： 尽管函数调用自身（同一函数），但要把每次所调用的函数都看做是不同的函数，这些函数具有相同的参数、返回值和语句。 我们可以把程序中的fact函数连同其中的语句照抄3遍，如图7.13所示。这样连同main函数，就是一个由5个函数组成的程序。为了区别，将照抄的3个fact函数分别更名为fact'、fact''、fact'''（注意这里仅为思考的过程，C程序中的函数名是不能带 ' 的）。则递归调用就可被转换为对这5个函数的嵌套调用：main→fact→fact'→fact''→fact'''，5个函数分别具有5个独立的空间，其中有同名变量n、r，但"同名不乱"。按照前面介绍的一般嵌套函数的调用过程，就能分析出递归的执行过程了。函数空间情况如图7.13所示。 Hanoi（汉诺）塔问题。 如图7.14，一块板上有三根针：A、B、C。A针上套有n个大小不等的圆盘，大的在下，小的在上。要把这n个圆盘从A针移到C针上，每次只能移动一个圆盘，移动可以借助B针进行。但在任何时候，任何针上的圆盘都必须保持大盘在下，小盘在上。你能求出移动的步骤吗？ 【分析】如果A上仅有1个盘子，则将该盘直接从A移动到C即可，无须借助B。 如果A上有2个盘子，则需分3步进行： (1) 将A上的第1个圆盘移到B上； (2) 再将A上的第2个圆盘移到C上； (3) 最后将B上的那个圆盘移到C上。 当A上有3个或3个以上的盘子时，与有2个盘子的移动方式是类似的；我们可归纳为当A上有n个盘子（n大于等于2）时，都需分3步进行： (1) 把A的上方n-1个圆盘移到B上（中间过程可借助于C，移动后C针仍为空）； (2) 把A的最后一个圆盘移到C上（移动后A针为空）； (3) 把B的那n-1个圆盘移到C上（中间过程可借助于A，移动后A针为空）； 其中第(2)步最容易进行；但第(1)步和第(3)步该如何做呢？我们编写一个函数实现"Hanoi（汉诺）塔问题"，该函数为： move(int n,char x,char y,char z) { …… } 其中参数n表示有几个圆盘，x、y、z分别表示3根针，其含义是函数将把x针上的n个圆盘移到z针上，中间可借助y针进行。 假设该函数已经编写成功，则我们可以把它当做"黑箱"，只要给它n、x、y、z四个参数，它就能实现移动。例如若把n个圆盘从A针移到C针，中间借助B针，只要调用： move(n, 'A', 'B', 'C'); 函数就会帮我们完成了。那么要把A针上的n-1个圆盘移到B针上，中间借助C针，该如何做呢？只要调用： move(n-1, 'A', 'C', 'B'); 仅 此一句我们就完成了第(1)步。为什么如此简单？因为递归的思想使我们可以在move函数还没有编写好的情况下，就使用move函数来编写move函数本 身。如同程序例7.7，"赵"要求n!，但并不亲自连乘，他又找了一个人"李"把求(n-1)!这个较复杂的任务交给"李"来做，于是对于"赵"来说只要 调用fact(n-1)就可以算出(n-1)!了。 同样道理，第(3)步是把B针上的n-1个圆盘移到C针上，中间借助A针，这只需调用： move(n-1, 'B', 'A', 'C'); 【程序例7.8】汉诺（Hanoi）塔问题求解程序。 move(int n,char x,char y,char z) /*n个圆盘从x针借y针移到z针*/ { if(n==1) printf("%c-->%c\n",x,z); /*把x的一个圆盘直接移到z,无须借助y*/ else { move(n-1, x, z, y); /*把x的n-1个圆盘移到y(借助z)*/ printf("%c-->%c\n",x,z); /*把x的一个圆盘移到z*/ move(n-1, y, x, z); /*把y的n-1个圆盘移到z(借助x)*/ } } main() { int n; printf("请输入圆盘数："); scanf("%d", &n); printf("%3d 个圆盘的移动步骤是：\n", n); move(n, 'A', 'B', 'C'); } 程序的运行结果为： 请输入圆盘数：4↓ 4 个圆盘的移动步骤是： A-->B A-->C B-->C A-->B C-->A C-->B A-->B A-->C B-->C B-->A C-->A B-->C A-->B A-->C B-->C 当A针上有4个盘子时，需要移动15次。如果A针上有64个盘子，要完成汉诺塔的搬迁，需要的移动次数是：264-1 = 18446744073709551615 递归是将一个较大的问题归约为一个或多个类似子问题的求解方法。而这些子问题在结构上与原问题相同，但比原问题简单。通过递归可以巧妙地解决很多相对复杂的问题。然而递归的缺点是函数逐层调用，其执行的时间和空间开销都比较大。 |
|
|
