函数的递归调用.ppt

6 6函数的递归调用 章节回顾 1 以下正确的函数定义形式为 A doublefun 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程序中 函数的返回值的类型由 A return语句中的表达式的类型决定B 调用该函数时的调用函数决定C 调用该函数时由系统临时决定D 在定义该函数时由函数的类型决定 A B B D 主要内容 一 引入新问题 二 函数递归概述 三 汉诺塔问题 四 课堂练习 五 课程小结 一 引入新问题 五位学生坐成一排 学生之间不知道相互的年龄 老师问最后一名学生 即第5名学生 她和她前面这一排学生的年龄总和是多少 思考问题 1 2 3 4 5 递归公式 二 函数递归概述 1 递归的定义 调用一个函数时直接或间接调用自身 称之为函数的递归 2 一个问题能够成为递归必须具备的条件是 3 程序中的递归方式 直接递归调用 函数直接调用本身间接递归调用 函数间接调用本身 后一部分与原始问题类似 后一部分是原始问题的简化 说明C语言对递归函数的自调用次数没有限制必须有递归结束条件 intf x intx inty z z f y return 2 z 直接调用 间接调用 intf1 x intx inty z z f2 y return 2 z intf2 t intt inta c c f1 a return 3 c 用C语言解决上述思考题 9岁 8岁 10岁 9岁 10岁 totalAge 1 myAge voidmain intm printf inputthestudent snumber scanf d inttotalAge intn inttotal myAge printf inputtotalnumber d n n printf pleaseinputthe dstudent sage n scanf d 三 汉诺塔问题 一个古典的数学问题 古代有一个梵塔 塔内有3个座A B C 开始时A座上有64个盘子 盘子大小不等 大的在下 小的在上 有一个老和尚想把这64个盘子从A座移动到C座 每次只允许移动一个盘 且在移动过程中 在每个座上都始终保持大盘在下 小盘在上 在移动过程中可以利用B座 写出移动步骤 A n个盘子 动画演示 分析3个盘子的情况 1 将A座上2个盘子移到B座 借助C 2 将A座上1个盘子移到C座 3 将B座上2个盘子移到C座 借助A 其中第2步可以直接实现 第1 3步还需要递归分解 递归分解 第1步 将A座上2个盘子移到B座 借助C 分解为 1 1将A上一个盘子从A移到C 1 2将A上一个盘子从A移到B 1 3将C上一个盘子从C移到B 第3步 将B座上2个盘子移到C座 借助A 分解为 3 1将B上一个盘子从B移到A 3 2将B上一个盘子从B移到C 3 3将A上一个盘子从A移到C 将以上综合起来 可得到移动3个盘子的步骤为 A C A B C B A C B A B C A C 共经历7 23 1 步 可以推知 移动n个盘子需要经历2n 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步 对用关系是 a A b C c B 对第3步 对用关系是 a B b A c C 因此 可以将上面的3个步骤分成两类操作 将n 1个盘子从一个座移到另一个座上 n 1 将1个盘子从一个座移到另一个座上 分别用两个函数来实现这两类操作 hanoi n a b c 表示 将n个盘子从a座借助b座移到c座 a b c对应不同情况的A B C 将n个盘子从A座移到C座 可以分解为3个步骤 算法分析 汉诺塔 includevoidhanoi intn chara charb charc if n 1 hanoi n 1 a c b printf c c n a c hanoi n 1 b a c voidmain intn printf Inputthenumberofdiskes n scanf d 源程序 hanoi n a b c 表示n个盘子从a塔借助于b塔 空 移至c塔 调用时塔用字符常量A B C表示 四 课堂练习 includelongf intn 函数原型声明 voidmain void longValue intn printf Pleaseinputanumber do scanf d 练习题 要求能够输出斐波那契数列第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 五 课程小结 调用一个函数时直接或间接调用自身 称之为函数的递归