- 1、本文档共73页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
1、递归的概念 2、递归算法的设计方法 3、递归算法的执行过程 4、递归算法的效率分析 5、递归算法的非递归化处理 斐波那契数列Fib(n)的递归定义是: 求第n项斐波那契数列的递归函数如下: long Fib(int n) { if(n == 0 || n == 1) return n; //递归出口 else return Fib(n-1) + Fib(n-2); //递归调用 } 用归纳法可以证明求Fib(n)的递归调用次数等于2n-1;计算斐波那契数列的递归函数Fib(n)的时间复杂度为O(2n)。计算斐波那契数列Fib(n)问题,我们也可根据公式写出循环方式求解的函数如下: Fib(5)的递归调用树 上述循环方式的计算斐波那契数列的函数Fib2(n)的时间复杂度为O(n)。对比循环结构的Fib2(n)和递归结构的Fib(n)可发现: 循环结构的Fib2(n)算法在计算第n项的斐波那契数列时保存了当前已经计算得到的第n-1项和第n-2项的斐波那契数列,因此其时间复杂度为O(n); 而递归结构的Fib(n)算法在计算第n项的斐波那契数列时,必须首先计算第n-1项和第n-2项的斐波那契数列,而某次递归计算得出的斐波那契数列,如Fib(n-1)、Fib(n-2)等无法保存,下一次要用到时还需要重新递归计算,因此其时间复杂度为O(2n) 。 优点:----递归过程结构清晰 ----程序易读 ----正确性容易证明 缺点:----时间效率低 ----空间开销大,问题规模扩大时,噩 梦来临。 ----算法不容易优化 对于频繁使用的算法,或不具备递归功能的程序设计语言,需要把递归算法转换为非递归算法。 1、递归的概念 2、递归算法的设计方法 3、递归算法的执行过程 4、递归算法的效率分析 5、递归算法的非递归化处理 采用迭代算法 尾递归的消除 利用栈消除任何递归 如果一个递归过程或递归函数中递归调用语句是最后一条执行语句,则称这种递归调用为尾递归。比较常用的递归形式 采用迭代算法 long Fact2(int n) {∥用迭代算法求n! x=1; for(i=1;i=n;i++) x*=i; return x; }∥Fact2 递归从顶到底 n! (n-1)! (n-2)! . . . 2! 1! 0! 迭代从底到顶 将递归转换成迭代 void Output1(LinkedList L) {∥顺序输出单链表结点数据的递归算法 if(L) { printf(L-data); ∥输出结点的值 Output1(L=L-next); ∥尾递归调用 } }∥Output1 使用跳转语句 void Output2(LinkedList L) {∥顺序输出单链表结点数据的非递归算法一 p=L; ∥设局部变量p=L Lbl: ∥在第一个可执行语句前设标号 if(p){printf(p-data);∥输出结点的值 p=p-next; ∥修改变量值 goto Lb1; ∥转到第一个可执行语句 } }∥ Output2 使用循环语句改造 void Output3(LinkedList L) {∥顺序输出单链表结点数据的非递归算法二 p=L; ∥设局部变量p=L while(p) {printf(p-data); ∥输出结点的值 p=p-next; ∥向里一层修改变量值 } }∥ Output3 因为堆栈的后进先出特点正好和递归函数的运行特点相吻合。所以原理上讲,任何递归都可以转换为非递归的算法。 利用栈可以将任何递归函数转换成非递归的形式,其步骤大致如下: 入栈处理 设一个工作栈代替递归函数中的栈,栈中每个记录包括函数的所有参数:函数名、局部变量和返回地址。 所有递归调用语句处,改写成把形参、局部变量和返回地址入栈的语句。 修改确定本次递归调用时的实际参数之新值。 转到函数的第一个语句。 (转下页) (接上页) 退栈处理 若栈空,算法结束,
文档评论(0)