基本信息

---

下载

文档摘要

---

0-1开课;;5.1什么是递归;何时使用递归;定义是递归的;【例如】计算Fibonacci数列的函数Fib(n)的定义：

n当n=0,1时

Fib(n)=

Fib(n-1)+Fib(n-2)当n1时

;数据结构是递归的;问题的解法是递归的;递归模型;5.2递归调用与实现;函数嵌套调用;;递归过程与递归工作栈;递归调用举例;以power函数为例剖析一个递归调用;5.3递归算法设计;对原问题（即“大问题”）进行分析，找到将“大问题”分解为“小问题”的规律。

基于规律确定递推关系：也就是确定递归体。

确定终止条件，即确定一个特定情况的解，以此作为递归出口。

根据递归模型，将递推关系式和终止条件翻译成代码，设计出求解原问题的递归算法。;递归出口：又叫结束条件或终止条件，即可以直接解决而无需再做递归的条件。

递归体：确定递归求解的递推关系，包含对本算法的递归调用，但每次调用时传递进去的参数较上次调用时传递进去的参数更接近于初始情况。;递归算法一般形式;5.4递归算法性能分析;（1）展开法;例2;（2）主定理;例3设某算法运行时间的递推式描述如下，分析该算法的时间复杂度;例4设某算法运行时间的递推式描述如下，分析该算法的时间复杂度;5.5应用举例;5.5应用举例;;