数据结构与算法java版罗文劼第2章节递归.ppt

文档介绍：在线教务辅导网:配套课件资源请访问在线教务辅导网2019/9/41第2章递归2019/9/42⒈教学内容递归的概念、递归调用的实现原理、递归转换为非递归、汉诺塔问题。⒉教学目的理解递归的特点,会分析什么样的问题适合用递归解决;领会递归调用的执行过程;了解递归的优点、了解递归的缺点。⒊教学重点什么样的问题可以用递归解决、递归实现的方法、递归方法的时空效率。⒋教学难点递归的执行过程,递归转换为非递归。2019/9/43例1:一个人要搬走10块石头,怎么搬呢?例2:计算从1到100的累加和。例3:计算2n。这些定义方式体现了一种逻辑思想,同时又是一种解决问题的方案。递归定义的问题,可以用递归的算法来求解。!=1n=0n*(n-1)!n>0Fib(n)=nn=0,1Fib(n-1)+Fib(n-2)n>=递归是一个过程或函数直接或间接调用自身的一种方法,它可以把一个大型的问题层层转化为一个与原问题相似、但规模较小的问题来求解。数学中阶乘的定义,n的阶乘可以如下表示:再如,斐波那契(i)数列指的是这样一个数列:直接或间接调用自身的程序称为递归程序。递归是一种特殊的嵌套调用,是某个函数调用自己,而不是另外一个函数。这是一种函数直接或者间接调用自身编程技术。2019/9/:需要解决的问题可以化为一个或多个子问题来求解,而这些子问题的求解方法与原来的问题完全相同,只是在数量规模上不同;递归调用的次数必须是有限的;必须有结束递归的条件(边界条件)来终止递归。2019/9/46递归算法的设计一般分为两步:第一步,将规模较大的原问题分解为一个或多个规模较小的而又类似于原问题特性的子问题,既将较大的问题递归地用较小的子问题来描述,解原问题的方法同样可以用来解决子问题;第二步,是确定一个或多个不需要分解、可直接求解的最小子问题。2019/9/472019/9/【算法2-1】中求阶乘的问题,假设程序运行时,n=4,那么程序的执行过程。2019/9/49从上面可以看出,递归调用的过程分为两个阶段:1)递归过程:将原始问题不断转化为规模小了一级的新问题,从求4!变成求3!,变成求2!,最终达到递归终结条件,求1!;2)回溯过程:从已知条件出发,沿递归的逆过程,逐一求值返回,直至递归初始处,完成递归调用。2019/9/410