iCAx开思工具箱

标题: 【原创】对递归算法的理解 [打印本页]

作者: 深夜摔键盘 时间: 2004-5-25 15:11
标题: 【原创】对递归算法的理解
递归的思想很重要。有的问题也只有使用递归的思想才可以求解，比如汉诺塔问题。
递归算法的机理：递归是一个函数对自身对自身的调用。一个函数在进程中某处被调用时，分为前置处理，执行指令，后置处理三个过程。

前置处理：系统会首先将寄存器EBP中的数据，返回地址，还有函数需要的参数统统压入系统堆栈保存，然后修改当前程序指针，使其指向函数的入口地址。

执行指令：接下来就开始执行该函数中的各条指令

后置处理：函数执行结束时，系统要将系统堆栈保存的数据弹出，并修改程序指针，使其指向堆栈中弹出的返回地址，继续执行进程中其他指令。

递归程序可以划分为两步骤来实现。
①第一个步骤是前递。只实现自身对自身调用时的前置处理，即不断的进行压栈，所以系统的堆栈的大小随着前递的次数呈线性趋势上升。每一次的前递，都相当于通知系统要完成一个任务，只让系统知道该任务的存在，并不立即让它去执行，而且还要让系统明白要处理这个任务，必须先处理下一个任务。递归可以看作是对一个大任务的进行上下级的分解，下级任务的完成是上级任务完成的保证！
②第二个步骤是回归。当将任务分解到最小单位时，这就满足了回归的条件。此时系统的堆栈相当于一份任务书，程序开始由下而上处理每一层的任务，每完成一个下级任务都要向系统报告，由系统确认该任务完成，然后就将任务规划表中与该任务相关的事宜注销掉。这样直至所有任务处理完毕后，进程中的程序指针会指向由进程第一次递归程序前置处理中压入堆栈的返回地址，去接受新的任务。

通过这个分析过程，可以粗略计算一个递归程序需要多大的系统堆栈。如果发生溢出，则要考虑将递归改成非递归的。非递归也是递归，只是原来有系统处理的堆栈被人工设置的堆栈取代了

作者: dragondancing 时间: 2004-5-26 09:36
谢了~

作者: goodluckwu 时间: 2004-5-27 14:13
可是我记得好像理论上已经证明所有的低轨问题都可以通过循环和判断来解决。只是程序的表达要繁琐很多而已

作者: 深夜摔键盘 时间: 2004-5-27 17:09
尾递归可以用循环来解决

非尾递归只有用栈来消除，实质上就是把系统做的事情由程序员来做了。我觉得只要递归时，只要系统的栈不发生溢出，没必要去改成非递归的。

关于递归，要想细说起来，三天也说不完呀。我不知道大家在做UG开发时，有没有遇到一些算法上的问题。

作者: qbasic 时间: 2004-5-27 18:04
中国人自己的软件数学能力远远超过国外的

作者: 深夜摔键盘 时间: 2004-5-27 18:07
呵呵，分形。

作者: linduyu_y 时间: 2004-5-31 00:17
狂顶

作者: goodluckwu 时间: 2004-5-31 10:32
可是递归的时间复杂度太高了，任何一个海量数据的程序都不会在主要的算法上使用递归的。我记得好像是指数型的。当然，小规模的程序递归是非常方便的。

作者: 深夜摔键盘 时间: 2004-5-31 11:14
递归是一种思考问题的方式。递归不是时间复杂度高，一个递归程序改成非递归，时间上快不了多少。
只有在递归层数太多，发生系统栈溢出时，才考虑改成“非递归”的，这种修改并不能改变问题是递归的性质，仅仅是把原本有系统管理的栈空间由程序员自己来管理了。

递归是一棵树状结构的思想。

作者: kangarooxy 时间: 2004-5-31 11:17

qbasic wrote:
中国人自己的软件数学能力远远超过国外的

给一个“软件数学能力”的定义先，
无论软件能力，还是所谓的数学能力，都不敢苟同

作者: acoka 时间: 2004-5-31 11:54
实际的软件开发里，不推荐用递归，
在不得不用的时候，一般也加个计数器，超过一定次数了话，就break;以免陷入死循环

作者: sanmusanliu 时间: 2004-5-31 21:04
陷入死循环的那不叫递归，那叫只递而不归！
递归是符合树形思想的，凡是递归的问题皆可转化为树的问题！也只有递归才可以创建树的结构。

我测试过，递归深度至少可以到1000层。我测试过一个空递归，可以到10000层的。

欢迎光临 iCAx开思工具箱 (https://t.icax.org/)