c语言-函数的递归调用课件.ppt

1、1第五章 函数 张福祥张福祥 主编主编 辽宁大学出版社辽宁大学出版社 1PPTPPT课件课件2第五章 函数我们先看这样一个例子:v说有一只调皮的小猴子说有一只调皮的小猴子,摘了一堆水果摘了一堆水果,第一天第一天吃了水果的一半吃了水果的一半,又多吃了一个又多吃了一个;第二天吃了剩第二天吃了剩下水果的一半下水果的一半,又多吃了一个又多吃了一个;依次类推依次类推.到第到第十天十天,发现只剩下了发现只剩下了1个水果个水果,请问这只猴子到请问这只猴子到底摘了多少个水果底摘了多少个水果?2PPTPPT课件课件3第五章 函数5.4 函数递归调用函数递归调用 后一部分与原始问题类似后一部分与原始问题类似 后一

2、部分是原始问题的简化后一部分是原始问题的简化1、定义：调用一个函数时直接或间接调用自身、定义：调用一个函数时直接或间接调用自身,称之为称之为函数的递归函数的递归。2、一个问题能够成为递归必须具备的条件是：、一个问题能够成为递归必须具备的条件是：许多数学函数都是用递归的形式定义的：许多数学函数都是用递归的形式定义的：)1()!1()1,0(1!nnnnn)0()0(11nxxnxnn3PPTPPT课件课件4第五章 函数1.直接递归调用：直接递归调用：函数直接调用本身函数直接调用本身2.间接递归调用：间接递归调用：函数间接调用本身函数间接调用本身4PPTPPT课件课件5第五章 函数v说明说明C语言

3、语言对递归函数的自调用次数没有限制对递归函数的自调用次数没有限制必须有递归结束条件必须有递归结束条件 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);5PPTPPT课件课件6第五章 函数 思考如下问题：思考如下问题：例例1:有有5个人坐在一起个人坐在一起,问第问第5个人多少岁个人多少岁,他说比第他说比第4个人大个人大2岁岁;问第问第4个人岁数个人岁数,他说比他说比第第3个人大个人大2岁岁;问

4、第问第3个人个人,又说比第又说比第2个大个大2岁岁;问第问第2个人，说比第个人，说比第1个人大个人大2岁；最后问第岁；最后问第1个人，他说他个人，他说他10岁；请问第岁；请问第5个人多大个人多大?比她大比她大2岁岁比她大比她大2岁岁比她大比她大2岁岁比她大比她大2岁岁我我10岁岁6PPTPPT课件课件7第五章 函数age(5)=16+2=18age(4)=14+2=16age(3)=12+2=14age(2)=10+2=12age(5)=age(4)+2age(4)=age(3)+2age(3)=age(2)+2age(2)=age(1)+2age(1)=107PPTPPT课件课件8第五章 函

5、数 main()printf(“%d”,age(5);age(int n)int c;if(n=1)c=10;else c=age(n-1)+2;return(c);age(5)c=10 n=1 c=age(3)+2 n=4 c=age(2)+2 n=3 c=age(1)+2 n=2 c=age(4)+2 n=5 c=10+2=12 c=12+2=14c=14+2=16c=16+2=188PPTPPT课件课件9第五章 函数例例2:2:汉诺塔汉诺塔(Hanoi)问题问题BC问题问题:将将A塔上塔上n个盘子移至个盘子移至C(借助于借助于B)。移动移动时时,保证三个塔始终是大盘在下保证三个塔始终是大

6、盘在下,小盘在上小盘在上，并且每次只能移动一个盘子并且每次只能移动一个盘子。An个盘子个盘子9PPTPPT课件课件10第五章 函数必须用递归方式解决必须用递归方式解决1)先将先将A塔塔n 1个盘子借助于个盘子借助于C移至移至B上上2)将将A上剩下的一个移至上剩下的一个移至C上上.3)将将B上上n 1个盘子借助于个盘子借助于A移至移至C上上.可以看到可以看到:1)、3)为同一问题为同一问题,都为都为n 1个盘子借助于一个个盘子借助于一个 空塔移至另一塔上。空塔移至另一塔上。10PPTPPT课件课件11第五章 函数ABC例例 Hanoi问题问题11PPTPPT课件课件12第五章 函数void mo

7、ve(char getone,char putone)printf(%c-%cn,getone,putone);void hanoi(int n,char A,char B,char C)if(n=1)move(A,C);else hanoi(n-1,A,C,B);move(A,C);hanoi(n-1,B,A,C);main()int n;scanf(%d,&n);hanoi(n,A,B,C);程序如下：程序如下：ABCABCABCABC12PPTPPT课件课件13第五章 函数 input the number of diskes:3 The step to moving 3 diskes:

8、A C A B C B A C B A B C A C运行情况如下：运行情况如下：13PPTPPT课件课件14第五章 函数 move(getone,putone)表示从表示从getone 塔移一个盘子至塔移一个盘子至putone塔塔 hanoi(n,one,two,three)表示表示n个盘子从个盘子从one塔借助于塔借助于two塔塔(空空)移移 至至three塔，塔，调用时塔用字符常量调用时塔用字符常量A,B,C 表示。表示。在程序中有两个函数在程序中有两个函数:14PPTPPT课件课件15第五章 函数 小结小结1.函数递归的定义函数递归的定义2.函数递归的特点函数递归的特点3.函数递归调用的方式函数递归调用的方式本节课主要介绍的内容：本节课主要介绍的内容：15PPTPPT课件课件16第五章 函数上机作业：上机作业：v说有一只调皮的小猴子说有一只调皮的小猴子,摘了一堆水果摘了一堆水果,第一天第一天吃了水果的一半吃了水果的一半,又多吃了一个又多吃了一个;第二天吃了剩第二天吃了剩下水果的一半下水果的一半,又多吃了一个又多吃了一个;依次类推依次类推.到第到第十天十天,发现只剩下了发现只剩下了10个水果个水果,请问这只猴子到请问这只猴子到底摘了多少个水果底摘了多少个水果?16PPTPPT课件课件