函数的递归调用

1、L/O/G/O 6.6 6.6 函数的递归调用函数的递归调用 章节回顾章节回顾 1. 以下正确的函数定义形式为：以下正确的函数定义形式为：【 】 Adouble fun(int x,int y) B. double fun(int x ;int y) C. double fun(int x,int y) ; D. double fun(int x,y) 2. 以下不正确的描述是：以下不正确的描述是：【 】 A在在C程序中，实参可以是常量、变量或表达式程序中，实参可以是常量、变量或表达式 B在在C程序中，形参可以是常量、变量或表达式程序中，形参可以是常量、变量或表达式 C在在C程序中，实参可以是

2、任意类型程序中，实参可以是任意类型 D形参应与其对应的实参在个数、类型、顺序上保持一致形参应与其对应的实参在个数、类型、顺序上保持一致 3. 在在C程序中，用简单变量作为实参时，它与对应的形参之间的数据传递方程序中，用简单变量作为实参时，它与对应的形参之间的数据传递方 式为：式为：【 】 A 地址传递地址传递 B 单向传递单向传递 C 按用户指定方式传递按用户指定方式传递 D 由实参传递给形参，再由形参传回给实参由实参传递给形参，再由形参传回给实参 4. 在在C程序中，函数的返回值的类型由：程序中，函数的返回值的类型由：【 】 Areturn语句中的表达式的类型决定语句中的表达式的类型决定 B

3、调用该函数时的调用函数决定调用该函数时的调用函数决定 C调用该函数时由系统临时决定调用该函数时由系统临时决定 D在定义该函数时由函数的类型决定在定义该函数时由函数的类型决定 A B B D 主要内容主要内容 一、一、 引入新问题引入新问题 二、二、 函数递归概述函数递归概述 三、三、 汉诺塔问题汉诺塔问题 四、四、 课堂练习课堂练习 五、五、 课程小结课程小结 一、引入新问题一、引入新问题 五位学生坐成一排，学生之间不知道相互的年 龄。老师问最后一名学生，即第5名学生，她和 她前面这一排学生的年龄总和是多少？ 思考问题： 12345 你们年龄之和？你们年龄之和？你们年龄之和？你们年龄之和？你们

