C语言程序设计课件-国家级精品课程：第9章 函数的高级应用
第9章函数的高级应用 本章内容 递归与递归函数 指向函数的指针 返回指针值的函数 递归问题的提出 “汉诺塔”(Hanoi) 这是一个必须用递归方法才能解决的问题 n=64时， 18,446,744,073,709,551,615次 1844亿亿次 每次1微秒，需要60万年 递归问题的提出 A→C，A→B，C→B， A→C，B→A，B→C，A→C 递归问题的提出 A→C，A→B，C→B， A→C，B→A，B→C，A→C 递归问题的提出 A→C，A→B，C→B， A→C，B→A，B→C，A→C 递归问题的提出 A→C，A→B，C→B， A→C，B→A，B→C，A→C 递归问题的提出 A→C，A→B，C→B， A→C，B→A，B→C，A→C 递归问题的提出 第一步：将问题简化。 假设A杆上只有2个圆盘，即汉诺塔有2层，n＝2。 递归问题的提出 对于一个有 n(n>1)个圆盘的汉诺塔，将n个圆盘分为两部分：上面的 n-1 个圆盘和最下面的n号圆盘。将“上面的n-1个圆盘”看成一个整体。 将 n-1个盘子从一根木桩移到另一根木桩上 将1个盘子从一根木桩移到另一根木桩上 递归问题的提出 将 n个盘子从一根木桩移到另一根木桩上 问题分解为： 将 n-1个盘子从一根木桩上移到另一根木桩上 将1个盘子从一根木桩移到另一根木桩上 设计一个函数，入口参数为n ： 将 n个盘子从一根木桩移到另一根木桩上 将 n-1个盘子从一根木桩上移到另一根木桩上 也要调用这个函数来实现 出现了函数调用自己的问题 递归调用(Recursive Call) 递归(Recursion)函数 递归函数 函数直接或间接调用自己 直接调用方式： int f(x) { int y,z; …. z=f(x); …… } 例9.1求整数n的阶乘n！ 计算n！= n *(n-1)*(n-2)*…*1 迭代法 用递归的方法 例9.1求整数n的阶乘n！ #include main() { int n, i; long result=1; printf("Input n:"); scanf("%d", &n); result = 1; for (i=1; i<=n; i++) result *= i; printf("%d!= %ld", n, result); } 例9.1求整数n的阶乘n！ 例9.1求整数n的阶乘n！ #include long fact(long n); main() { int n; long result; printf("Input n: "); scanf("%d", &n); result = fact(n); if(result==-1) printf("n<0,data error ! \ n"); else printf("%d! = %ld\n", n, result); } 递归调用过程 执行过程： fact(5)=5*fact(4)=120 fact(4)=4*fact(3)=24 fact(3)=3*fact(2)=6 fact(2)=2*fact(1)=2 fact(1)=1 递归函数 递归方法的基本原理 将复杂问题逐步化简，最终转化为一个最简单的问题 最简单问题的解决，就意味着整个问题的解决 递归调用应该能够在有限次数内终止递归 递归调用如果不加以限制，将无数次的循环调用 必须在函数内部加控制语句，只有当满足一定条件时，递归终止 有时将其称为条件递归 递归函数 任何一个递归调用程序必须包括两部分 递归循环继续的过程 递归调用结束的过程 if (递归终止条件成立) return 递归公式的初值; else return 递归函数调用返回的结果值; 递归函数 思考：下面程序有什么问题 阶乘函数的递归实现 unsigned long Fac(unsigned int n) { i
