ch5模块化程序设计 C语言 《解析C程序设计》.pptVIP

3. 递归形式的与或结点图为 求Jump(3,4) S==0 Jump(S,y) y+1 S!=0 Jump(S-1,y) 2*Jump(S-1,y) S==0 Jump(3,4) 4+1 3!=0 A=Jump(2,4) 2*A 2*20=40 B=Jump(1,4) 2*B 2*10=20 2!=0 C=Jump(0,4) 2*C 2*5=10 1!=0 40 // * 主要功能：青蛙过河 #include stdio.h int Jump(int, int); //声明有被调用函数 int main() { int S=0,y=0,sum=0; //s为河中石柱数,y为荷叶数 scanf(“%d”,S); scanf(“%d”, y); sum = Jump ( S , y ) ; //最多可跳过河的青蛙数 printf(Jump(%d,%d)=%d\n,S,y,sum); return 0; } int Jump ( int r, int z ) { int k=0; if (r==0) k = z + 1; //直接可解结点, k 值为 z + 1 else k=2*Jump(r-1,z);　//要调用Jump( r-1, z ) return k;　 } 练习 将十进制数转换成2进制数输出（递归实现） 十进制与二进制的相互转换 屏幕显示菜单（提示），用户选择： 1： 十 ? 二 2： 二 ? 十 * 云南师范大学 云南师范大学 云南师范大学 云南师范大学 计算机科学与信息技术学院 解敏 xmin7186@ 程序设计导引 2007.9 — 2008.1 云南师范大学 云南师范大学 第5章 模块化程序设计 本章要点 函数的嵌套调用 递归求n! 递归求Fibonacii数列（自学p144） Hanoi塔, 青蛙过河 计算ex（自学p152） 输入年份，输出日历(p153) 练习 函数可以嵌套调用，但不能嵌套定义 main() { ... f1(); ... } f1() { ... f2(); ... f3(); ... } f2() { ... } f3() { ... } f4() { ... f5(); ... } f5() { ... } 求n!（递归实现） 递归法的思想 n! 递归 调用与返回 n 程序实现 “与结点” 表达递归 fact() 递归与递推 递推：从已知的初始条件出发，由递推公式逐次求所需要的 如求 3！　　初始条件 ： 递归：从所求的未知项出发逐次调用本身的求解过程(递归函数)，直到递归的边界（即初始条件） 递归算法比较符合人的思维方式，逻辑性强，可将问题描述得简单扼要，具有良好的可读性，易于理解 递归的常见应用：有哪些信誉好的足球投注网站，排序，任务分析 递归通常适合于一些可以分成许多更小问题的问题。如果这些“更小”问题差异很大时，迭代(递推)可能比递归更有用 直接或间接调用自己的函数 思路 A: 能够直接处理的部分 B: 暂时不能直接处理，但与原问题相似（递归调用），且规模缩小（参数变化趋向于能够直接处理的部分） 递归函数 与结点 ：表达递归算法 A 的最终取值为 C 结点的值，但为了求得 C 的值，得先求出 B 结点的值, C 是B 的函数。 与结点有多个相关联的点 A B C A B ... D C 求“n ! “ 的与或图 求3! A B C fact(n) n==1 1 D E n*fact(n-1) fact(n-1) n1 A B E fact(3) n==1 31 fact(2) 21 3*fact(2) C fact(1) 1 2*fact(1) D 2*1=2 3*2=6 6 #includestdio.h　//递归法求n! int fact(int n); //函数说明 int main() //主函数 { int n; 　 scanf(“%d”,n); 　 printf(“\t%d!=%d\n”,n, fact(n) );　//函数调用 　 return 0; } int fact(int n) 　//递归法求n! { int result; 　 if(n==1 || n==0) result=1; 　//递归出口 　 else result=n* fact(n-1) ; 　//递归调用 　 return result; //返回主调函数 } 递归调用与返回 真 假 1==1 result=1 返回result 函数fa