递归算法完整版本.pptVIP

*main()现场返回地址保护fn=fact(3)现场返回地址保护y=x=2n=3fact(2)现场返回地址保护y=x=1n=2fact(1)现场返回地址保护y=x=0n=1*fn=y=x=2n=3y=x=1n=2y=x=0n=1根据栈中内容，恢复fact(1)现场根据栈中内容，恢复fact(2)现场根据栈中内容，恢复fact(3)现场根据栈中内容，恢复main()现场返回地址1返回地址1返回地址26返回地址函数调用与返回的过程（1）函数调用

当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，

需先完成三项任务：将返回地址、所有实参等信息传递给被调用函数保存；为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。函数调用与返回的过程（2）函数返回

从被调用函数返回调用函数之前，应该完成下列三项任务：保存被调函数的计算结果；释放被调函数保存局部变量的数据区；依照被调函数保存的返回地址将控制转移到调用函数。递归算法的执行过程是不断地自调用，直到到达递归出口才结束自调用过程；到达递归出口后，递归算法开始按最后调用的过程最先返回的次序返回；返回到最外层的调用语句时递归算法执行过程结束。1、递归的概念2、递归算法的设计方法3、递归算法的执行过程4、递归算法的效率分析5、递归算法的非递归化处理4、递归算法的效率分析Hanoi塔时间复杂度?递归算法的效率分析求第n项斐波那契数列的递归函数如下：longFib(intn){if(n==1)return1;if(n==2)return1;returnFib(n-1)+Fib(n-2);}Fib(5)Fib(4)Fib(3)Fib(3)Fib(2)Fib(2)Fib(1)Fib(2)Fib(1)我用这个函数计算Fib(60)竟然用了2538毫秒!求第n项斐波那契数列的非递归算法longFib(intn){if(n==1)return1;if(n==2)return1;longf1,f2,f3;f1=0,f2=1;for(inti=3;i=n;i++){f3=f2+f1;f1=f2,f2=f3;}returnf3;}我用这个函数计算Fib(60)用了不到1毫秒!上述循环方式的计算斐波那契数列的函数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、递归算法的非递归化处理对于某些复杂问题(例如hanio塔问题)，递归算法是一种自然且合乎逻辑的解决问题的方式，但是递归算法的执行效率通常比较差。因此，在求解某些问题时，常采用递归算法来分析问题，用非递归算法来求解问题；另外，有些程序设计语言不支持递归，这就需要把递归算法转换为非递归算法。采用迭代算法尾递归的消除利用栈消除任何递归如果一个递归过程或递归函数中递归调用语句是最后一条执行语句,则称这种递归调用为尾递归。比较常用的递归形式采用迭代算法longFact2(intn){∥用迭代算法求n!x=1;for(i=1;i=n;i++)x*=i;returnx;}∥Fact2递归从顶到底n!(n-1)!