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

计算机科学系陈垚 1 张福祥主编辽宁大学出版社 C语言程序设计 计算机科学系陈垚 2 我们先看这样一个例子 说有一只调皮的小猴子 摘了一堆水果 第一天吃了水果的一半 又多吃了一个 第二天吃了剩下水果的一半 又多吃了一个 依次类推 到第十天 发现只剩下了1个水果 请问这只猴子到底摘了多少个水果 计算机科学系陈垚 3 一 函数递归的特点 5 4函数递归调用 1 定义 调用一个函数时直接或间接调用自身 称之为函数的递归 2 一个问题能够成为递归必须具备的条件是 许多数学函数都是用递归的形式定义的 计算机科学系陈垚 4 1 直接递归调用 函数直接调用本身 二 程序中的递归方式 2 间接递归调用 函数间接调用本身 计算机科学系陈垚 5 说明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 计算机科学系陈垚 6 思考如下问题 例1 有5个人坐在一起 问第5个人多少岁 他说比第4个人大2岁 问第4个人岁数 他说比第3个人大2岁 问第3个人 又说比第2个大2岁 问第2个人 说比第1个人大2岁 最后问第1个人 他说他10岁 请问第5个人多大 比她大2岁 比她大2岁 比她大2岁 比她大2岁 我10岁 计算机科学系陈垚 7 age 5 16 2 18 age 4 14 2 16 age 3 12 2 14 age 2 10 2 12 设age表示年龄 则有如下 age 5 age 4 2 age 4 age 3 2 age 3 age 2 2 age 2 age 1 2 age 1 10 计算机科学系陈垚 8 main printf d age 5 age 5 计算机科学系陈垚 9 例2 汉诺塔 Hanoi 问题 问题 将A塔上n个盘子移至C 借助于B 移动时 保证三个塔始终是大盘在下 小盘在上 并且每次只能移动一个盘子 A n个盘子 计算机科学系陈垚 10 必须用递归方式解决 1 先将A塔n 1个盘子借助于C移至B上 2 将A上剩下的一个移至C上 3 将B上n 1个盘子借助于A移至C上 可以看到 1 3 为同一问题 都为n 1个盘子借助于一个空塔移至另一塔上 计算机科学系陈垚 11 例Hanoi问题 计算机科学系陈垚 12 voidmove chargetone charputone printf c c n getone putone voidhanoi intn charA charB charC if n 1 move A C else hanoi n 1 A C B move A C hanoi n 1 B A C main intn scanf d 程序如下 计算机科学系陈垚 13 inputthenumberofdiskes 3 Thesteptomoving3diskes A CA BC BA CB AB CA C 运行情况如下 计算机科学系陈垚 14 计算机科学系陈垚 15 move getone putone 表示从getone塔移一个盘子至putone塔 hanoi n one two three 表示n个盘子从one塔借助于two塔 空 移至three塔 调用时塔用字符常量 A B C 表示 在程序中有两个函数 计算机科学系陈垚 16 小结 1 函数递归的定义 2 函数递归的特点 3 函数递归调用的方式 本节课主要介绍的内容 计算机科学系陈垚 17 上机作业 说有一只调皮的小猴子 摘