iCAx开思工具箱

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 25138|回复: 11
打印 上一主题 下一主题

【原创】对递归算法的理解

[复制链接]
跳转到指定楼层
楼主
发表于 2004-5-25 15:11:14 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式

马上注册登录,享用更多网站功能!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
递归的思想很重要。有的问题也只有使用递归的思想才可以求解,比如汉诺塔问题。
递归算法的机理:递归是一个函数对自身对自身的调用。一个函数在进程中某处被调用时,分为前置处理,执行指令,后置处理三个过程。
  
前置处理:系统会首先将寄存器EBP中的数据,返回地址,还有函数需要的参数统统压入系统堆栈保存,然后修改当前程序指针,使其指向函数的入口地址。
  
执行指令:接下来就开始执行该函数中的各条指令
  
后置处理:函数执行结束时,系统要将系统堆栈保存的数据弹出,并修改程序指针,使其指向堆栈中弹出的返回地址,继续执行进程中其他指令。
  
递归程序可以划分为两步骤来实现。
①第一个步骤是前递。只实现自身对自身调用时的前置处理,即不断的进行压栈,所以系统的堆栈的大小随着前递的次数呈线性趋势上升。每一次的前递,都相当于通知系统要完成一个任务,只让系统知道该任务的存在,并不立即让它去执行,而且还要让系统明白要处理这个任务,必须先处理下一个任务。递归可以看作是对一个大任务的进行上下级的分解,下级任务的完成是上级任务完成的保证!
②第二个步骤是回归。当将任务分解到最小单位时,这就满足了回归的条件。此时系统的堆栈相当于一份任务书,程序开始由下而上处理每一层的任务,每完成一个下级任务都要向系统报告,由系统确认该任务完成,然后就将任务规划表中与该任务相关的事宜注销掉。这样直至所有任务处理完毕后,进程中的程序指针会指向由进程第一次递归程序前置处理中压入堆栈的返回地址,去接受新的任务。
  
通过这个分析过程,可以粗略计算一个递归程序需要多大的系统堆栈。如果发生溢出,则要考虑将递归改成非递归的。非递归也是递归,只是原来有系统处理的堆栈被人工设置的堆栈取代了
分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
收藏收藏 分享淘帖 支持支持
沙发
发表于 2004-5-26 09:36:44 | 只看该作者

马上注册登录,享用更多网站功能!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
板凳
发表于 2004-5-27 14:13:23 | 只看该作者

马上注册登录,享用更多网站功能!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
地板
 楼主| 发表于 2004-5-27 17:09:54 | 只看该作者

马上注册登录,享用更多网站功能!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
5
发表于 2004-5-27 18:04:36 | 只看该作者

马上注册登录,享用更多网站功能!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

1945932-a-embed.JPG (248.79 KB, 下载次数: 9)

阅读权限: 1

1945932-a-embed.JPG
6
 楼主| 发表于 2004-5-27 18:07:33 | 只看该作者

马上注册登录,享用更多网站功能!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
7
发表于 2004-5-31 00:17:04 | 只看该作者

马上注册登录,享用更多网站功能!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
8
发表于 2004-5-31 10:32:02 | 只看该作者

马上注册登录,享用更多网站功能!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
9
 楼主| 发表于 2004-5-31 11:14:31 | 只看该作者

马上注册登录,享用更多网站功能!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
10
发表于 2004-5-31 11:17:16 | 只看该作者

马上注册登录,享用更多网站功能!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

手板模型制作,在线3D打印服务

QQ|小黑屋|手机版|开思工具箱 CAD工具箱_CAM工具箱  

GMT+8, 2024-12-24 00:38 , Processed in 0.028083 second(s), 7 queries , Gzip On, Redis On.

Powered by Discuz! X3.3

© 2002-2024 www.iCAx.org

快速回复 返回顶部 返回列表