第八章 递归.pptVIP

第八章 递 归 8.1 递归的概念 8.2 基本递归过程 8.3 递归过程的实现 定义：如果一个对象部分地包含它自己，或者利用自己定义自己的方式来定义或描述，则称这个对象是递归的（递归定义）；如果一个过程直接或间接地调用自己，则称这个过程是一个递归过程。（递归算法） 组成：递归调用部分、递归终止条件 递归的简单例子 xn=x*x*…*x*x （n个x连乘） xn+1=xn * x S(n)=1+2+3+…+(n-1)+n S(n+1)=S(n)+(n+1) 以下三种情况适于用递归求解问题： 问题的定义是递归的； 问题所涉及的数据结构是递归的； 问题的解法满足递归的性质。 1、问题的定义是递归的 阶乘函数、幂函数和斐波那契数列。 [例1] 阶乘函数的定义 求解阶乘函数的递归过程 long Factorial(long n) { if (n==0) return 1; //递归终止条件 else return n * Factorial(n-1); }　　　　　　　　　　 //递归调用过程 2、问题所涉及的数据结构是递归的 [例1]　单链表节点类的递归定义 [例2]　单链表的递归定义 head=NULL 头指针为head的单链表的递归定义： （1）head指向一个空结点的数据结构是一个单链表； （2）head指向一个非空结点，该结点的指针域指向一个单链表，这样的数据结构是一个单链表。 在头指针为p的单链表中有哪些信誉好的足球投注网站data值为item的结点 　template class T 　void Search（Node T *p，T item） 　{ 　　if（p = = NULL） 　　{cerr “Can not find the item .” ；return ；} 　　if （p-data = = item） 　　Dealwith（p）； 　// 通过Dealwith函数对　　　　　　　　　　　　　　　//该节点进行一定的处理 　　else 　　　Search（p-next，item）； 　} 3、问题的解法满足递归的性质 递归求解的基本思想（分治策略）：　 对于一个比较复杂的问题，如果能够把它分解为若干个相对简单的、而且解法相同或类似的子问题，那么当这些子问题获得解决时，原问题就获得解决－－分治策略。 子问题无需分解就可以直接解决时，停止分解，直接求解该子问题－－递归结束条件。 [例1] 二叉树的遍历：　 　归纳基础　　?　递归出口　 归纳步骤　 ? 递归调用 [例3] 求文件中的最大元-最小元问题 [例4] 汉诺塔(Tower of Hanoi)问题 … … 8.2　基本递归过程 递归过程在实现时，发生递归调用：分为外部调用和内部调用。 调用方式不同，返回的方式也不相同。 递归过程与实现的基本思想 高级语言的编译程序中，函数调用是通过堆栈实现的； 递归函数调用是一种特殊的函数调用形式，因此也可以通过堆栈实现。 函数调用方式： 递归函数调用方式： 函数调用时执行入栈操作保存本次递归调用对应的信息 函数返回时执行出栈操作恢复上次递归调用对应的信息 一次递归调用所需要的信息表示为一个工作记录：　　　　　　 　返回地址 　参　数 （函数名、引用参数与实参等） 　局部变量 递归工作栈 long Factorial ( long n ) { if ( n == 0 ) return 1; else return n * Factorial (n-1); RetLoc2 } 　　　　 void main ( ) { 　　　　int Result; 　　　　Result = Factorial (4); RetLoc1 } 递归算法的优点： 递归过程结构清晰 递归程序易写、易读 正确性证明相对容易 递归算法的不足： 运行效率低，原因： 函数调用开销（时间、空间）大 会出现重复计算 计算斐波那契数列的非递归函数 long CalFib（long n） { if（n = 1） return n； else { long f0 = 0，f1 = 1，f = 0； for（ int i = 2；i = n；i++） {