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

1、1 第五章 函数 计算机科学系计算机科学系 陈垚陈垚 1 张福祥张福祥 主编主编 辽宁大学出版社辽宁大学出版社 2 第五章 函数 计算机科学系计算机科学系 陈垚陈垚 2 我们先看这样一个例子: v说有一只调皮的小猴子说有一只调皮的小猴子,摘了一堆水果摘了一堆水果,第一天第一天 吃了水果的一半吃了水果的一半,又多吃了一个又多吃了一个;第二天吃了剩第二天吃了剩 下水果的一半下水果的一半,又多吃了一个又多吃了一个;依次类推依次类推.到第到第 十天十天,发现只剩下了发现只剩下了1个水果个水果,请问这只猴子到请问这只猴子到 底摘了多少个水果底摘了多少个水果? 3 第五章 函数 计算机科学系计算机科学系

2、陈垚陈垚 3 5.4 函数递归调用函数递归调用 后一部分与原始问题类似后一部分与原始问题类似 后一部分是原始问题的简化后一部分是原始问题的简化 1、定义：调用一个函数时直接或间接调用自身、定义：调用一个函数时直接或间接调用自身, 称之为称之为函数的递归函数的递归。 2、一个问题能够成为递归必须具备的条件是：、一个问题能够成为递归必须具备的条件是： 许多数学函数都是用递归的形式定义的：许多数学函数都是用递归的形式定义的： ) 1()!1( ) 1 , 0(1 ! nnn n n )0( )0(1 1 nxx n x n n 4 第五章 函数 计算机科学系计算机科学系 陈垚陈垚 4 1. 直接递归

3、调用：直接递归调用：函数直接调用本身函数直接调用本身 2. 间接递归调用：间接递归调用：函数间接调用本身函数间接调用本身 5 第五章 函数 计算机科学系计算机科学系 陈垚陈垚 5 v说明说明 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) ; ret

4、urn(3+c) ; 6 第五章 函数 计算机科学系计算机科学系 陈垚陈垚 6 思考如下问题：思考如下问题： 例例1: 有有5个人坐在一起个人坐在一起,问第问第5个人多少岁个人多少岁, 他说比第他说比第4个人大个人大2岁岁;问第问第4个人岁数个人岁数,他说比他说比 第第3个人大个人大2岁岁;问第问第3个人个人,又说比第又说比第2个大个大2岁岁; 问第问第2个人，说比第个人，说比第1个人大个人大2岁；最后问第岁；最后问第1 个人，他说他个人，他说他10岁；请问第岁；请问第5个人多大个人多大? 比她大比她大2岁岁 比她大比她大2岁岁 比她大比她大2岁岁 比她大比她大2岁岁 我我10岁岁 7 第五章

5、 函数 计算机科学系计算机科学系 陈垚陈垚 7 age(5) =16+2=18 age(4) =14+2=16 age(3) =12+2=14 age(2) =10+2=12 age(5) =age(4)+2 age(4) =age(3)+2 age(3) =age(2)+2 age(2) =age(1)+2 age(1) =10 8 第五章 函数 计算机科学系计算机科学系 陈垚陈垚 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

6、 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=18 9 第五章 函数 计算机科学系计算机科学系 陈垚陈垚 9 例例2:2: 汉诺塔汉诺塔(Hanoi)问题问题 B C 问题问题: : 将将A塔上塔上n个盘子移至个盘子移至C(借助于借助于B)。 移动移动 时时,保证三个塔始终是大盘在下保证三个塔始终是大盘在下,小盘在上小盘在上， 并且每次只能移动一个盘子并且每次只能移动一个盘子。 A n个盘子个盘子 10 第五章 函数 计算机科学系计算机科学系

7、 陈垚陈垚 10 必须用递归方式解决必须用递归方式解决 1) 先将先将A塔塔n 1个盘子借助于个盘子借助于C移至移至B上上 2) 将将A上剩下的一个移至上剩下的一个移至C上上. 3) 将将B上上n 1个盘子借助于个盘子借助于A移至移至C上上. 可以看到可以看到: 1)、3)为同一问题为同一问题,都为都为n 1个盘子借助于一个个盘子借助于一个 空塔移至另一塔上。空塔移至另一塔上。 11 第五章 函数 计算机科学系计算机科学系 陈垚陈垚 11 ABC 例例 Hanoi问题问题 12 第五章 函数 计算机科学系计算机科学系 陈垚陈垚 12 void move(char getone, char pu

8、tone) 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, hanoi(n,A,B,C); 程序如下：程序如下： ABC ABC ABC ABC 13 第五章 函数 计算机科学系计算机科学系 陈垚陈垚 13 input the number of diskes:3 The step to moving 3 diskes

9、: A C A B C B A C B A B C A C 运行情况如下：运行情况如下： 14 第五章 函数 计算机科学系计算机科学系 陈垚陈垚 14 15 第五章 函数 计算机科学系计算机科学系 陈垚陈垚 15 move (getone, putone) 表示从表示从getone 塔移一个盘子至塔移一个盘子至putone塔塔 hanoi(n, one, two, three) 表示表示n个盘子从个盘子从one塔借助于塔借助于two塔塔(空空)移移 至至three塔，塔，调用时塔用字符常量调用时塔用字符常量A , B , C 表示。表示。 在程序中有两个函数在程序中有两个函数: : 16 第五章 函数 计算机科学系计算机科学系 陈垚陈垚 16 1. 函数递归的定义函数递归的定义 2. 函数递归的特点函数递归的特点 3.函数递归调用的方式函数递归调用的方式 本节课主要介绍的内容：本节课主要介绍的内容： 17 第五章 函数 计算机科学系计算机科学系 陈垚陈垚 17 上机作业：上机作业： v说有一只调皮的小猴子说有一只调皮的小猴子,摘了一堆水果摘了一