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

《c语言--函数的递归调用.ppt》由会员分享，可在线阅读，更多相关《c语言--函数的递归调用.ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2第五章 函数计算机科学系计算机科学系 陈垚陈垚2我们先看这样一个例子:v说有一只调皮的小猴子说有一只调皮的小猴子,摘了一堆水果摘了一堆水果,第一天第一天吃了水果的一半吃了水果的一半,又多吃了一个又多吃了一个;第二天吃了剩第二天吃了剩下水果的一半下水果的一半,又多吃了一个又多吃了一个;依次类推依次类推.到第到第十天十天,发现只剩下了发现只剩下了1个水果个水果,请问这只猴子到请问这只猴子到底摘了多少个水果底摘了多少个水果?3第五章 函数计算机科学系计算机科学系 陈垚陈垚35.4 函数递归调用函数递归调用 后一部分与原始问题类似后一部分与原始问题类似 后一部分是原始问题的简化后一部分是原始问题的简

2、化1、定义：调用一个函数时直接或间接调用自身、定义：调用一个函数时直接或间接调用自身, 称之为称之为函数的递归函数的递归。2、一个问题能够成为递归必须具备的条件是：、一个问题能够成为递归必须具备的条件是：许多数学函数都是用递归的形式定义的：许多数学函数都是用递归的形式定义的：) 1()!1() 1 , 0(1!nnnnn)0()0(11nxxnxnn4第五章 函数计算机科学系计算机科学系 陈垚陈垚41. 直接递归调用：直接递归调用：函数直接调用本身函数直接调用本身2. 间接递归调用：间接递归调用：函数间接调用本身函数间接调用本身5第五章 函数计算机科学系计算机科学系 陈垚陈垚5v说明说明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) ; 6第五章 函数计算机科学系计算机科学系 陈垚陈垚6 思考如下问题：思考如下问题：例例1: 有有5个人坐在一起个人坐在一起,问第问第5个人多少岁个人多少岁,他说比第他说比第4个人大个人

4、大2岁岁;问第问第4个人岁数个人岁数,他说比他说比第第3个人大个人大2岁岁;问第问第3个人个人,又说比第又说比第2个大个大2岁岁;问第问第2个人，说比第个人，说比第1个人大个人大2岁；最后问第岁；最后问第1个人，他说他个人，他说他10岁；请问第岁；请问第5个人多大个人多大?比她大比她大2岁岁比她大比她大2岁岁比她大比她大2岁岁比她大比她大2岁岁我我10岁岁7第五章 函数计算机科学系计算机科学系 陈垚陈垚7age(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

5、(2)+2age(2)=age(1)+2age(1)=108第五章 函数计算机科学系计算机科学系 陈垚陈垚8 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=189第五章 函数计算机科学系计算机科学系 陈垚陈垚9例例2:2: 汉诺塔汉诺塔(

6、Hanoi)问题问题BC问题问题: : 将将A塔上塔上n个盘子移至个盘子移至C(借助于借助于B)。 移动移动时时,保证三个塔始终是大盘在下保证三个塔始终是大盘在下,小盘在上，小盘在上，并且每次只能移动一个盘子。并且每次只能移动一个盘子。An个盘子个盘子10第五章 函数计算机科学系计算机科学系 陈垚陈垚10必须用递归方式解决必须用递归方式解决1) 先将先将A塔塔n 1个盘子借助于个盘子借助于C移至移至B上上2) 将将A上剩下的一个移至上剩下的一个移至C上上.3) 将将B上上n 1个盘子借助于个盘子借助于A移至移至C上上.可以看到可以看到: 1)、3)为同一问题为同一问题,都为都为n 1个盘子借助

7、于一个个盘子借助于一个 空塔移至另一塔上。空塔移至另一塔上。11第五章 函数计算机科学系计算机科学系 陈垚陈垚11ABC例例 Hanoi问题问题12第五章 函数计算机科学系计算机科学系 陈垚陈垚12void move(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

8、); hanoi(n,A,B,C); 程序如下：程序如下：ABCABCABCABC13第五章 函数计算机科学系计算机科学系 陈垚陈垚13 input the number of diskes:3 The step to moving 3 diskes: A C A B C B A C B A B C A C运行情况如下：运行情况如下：14第五章 函数计算机科学系计算机科学系 陈垚陈垚14 move (getone, putone) 表示从表示从getone 塔移一个盘子至塔移一个盘子至putone塔塔 hanoi(n, one, two, three) 表示表示n个盘子从个盘子从one塔借助于

9、塔借助于two塔塔(空空)移移 至至three塔，塔，调用时塔用字符常量调用时塔用字符常量A , B , C 表示。表示。在程序中有两个函数在程序中有两个函数: :15第五章 函数计算机科学系计算机科学系 陈垚陈垚151. 函数递归的定义函数递归的定义2. 函数递归的特点函数递归的特点3.函数递归调用的方式函数递归调用的方式本节课主要介绍的内容：本节课主要介绍的内容：16第五章 函数计算机科学系计算机科学系 陈垚陈垚16上机作业：上机作业：v说有一只调皮的小猴子说有一只调皮的小猴子,摘了一堆水果摘了一堆水果,第一天第一天吃了水果的一半吃了水果的一半,又多吃了一个又多吃了一个;第二天吃了剩第二天吃了剩下水果的一半下水果的一半,又多吃了一个又多吃了一个;依次类推依次类推.到第到第十天十天,发现只剩下了发现只剩下了10个水果个水果,请问这只猴子到请问这只猴子到底摘了多少个水果底摘了多少个水果?结束结束