函数的递归调用

L/O/G/O6.6函数的递归调用章节回顾1.以下正确的函数定义形式为：【】A．doublefun(intx,inty)B.doublefun(intx;inty)C.doublefun(intx,inty);D.doublefun(intx,y)2.以下不正确的描述是：【】A．在C程序中，实参可以是常量、变量或表达式B．在C程序中，形参可以是常量、变量或表达式C．在C程序中，实参可以是任意类型D．形参应与其对应的实参在个数、类型、顺序上保持一致3.在C程序中，用简单变量作为实参时，它与对应的形参之间的数据传递方式为：【】A．地址传递B．单向传递C．按用户指定方式传递D．由实参传递给形参，再由形参传回给实参4.在C程序中，函数的返回值的类型由：【】A．return语句中的表达式的类型决定B．调用该函数时的调用函数决定C．调用该函数时由系统临时决定D．在定义该函数时由函数的类型决定ABBD主要内容一、引入新问题二、函数递归概述三、汉诺塔问题四、课堂练习五、课程小结一、引入新问题五位学生坐成一排，学生之间不知道相互的年龄。老师问最后一名学生，即第5名学生，她和她前面这一排学生的年龄总和是多少？思考问题：12345你们年龄之和？你们年龄之和？你们年龄之和？你们年龄之和？我们共37岁（27+10）我们共27岁（19+8）我们共19岁（10+9）我10岁你们年龄之和我们共46岁（37+9）)1()1()1()(nmyAgenntotalAgemyAgentotalAge递归公式二、函数递归概述1.递归的定义：调用一个函数时直接或间接调用自身,称之为函数的递归。2.一个问题能够成为递归必须具备的条件是：3.程序中的递归方式:直接递归调用：函数直接调用本身间接递归调用：函数间接调用本身后一部分与原始问题类似后一部分是原始问题的简化)1()1()1()(nmyAgenntotalAgemyAgentotalAge•说明–C语言对递归函数的自调用次数没有限制–必须有递归结束条件intf(x)intx;{inty,z;……z=f(y);……return(2*z);}直接调用间接调用intf1(x)intx;{inty,z;……z=f2(y);……return(2*z);}intf2(t)intt;{inta,c;……c=f1(a);……return(3+c);}用C语言解决上述思考题9岁8岁10岁9岁totalAge(5)=myAge+totalAge(4)totalAge(4)=myAge+totalAge(3)totalAge(3)=myAge+totalAge(2)totalAge(2)=myAge+totalAge(1)totalAge(4)=10+27=37totalAge(3)=8+19=27totalAge(2)=9+10=19totalAge(1)=myAge=10Main()调用子函数totalAge(5)=9+37=4610岁)1()1()1()(nmyAgenntotalAgemyAgentotalAgetotalAge(1)=myAgevoidmain(){intm;printf(inputthestudent'snumber:);scanf(%d,&m);if(m=0)printf(thenumberiserror\n);elseprintf(allstudent'sageis:%d,totalAge(m));}inttotalAge(intn){inttotal,myAge;printf(inputtotalnumber(%d)\n,n);printf(pleaseinputthe%dstudent'sage:,n);scanf(%d,&myAge);if(n1)total=myAge+totalAge(n-1);elseif(n==1)total=myAge;printf(fromtotalnumber(%d)return%d\n,n,total);getch();returntotal;}三、汉诺塔问题BC一个古典的数学问题：古代有一个梵塔，塔内有3个座A、B、C，开始时A座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把这64个盘子从A座移动到C座，每次只允许移动一个盘，且在移动过程中，在每个座上都始终保持大盘在下，小盘在上。在移动过程中可以利用B座，写出移动步骤。An个盘子ABC动画演示：分析3个盘子的情况：1.将A座上2个盘子移到B座（借助C）；2.将A座上1个盘子移到C座；3.将B座上2个盘子移到C座（借助A）。其中第2步可以直接实现。第1、3步还需要递归分解。ABCABCABC递归分解：第1步——将A座上2个盘子移到B座（借助C），分解为：1.1将A上一个盘子从A移到C；1.2将A上一个盘子从A移到B；1.3将C上一个盘子从C移到B。ABC1.1ABC1.2ABC1.3ABC3.第3步——将B座上2个盘子移到C座（借助A），分解为：3.1将B上一个盘子从B移到A；3.2将B上一个盘子从B移到C；3.3将A上一个盘子从A移到C。将以上综合起来，可得到移动3个盘子的步骤为：A→C，A→B，C→B，A→C，B→A，B→C，A→C。共经历7（=23－1）步。可以推知，移动n个盘子需要经历2n－1。1.将A座上n-1个盘子借助C座移到B座上；2.将A座上剩下的1个盘子移到C座上；3.将B座上n-1个盘子借助A座移到C座上。将第1步和第3步表示为：将“a”座上n-1个盘子借助“b”座移到“c”座。只是在第1步和第3步中，one、two、three和A、B、C的对应关系不同。对第1步，对用关系是：a——A，b——C，c——B。对第3步，对用关系是：a——B，b——A，c——C。因此，可以将上面的3个步骤分成两类操作：⑴将n-1个盘子从一个座移到另一个座上（n1）；⑵将1个盘子从一个座移到另一个座上；分别用两个函数来实现这两类操作。hanoi(n,a,b,c)表示“将n个盘子从a座借助b座移到c座。a、b、c对应不同情况的A、B、C。将n个盘子从A座移到C座，可以分解为3个步骤：第二步：将A上剩下的一个移至C上.第一步：先将A塔n-1个盘子借助于C移至B上第三步：将B上n-1个盘子借助于A移至C上.第一步和第三部为同一问题,都为n-1个盘子借助于一个空塔移至另一塔上。算法分析：//汉诺塔#includestdio.hvoidhanoi(intn,chara,charb,charc){if(n=1){hanoi(n-1,a,c,b);printf(“%c--%c\n”,a,c);hanoi(n-1,b,a,c);}}voidmain(){intn;printf(Inputthenumberofdiskes:\n“);scanf(“%d”,&n);hanoi(n,'A','B','C');}源程序：hanoi(n,a,b,c)表示n个盘子从a塔借助于b塔(空)移至c塔。调用时塔用字符常量A，B，C表示。四、课堂练习#includestdio.hlongf(intn);/*函数原型声明*/voidmain(void){longValue;intn;printf(Pleaseinputanumber:);do{scanf(%d,&n);if(n0){printf(Dataerror!);}}while(n0);/*如果输入n0,打印提示并重新输入*/Value=f(n);/*调用函数*/printf(f(%d)=%ld\n,n,Value);}【练习题】要求能够输出斐波那契数列第n个数是什么，斐波那契数列定义为：00111)2()1()(nnnnfnfnf/*函数名：f*//*功能：递归求斐波那契数列*//*参数：n(整型)*//*返回值：项序为n的递归求斐波那契数列值(长整型)*/longf(intn){longy;if(n==0)y=0;elseif(n==1)y=1;elsey=f(n-1)+f(n-2);returny;}五、课程小结调用一个函数时直接或间接调用自身,称之为函数的递归。函数递归定义函数递归特点递归注意事项后一部分与原始问题类似；后一部分是原始问题的简化C语言对递归函数的自调用次数没有限制必须有递归结束条件