函数的嵌套调用和递归调用.ppt

函数的嵌套调用 C语言中 所有函数的定义都是互相平行和独立的 一个函数的定义不能包含另一个函数的定义 即不允许函数的嵌套定义 但函数的调用可以通过一个函数来调用另一个函数来实现 这就形成了函数的嵌套调用 下面是一个两层嵌套的例子 例7 9 利用公式 e 1 1 1 1 2 1 3 1 4 近似计算自然数e 算法按两层进行 函数fac v 计算1 m m 1 2 3 n 函数cai e 计算整个公式右边之和 作为e的近似值 函数cai e 调用函数fac v 以获得1 m 的值 而主函数则调用cai c得到e的近似值 函数的嵌套调用 includemain doublecai e int intn printf 请输入一个正整数 scanf d n printf 自然数e的近似值为 lf n cai e n doublecai e intn doublefac v int doublee 1 0 while n e fac v n return e doublefac v intm doublev 1 0 while m v m return v 函数的嵌套调用 整个程序执行的流程如图所示 main 函数 调用cai e n 结束 cai e n 函数 调用fac v m return语句 fac v m 函数 return语句 函数的递归调用 函数的递归调用是指一个函数直接或间接地调用了该函数本身 它有两种形式 直接递归调用 间接递归调用1 递归的形式 1 直接递归 例7 10 下面函数sum 计算整数和 1 2 3 4 n longsum intn if n 1 return 1 return sum n 1 n 函数的递归调用 2 间接递归上面的sum 函数改写成两个函数acc 和add 来共同实现这个计算 longacc intn longadd int 函数说明 if n 1 return 1 return add n longadd intn longacc int 函数说明 return acc n 1 n 在函数acc 中嵌套调用了函数add 而在函数add 中又来调用函数acc 这样就形成了间接递归调用 函数的递归调用 2 递归的过程从嵌套的角度看 这里包含了一个循环过程 在这个循环过程中函数进行递推的计算或操作 递推过程 从循环的角度看 任何有效的循环都应有循环条件 递归条件 或者说循环结束的出口 递归出口 例6 10 中给出的sum 函数具有以上两个递归函数的必备特征 递推过程 return sum n一1 n 语句计算sum n 1 n 并将它作为函数调用sum n 的返回值 其中函数调用sum n 1 维持循环 直至递归出口 递归出口 if n 1 return 1 语句在n 1时结束递推过程 这里没有sum 函数的调用 并将数值1作为sum 1 的返回值 函数的递归调用 如函数调用sum 5 的递归过程中 如下图所示 sum 5 sum 4 5return15 sum 3 sum 2 3return6 sum 4 sum 3 4return10 递归出口sum 1 1return1 sum 2 sum 1 2return3 求出sum 2 并返回 求出sum 5 并返回 求出sum 3 并返回 求出sum 4 并返回 递推过程 回推迭代过程 图6 3递归函数sum 的调用过程 函数的递归调用 3 递归的算法递归函数s n 具有以下性质 递推关系 s m s m 1 m m 1 2 n 极端情形 s 1 1递推出口是极端情形的程序语言描述 完成了这两点 就完成了递归函数的设计 递归函数sum 也可以写成如下形式 longsum intn if n 1 return sum n一1 十n return 1 函数的递归调用 4 示例 例7 12 编写求两个正整数的最大公约数的函数gcm 分析 以g表示正整数m和n的最大公约数 则 1 g可以整除min m n 和 m n 2 若m n 最大公约数g就是他们本身 用递归来表示 gcm m n 是求得正整数m和n的最大公约数 则递推关系 gcm m n gcm min m n m n 极端情形 若m n 最大公约数gcm m n 就是他们本身 函数的递归调用 程序表示 unsignedgcm unsignedm unsignedn if m n returnm if m n return gcm m n n elsereturn gcm n m m 例7 13 汉诺塔问题 有三根柱子编号为1 2 3 其中1号柱上有若干个大小不等的盘子 大的在下 小的在上 要求将柱1上的盘子全部移到柱3上 在移动的过程中可以借助于2号柱 但一次只能移动一个盘子 且在移动过程中三根柱子上的盘子始终保持大盘在下 小盘在上的秩序 编写函数完成 并输出其移动的步骤 函数的递归调用 123 分析 可以设计函数hanoi n x y z 用来把柱x上的n个盘子借助于y柱的帮助移动到柱z上 这个问题用递归表示为 极端情形 当n 1时 直接把x柱上的一个盘子移到z柱上 递推关系 当n 1时 把问题分成三个步骤 1 调用hanoi n 1 x z y 是先将x柱上的n 1个盘子移到y柱 2 直接将x柱上的最后一个大盘子移到z柱 3 调用hanoi n 1 y x z 最后将y柱上的n 1个盘子移到z柱只要n不为1 就一直递归下去 直到极端情形的出口 函数的递归调用 程序表示 voidhanoi intn intx inty intz if n 1 printf Takethedishto dfrom d n z x else hanoi n 1 x z y printf Takethedishto dfrom d