资源简介

(共17张PPT)
第3课 递归算法
目 录
1
递归算法原理
Principle of recursive algorithm
2
递归算法设计与分析
Recursive algorithm design
3
递归算法设计实例
Recursive algorithm design example
4
总结
Summary of recursive algorithm
第一章
递归算法原理
游戏引入：比比谁算的快
游戏规则：
1、让5位同学排成一队，从第一位同学开始，依次按顺序，每位同学给出一个关于自己身高的提示。
2：第一位同学说比第二位同学高2厘米；第二位同学说比第三位同学高2厘米；第三位同学说比第四位同学高2厘米；第四位同学说比第五位同学高2厘米；第五位同学说他170厘米。
请问这5位同学的身高分别是多少？比一比，哪个小组算的更快，并派小组代表说说你们小组是怎么算出来的。
游戏启发
第5位同学的身高。
解决该问题的出发点和已知条件分别是什么
H5=170cm，H4=H5+2，H3=H4+2，H2=H3+2，H1=H2+2。
前后相邻两人在身高上有什么样的数量关系 最好用数学关系式表示出来。
function (求当前同学身高)
{
if(是第五位同学)
身高是170cm；
else 身高=后一位同学+2cm；
}
把刚刚求解每位同学身高的问题，从自定义函数的角度用伪码来描述呢？
游戏启发
回到刚刚求身高的问题，我们发现由求第1个人身高的问题转化为求第2个人身高的问题，最后到求第5个人身高的问题，该阶段为递推阶段。从第5个人的已知身高推算出第4个人的身高，一直到推算出第1个人的身高的阶段为返回阶段。递推阶段和返回阶段共同构成递归过程。
利用一个已知数一步步进行推算的方法，就是递归法。
1：问题的初始条件是H(5)=170厘米，终止条件是求到第5位同学就可以不用求了。
2：H(n)和H(n+l)的关系是：H(n)=H(n+1)+2。
假设用n表示第n个人，用函数H(n)表示第n个人的身高，提出问题：
1：递归的初始和终止条件分别是什么
2：H(n)和H(n-l)的关系是什么
原理及特点介绍
定义一个方法时，出现本方法调用本方法的过程，称之为递归。
递归的概念
1.必然有一个边界值
2.使用递归代码往往更加简洁，可读性强。
递归的特点
需要解决的问题可以转化为一个或多个子问题来求解，而这些子问题的求解方法与原问题完全相同，只是在数量规模上不同。
递归调用的次数必须是有限的。
必须有结束递归的条件来终止递归。
递归解决的问题应该满足以下三个条件：
第二章
递归算法设计与分析
递归算法设计
根据前面所讲“满足递归解决问题的条件” ，我们设计递归算法来求刚刚游戏中的身高问题
C++代码实现如下：
int height(int n)
{
if(n==5)
return 170;
else
return height(n+1)+2;
}
比较分析
普通实现方式与递归实现方式比较：
通过比较发现：
递归算法具有一个边界条件n=5，当满足n为5，返回自身
递归算法的返回值有两种情况，满足边界值返回特定值，不满足边界条件，返回自身调用自身的形式
非递归算法没有明确的边界值条件，但利用了for循环，隐式地传达了边界值，i>=时不再相加
非递归算法还建立了数组a，用来记录每位同学的身高
设计结论
从以上过程可以得出：
每递归调用一次，就需进栈一次，最多的进栈元素个数称为递归深度，当n越大，递归深度越深，开辟的栈空间也越大。
每当遇到递归出口或完成本次执行时，需退栈一次，并把当前栈顶保留的值送回相应的参量中进行恢复，当全部执行完毕时，栈应为空。
height(1)
height(2)
height(3)
height(4)
height(5)=170
height(4)=height(5)+2=172
height(3)=height(4)+2=174
height(2)=height(3)+2=176
height(1)=height(2)+2=178
分
解
过
程
求
值
过
程
第三章
递归算法设计实例
经典递归算法实例
兔子出生以后两个月就能生小兔，如果每月生一次恰好生一对小兔（雌雄各一对），且出生的兔子都能成活。试问：由1对小兔开始，一年后有多少对兔子，两年后共有多少对兔子。
问题
在第0月有1对兔子；第一月也只有1对兔子；在第2月这对兔子生了1对小兔，公两对兔子；在第3月，老兔子又生了1对兔子，共3对兔子；在第4个月，老兔子和第2个月出生的兔子各生了一对小兔，共五对兔子；在第5个月，第3个月的3对兔子各生了一对兔子，共8对兔子；在第6个月，第4个月的5对兔子各生了一对兔子，共13对兔子…以此类推
思路
经典递归算法实例
而斐波那契数就是用来描述一组具有兔子总数规律的数列，他具有的特征就是从第3项起，每个数都是前两个数之和。
C++中斐波那契数的实现：
不难得兔子数量和月数之间的关系：
第四章
总结
总结
使用递归首先要满足递归的条件，必须有结束递归的条件来终止递归，并且递归的次数是有限的。
一个正确的递归程序虽然每次调用的是相同的子程序，但它的参量和局部变量均不相同。
因为系统在每一次调用时开辟一组存储单元，用来存放本次调用的返回地址以及被中断的函数的参量值，所以这就保证了重复调用执行时的独立性。
随着调用的不断深入，到达出口时，不再执行递归调用而终止函数的执行。
谢谢观看！

展开更多......

收起↑