算法设计与分析课件 07 递归算法_第1页
算法设计与分析课件 07 递归算法_第2页
算法设计与分析课件 07 递归算法_第3页
算法设计与分析课件 07 递归算法_第4页
算法设计与分析课件 07 递归算法_第5页
已阅读5页，还剩4页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

算法设计与分析本节要点CONTENTS递归算法递归算法递归必须要求有结束条件，不然就会陷入无限递归的状态，永远无法结束调用。递归调用就是函数内部调用自身的过程。实例1（P5739）：求解n的阶乘n!，n!=1×2×3⋯×n。解析：n的阶乘等于n×(n-1)!，可以采用递归算法，只需对特殊情况判断，作为递归结束条件。直接返回1，其它情况递归调用。设计递归函数三部曲：（1）函数名和参数（2）递归的结束条件（3）自调用3递归算法递归原理4递归：递推和回归。递推是将原问题不断分解成子问题，直到达到结束条件，返回最近子问题的解；然后逆向逐一回归，最终到达递推开始的原问题，返回原问题的解。递归算法5递归算法阶乘是典型的递归调用问题。求解5的阶乘递推、回归过程如下图所示。递归与栈递归需要调用栈，系统自动调用。6递归需要的栈空间等于递归树的深度。递归算法75的阶乘递推（进栈）过程的形象表达如下图所示。递归算法85的阶乘回归（出栈）过程的形象表达如下图所示。递归算法9递归算法

求解n的阶乘需要n次乘法，时间复杂度为O(n)，递归过程中需要使用的栈空间，其空间复杂度也为O(n)。注意：递归算法中，每一次递推都需要一个栈空间保存调用记录

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论