《递归算法分析》-课件设计(公开).ppt

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 因为堆栈的后进先出特点正好和递归函数的运行特点相吻合。所以原理上讲，任何递归都可以转换为非递归的算法。 利用栈可以将任何递归函数转换成非递归的形式，其步骤大致如下： 入栈处理 设一个工作栈代替递归函数中的栈，栈中每个记录包括函数的所有参数：函数名、局部变量和返回地址。 所有递归调用语句处，改写成把形参、局部变量和返回地址入栈的语句。 修改确定本次递归调用时的实际参数之新值。 转到函数的第一个语句。 （转下页） （接上页） 退栈处理 若栈空，算法结束，