函数的递归调用.ppt
L/O/G/O6.6 6.6 6.6 6.6 函数的递归调用函数的递归调用函数的递归调用函数的递归调用章节回顾章节回顾1.以下正确的函数定义形式为：以下正确的函数定义形式为：【】Adoublefun(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程序中，函数的返回值的类型由：程序中，函数的返回值的类型由：【】Areturn语句中的表达式的类型决定语句中的表达式的类型决定B调用该函数时的调用函数决定调用该函数时的调用函数决定C调用该函数时由系统临时决定调用该函数时由系统临时决定D在定义该函数时由函数的类型决定在定义该函数时由函数的类型决定A AB BB BD D主要内容主要内容主要内容主要内容一、一、一、一、引入新问题引入新问题引入新问题引入新问题二、二、二、二、函数递归概述函数递归概述函数递归概述函数递归概述三、三、三、三、汉诺塔问题汉诺塔问题汉诺塔问题汉诺塔问题四、四、四、四、课堂练习课堂练习课堂练习课堂练习五、五、五、五、课程小结课程小结课程小结课程小结一、引入新问题一、引入新问题 五位学生坐成一排，学生之间不知道相互的年龄。老师问最后一名学生，即第5名学生，她和她前面这一排学生的年龄总和是多少？思考问题：1 12 23 34 45 5你们年龄之和？你们年龄之和？你们年龄之和？你们年龄之和？你们年龄之和？你们年龄之和？你们年龄之和？你们年龄之和？我们共我们共3737岁岁（27+1027+10）我们共我们共2727岁岁（19+819+8）我们共我们共1919岁岁（10+910+9）我我1010岁岁你你们们年年龄龄之之和和我我们们共共4 46 6岁岁（3 37 7+9 9）递归公式递归公式二、函数递归概述二、函数递归概述1.递归的定义：调用一个函数时直接或间接调用自身,称之为函数的递归函数的递归。2.一个问题能够成为递归必须具备的条件是：3.程序中的递归方式:直接递归调用：直接递归调用：函数直接调用本身间接递归调用：间接递归调用：函数间接调用本身 后一部分与原始问题类似后一部分与原始问题类似 后一部分是原始问题的简化后一部分是原始问题的简化说明说明C C语言语言对递归函数的自调用次数没有限制对递归函数的自调用次数没有限制必须有递归结束条件必须有递归结束条件 int f(x)int x;int y,z;z=f(y);return(2*z);直接调用直接调用直接调用直接调用间接调用间接调用间接调用间接调用int f1(x)int x;int y,z;z=f2(y);return(2*z);int f2(t)int t;int a,c;c=f1(a);return(3+c);用用C C语言解决上述思考题语言解决上述思考题9 9岁岁8 8岁岁1010岁岁9 9岁岁totalAge(5)totalAge(5)=myAge+totalAge(4)=myAge+totalAge(4)totalAge(4)totalAge(4)=myAge+totalAge(3)=myAge+totalAge(3)totalAge(3)totalAge(3)=myAge+totalAge(2)=myAge+totalAge(2)totalAge(2)totalAge(2)=myAge+totalAge(1)=myAge+totalAge(1)totalAge(4)totalAge(4)=1010+27+27=37=37totalAge(3)totalAge(3)=8 8+19+19=27=27totalAge(2)totalAge(2)=9 9+10+10=19=19totalAge(1)totalAge(1)=myAge=myAge=1010M Ma ai in n()调调用用子子函函数数t to ot ta al lA Ag ge e(5 5)=9 9+3 37 7=4 46 61010岁岁totalAge(1)totalAge(1)=myAge=myAgevoid main()int m;printf(input the students number:);scanf(%d,&m);if(m1)total=myAge+totalAge(n-1);else if(n=1)total=myAge;printf(from totalnumber(%d)return%dn,n,total);getch();return total;三、汉诺塔问题三、汉诺塔问题BC一个古典的数学问题：一个古典的数学问题：古代有一个梵塔，塔内有古代有一个梵塔，塔内有3 3个座个座A、B、C，开始时，开始时A 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步还需要递归分解。步还需要递归分解。A B CA BCA B C递归分解：递归分解：第第1 步步将将A座上座上2个盘子移到个盘子移到B座（借助座（借助C），分解为：），分解为：1.1 将将A上一个盘子从上一个盘子从A移到移到C；1.2 将将A上一个盘子从上一个盘子从A移到移到B；1.3 将将C上一个盘子从上一个盘子从C移到移到B。A BC1.1A BC1.2A BC1.3A B C3.第第3步步将将B座上座上2个盘子移到个盘子移到C座座（借助（借助A），分解为：），分解为：3.1 将将B上一个盘子从上一个盘子从B移到移到A；3.2 将将B上一个盘子从上一个盘子从B移到移到C；3.3 将将A上一个盘子从上一个盘子从A移到移到C。将以上综合起来，可得到移动将以上综合起来，可得到移动3个盘子的步骤为：个盘子的步骤为：AC，A B，C B，A C，B A，B C，A C。共经历共经历7（=231）步。）步。可以推知，可以推知，移动移动 n 个盘子需要经个盘子需要经历历2 n 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步，对用关系是：步，对用关系是：aA，bC，cB。对第对第3步，对用关系是：步，对用关系是：aB，bA，cC。因此，可以将上面的因此，可以将上面的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 A上剩下的一个上剩下的一个 移至移至C C上上.第一步：先将第一步：先将A A塔塔n-1n-1个盘个盘 子借助于子借助于C C移至移至B B上上第三步：第三步：将将B B上上n-1n-1个盘个盘 子借助于子借助于A A移至移至C C上上.第第一一步步和和第第三三部部为为同同一一问问题题,都都为为n n-1 1个个盘盘子子借借助助于于一一个个空空塔塔移移至至另另一一塔塔上上。算法分析：算法分析：/汉诺塔汉诺塔#include void hanoi(int n,char a,char b,char c)if (n=1)hanoi(n-1,a,c,b);printf(“%c-%cn”,a,c);hanoi(n-1,b,a,c);void main()int n;printf(Input the number of diskes:n“);scanf(“%d”,&n);hanoi(n,A,B,C);源程序：源程序：hanoi(n,a,b,c)hanoi(n,a,b,c)表示表示n n个盘个盘子子从从a a塔借助于塔借助于b b塔塔(空空)移至移至c c塔塔。调调用用时时塔用字符常量塔用字符常量A A，B B，C C表示。表示。四、课堂练习四、课堂练习#includelongf(intn);/*函数原型声明函数原型声明*/voidmain(void)longValue;intn;printf(Pleaseinputanumber:);doscanf(%d,&n);if(n0)printf(Dataerror!);while(n0);/*如果输入如果输入n0,打印提示并重新输入打印提示并重新输入*/Value=f(n);/*调用函数调用函数*/printf(f(%d)=%ldn,n,Value);【练习题练习题】要求能够输出要求能够输出斐波那契数列斐波那契数列第第n个数是什么个数是什么，斐波那契数列定义为：斐波那契数列定义为：/*函数名：函数名：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 C语语言言对递对递归归函函数数的自的自调调用用次次数没数没有限制有限制 必必须须有有递递归归结结束束条条件件