4、年龄之和？你们年龄之和？你们年龄之和？你们年龄之和？ 我们共我们共3737岁岁 （27+1027+10） 我们共我们共2727岁岁 （19+819+8） 我们共我们共1919岁岁 （10+910+9） 我我1010岁岁 你们年龄之和你们年龄之和 我们共我们共46 46岁 岁 （37+9 37+9） ） ) 1( ) 1() 1( )( nmyAge nntotalAgemyAge ntotalAge 递归公式递归公式 二、函数递归概述二、函数递归概述 1. 递归的定义： 调用一个函数时直接或间接调用自身, 称之为函数的递归函数的递归。 2. 一个问题能够成为递归必须具备的条件是： 3. 程序中

5、的递归方式: 直接递归调用：直接递归调用：函数直接调用本身 间接递归调用：间接递归调用：函数间接调用本身 后一部分与原始问题类似后一部分与原始问题类似 后一部分是原始问题的简化后一部分是原始问题的简化 ) 1( ) 1() 1( )( nmyAge nntotalAgemyAge ntotalAge 说明说明 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(

6、y) ; return(2*z) ; int f2(t) int t ; int a, c ; c =f1(a) ; return(3+c) ; 用用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 =37 totalAge(3) =8+19 =27 totalAge(2) =9+10

7、=19 totalAge(1) =myAge =10 Main()Main()调用子函数 调用子函数 totalAge(5) =9+37 =46 10岁岁 ) 1( ) 1() 1( )( nmyAge nntotalAgemyAge ntotalAge totalAge(1) =myAge void main() int m; printf(input the students number:); scanf(%d, if(m1) total=myAge+totalAge(n-1); else if(n=1) total=myAge; printf(from totalnumber(%d)r

8、eturn %dn,n,total); getch(); return total; 三、汉诺塔问题三、汉诺塔问题 B C 一个古典的数学问题：一个古典的数学问题： 古代有一个梵塔，塔内有古代有一个梵塔，塔内有3个座个座A、B、C，开始时，开始时A 座上有座上有64个盘子，盘子大小不等，大的在下，小个盘子，盘子大小不等，大的在下，小 的在上。的在上。 有一个老和尚想把这有一个老和尚想把这64个盘子从个盘子从A座移动到座移动到C座，每座，每 次只允许移动一个盘，且在移动过程中，在每个次只允许移动一个盘，且在移动过程中，在每个 座上都始终保持座上都始终保持大盘在下，小盘在上大盘在下，小盘在上。在移

9、动过。在移动过 程中可以利用程中可以利用B 座，写出移动步骤。座，写出移动步骤。 A n个盘子个盘子 ABC 动画演示：动画演示： 分析分析3个盘子的情况：个盘子的情况： 1. 将将A座上座上2个盘子移到个盘子移到B座座 （借助（借助C）；）； 2. 将将A座上座上1个盘子移到个盘子移到C座；座； 3. 将将B座上座上2个盘子移到个盘子移到C座座 （借助（借助A）。）。 其中第其中第2 步可以直接实现。步可以直接实现。 第第1、3步还需要递归分解。步还需要递归分解。 A B C A BC A B C 递归分解：递归分解： 第第1 步步将将A座上座上2个盘子移到个盘子移到 B座（借助座（借助C）

10、，分解为：），分解为： 1.1 将将A上一个盘子从上一个盘子从A移到移到C； 1.2 将将A上一个盘子从上一个盘子从A移到移到B； 1.3 将将C上一个盘子从上一个盘子从C移到移到B。 A BC 1.1 A BC 1.2 A BC 1.3 A B C 3. 第第3步步将将B座上座上2个盘子移到个盘子移到 C座座 （借助（借助A），分解为：），分解为： 3.1 将将B上一个盘子从上一个盘子从B移到移到A； 3.2 将将B上一个盘子从上一个盘子从B移到移到C； 3.3 将将A上一个盘子从上一个盘子从A移到移到C。 将以上综合起来，可得到移动将以上综合起来，可得到移动3 个盘子的步骤为：个盘子的步骤

11、为： 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

12、、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

13、座。座。a、b、c对应不同情况的对应不同情况的 A、B、C。 将将n 个盘子从个盘子从A 座移到座移到C 座，可以分解为座，可以分解为3个步骤个步骤： 第二步：第二步：将将A上剩下的一个上剩下的一个 移至移至C上上. 第一步：先将第一步：先将A A塔塔n-1n-1个盘个盘 子借助于子借助于C C移至移至B B上上 第三步：第三步：将将B上上n-1个盘个盘 子借助于子借助于A移至移至C上上. 第一步和第三部第一步和第三部为同一问题为同一问题, 都为都为n-1个盘子借助于一个空塔移至另一塔上。个盘子借助于一个空塔移至另一塔上。 算法分析：算法分析： / 汉诺塔汉诺塔 # include void

14、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”, hanoi ( n, A , B , C ) ; 源程序：源程序： hanoi(n, a, b, c) 表示n个盘个盘子从从a 塔借助于b塔(空) 移至c塔。调调用时时 塔用字符常量A，

15、B ，C表示。 四、课堂练习四、课堂练习 #include long f(int n); /* 函数原型声明函数原型声明 */ void main(void) long Value; int n; printf(Please input a number: ); do scanf(%d, if(n 0) printf(Data error! ); while(n 0); /* 如果输入如果输入n0,打印提示并重新输入打印提示并重新输入 */ Value = f(n); /* 调用函数调用函数 */ printf(f(%d) = %ldn,n,Value); 【练习题练习题】要求能够输出要求能够输出斐波那契数列斐波那契数列第第n个数是什么个数是什么， 斐波那契数列定义为：斐波那契数列定义为： 00 11 1)2()1( )( n n nnfnf nf /* 函数名：函数名：f */ /* 功功 能：递归求斐波那契数列能：递归求斐波那契数列 */ /* 参参 数：数：n(整型整型) */ /* 返回值：项序为返回值：项序为n的递归求斐波那契数列值的递归求斐波那契数列值(长整型长整型) */ long f(int n) long y; if(n = 0) y = 0; else if(n = 1) y = 1;