-5

我在思考递归算法的真正目的是什么。我们都知道递归算法在某些方面是紧凑且易于理解的。然而,递归的最大缺点是递归算法在运行时需要大量的系统资源。这导致递归算法只能在非常“简单的数据”上运行的结果(我不确定我是否使用了正确的词)。

例如:虽然我编写了一个算法来使用递归算法计算某个矩阵的格路径数。该算法适用于较小的矩阵大小,但在处理大于 20 的矩阵大小时,计算机需要很长时间才能完成任务。所以我必须用正常的方法重写我的算法。

谁能为我解释使用递归算法的目的?因为它对系统资源的使用不是很有效,并且可以通过常规方法完全重写(我知道有时可能很难重写递归算法)。

4

1 回答 1

3

其实在这种情况下,一个人的垃圾就是另一个人的宝物。但是作为备份,让我们考虑一下您关于“大量系统资源”的说法:忽略缓存和流水线的问题,递归算法“隐形”使用的资源是用于进行递归调用的系统堆栈空间:当前指令指针被推送在堆栈上以及递归函数的所有参数。加上递归过程的局部变量是在堆栈上创建的,尽管在任何函数中都是这种情况,但是局部变量占用的内存是递归深度的乘积。尽管如此,这并不一定意味着“巨大”。

递归方法的优点(除了你提到的那些)是......等待它......您可以将系统堆栈用作另一种数据结构。考虑一个探索二叉树的递归算法:通过传递节点递归函数的参数,您实际上是在维护一个数据结构(即堆栈),您需要以非递归方法显式维护它,不同之处在于在递归函数中您不必实际声明并明确维护您的堆栈。因此,唯一额外的“浪费”资源是堆栈帧中需要的任何其他内容,加上堆栈上指令指针的大小*递归深度。对于通过不必声明显式数据结构来存储节点指针而变得更简单的易于理解的算法,这是一个很小的代价。

请记住,对于许多递归函数,递归方法不涉及实际递归:如果递归调用是递归函数中的最后一次调用,并且递归调用的结果由调用函数本身返回,则尾调用优化(在许多编译器上可用)将生成非递归代码。

于 2013-03-27T18:04:54.323 回答