(
课件网) 第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 分 解 过 程 求 值 过 程 第三章 递归算法设计实例 经典递归算法实例 兔子出生以后两个月就能生小兔，如果每月生一次恰好生一对小兔（雌雄各一对），且出 ... ...
