C语言程序设计 教学课件 作者 孙锋 主编 付兴宏 王庆桦 副主编chapter9.ppt

《C语言程序设计 教学课件 作者 孙锋 主编 付兴宏 王庆桦 副主编chapter9.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、C语言程序设计第9章函数的高级应用9.1递归9.1.1递归问题的提出生活中有些问题看似无解或十分复杂，例如：著名的汉诺塔Hanoi问题。相传在古代印度的Bramah庙中，有三根插在黄铜板上的宝石柱，在其中一个柱子上放了64个金盘子，大盘在下，小盘在上，称为汉诺塔。和尚们想把这些盘子从一个柱子移到另一个柱子上，但规定每次只允许移动一个，而且小盘子永远不能放在大盘子之下。在移动时可以利用这三根柱子中的任意一根。若把这个题目变为手动的游戏，虽然需要动动脑筋，花费一些时间，还是可以实现的。但是如果要求编写一个程序，按照盘子的移动过程，显示记录每一次移动操作，直

2、到任务全部完成，恐怕大家想想都会感到头痛。9.1递归9.1递归现在，我们来分析一下，假设有n个盘子。当n=1时，直接把盘子从原来柱子移动到目标柱子即可。当n=2时，需要经过三次移动，完成任务，具体移动过程，如图9-1所示。当n=3时，我们可以把3个盘子分为两组，上面2个较小的盘子一组，下面当前最大的盘子一组。通过上面的方法，可以先按照游戏规则，借助C柱，把上面2个较小的盘子从A柱移到B柱；然后把第3个盘子从A柱移到C柱；最后，再重复使用上面的方法，借助A柱，把2个较小的盘子从B柱移到C柱。从而完成整个任务。依次类推，当n=64时，只要我们能解决63个盘

3、子的移动，就可完成64个盘子的任务；要移动63个盘子，就得先解决62个盘子，……。也就是说，为了完成任务要从64个盘子一直回推到2个盘子，这就是递归。在解决问题时，把解决方案转换成一个新的问题，该问题的解决方案与原来问题的解决方案相同，仅仅是处理对象不同了，且处理对象也是规律地递增或递减。9.1递归9.1.2函数的递归调用C语言中，在调用一个函数的过程中直接或间接地调用该函数本身，称为函数的递归调用。例如：intf(intx)｛inty,ｚ;z=f(y);return(2*z);｝这个函数是一个递归函数，但是运行该函数将无休止地调用其自身，这当然是不正

4、确的。为了防止递归调用无终止地进行，必须在函数内有终止递归调用的条件。常用的办法是加判断语句，满足某种条件后就不再作递归调用，然后逐层返回。9.1递归一个问题要采用函数递归的方法解决时，必须符合以下3个条件：条件1：能够把需求解决的问题转换为一个新问题，该问题的解法与原问题的解法相同，只是处理对象发生了规律的递增或递减。条件2：应用这个转化过程可使原问题得到解决。条件3：必须存在一个明确的使递归结束的条件。例9-1用递归方法求n！。问题分析：n!所对应的递归函数表达式：。9.1递归#includelongfact(intj)/*函数类

5、型为long，因为n!可能会是一个很大的值*/{intsum;if(j==0)/*递归结束条件*/sum=1;else/*没有满足递归结束条件时，继续递归调用*/sum=j*fact(j-1);returnsum;}main(){inti;printf("Pleaseinputi:");scanf("%d",&i);printf("%ld!=%d",i,fact(i));/*由于函数类型为long，所以输出格式为%ld*/}运行结果：9.1递归例9-2编写函数fib(n)，其功是计算Fibonacci数列的第n项。问题分析：Fibonacci数列是

6、1，1，2，3，5，8，13，21，……，其特点是从第3项开始，每一项的值是其前两项之和。可得到递归函数公式如下：9.1递归intfib(intn){intresult;if(n==1

7、

8、n==2)result=1;elseresult=fib(n-2)+fib(n-1);returnresult;}程序说明：函数递归调用的过程，当函数fib(n)自己调用自己时，系统将自动把函数当前的局部变量和形参保存起来，在新一次函数调用中，系统为该次调用的函数中所用到的局部变量和形参开辟另外的存储单元。因此，递归函数调用的层次越多，同名局部变量和形参占用的存储单元

9、也就越多。当本次调用运行结束时，系统将释放本次调用时所占用的存储单元，程序的执行流程返回到上一层的调用点，同时取出当初离开该层时保存在内存中的局部变量和形参的值。例如，函数调用fib(4)，其过程如图9-2所示9.1递归9.1递归例9-3编写函数MaCathy(x)，计算给定x的McCathy(x)的值。问题分析：本题以递归调用的结果作为下一次递归调用的参数。intMcCathy(intx){if(x>100)return(x-10);elsereturn(McCathy(McCathy(x+11)));}9.1递归例9-4编写程序，由键盘输入整数n（

10、n<100），然后将n分解为若干个整数相加，输出这些数的乘积，且要保证乘积是最大的。问题分析：