哈工大-7函数讲解.ppt

汉诺塔（Hanoi）问题 设计2个函数： 将n个圆盘借助C从A移到B 将一个圆盘从A移到B A C B 将n-1个圆盘从A移到C 将n号圆盘从A移到B 将n-1个圆盘从C移到B 汉诺塔（Hanoi）问题 递归方法的基本原理 将复杂问题逐步化简，最终转化为一个最简单的问题 最简单问题的解决就意味着整个问题的解决 汉诺塔（Hanoi）问题 7.4.2递归函数 long fact(int n) {  if (n 0) return -1; else if (n == 0 || n == 1) return 1; else  return n * fact(n-1); } 【例7.6】计算n！= n *(n-1)*(n-2)*……*1 函数直接或间接调用自己，称为递归调用（Recursive Call） 7.4.2递归函数 unsigned long fact(unsigned int n) {  if (n == 0 || n == 1)  return 1; else  return n * fact(n-1); } 基线情况(base case) 一般情况(general case) 无需考虑n0了 【例7.6】计算n！= n *(n-1)*(n-2)*……*1 7.4.2递归函数 递归调用应该能够在有限次数内终止递归 递归调用若不加以限制，将无限循环调用 必须在函数内部加控制语句，仅当满足一定条件时，递归终止，称为条件递归 任何一个递归调用程序必须包括两部分 递归循环继续的过程 递归调用结束的过程 if (递归终止条件成立) return 递归公式的初值; else return 递归函数调用返回的结果值; n!=n×(n-1)! (n-1)!=(n-1)×(n-2)! (n-2)! .. (n-3)! 5! : 4!=4×3! 3!=3×2! 2!=2×1! 1!=1 回推过程 递推过程 每个递归函数必须至少有一个基线条件 一般情况必须最终能简化为基线条件 递归层数太多易 导致栈空间溢出 后果很严重，程序被异常中止 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 main fact(5) fact(4) fact(3) fact(2) fact(1) 递归与迭代 用迭代（即循环）方法编写的阶乘函数 unsigned long Fact(unsigned int n) { unsigned long result = 1; unsigned int i; for (i = 1; i = n; i++) result *= i; return result; } 递归程序遵循了数学中对阶乘的定义 因此递归方法编写程序具有更清晰、可读性更好的优点 递归与迭代 1，1，2，3，5，8，...... long Fib(int n) { long f; if (n == 0) f = 0; else if (n == 1) f = 1; else f = Fib(n-1) + Fib(n-2); return f; } 1 5 4 3 2 3 2 2 1 1 0 1 0 1 0 计算fib(5)共需15次fib调用 【例7.7】计算Fibonacci数列 从第三项开始,每一项都等于前两项之和 递归与迭代 优点： 从编程角度来看，比较直观、精炼，逻辑清楚 符合人的思维习惯，逼近数学公式的表示 尤其适合非数值计算领域 hanoi塔，骑士游历、八皇后问题（回溯法） 缺点： 增加了函数调用的开销，每次调用都需要进行参数传递、现场保护等 耗费更多的时间和栈空间 应尽量用迭代形式替代递归形