代码之家 › 专栏 › 技术社区 › Indominus

在递归算法中,避免堆栈溢出的通常做法是什么?[关闭]

recursion algorithm

Indominus · 技术社区 · 7 年前

我曾经认为迭代算法总是优于递归算法,因为潜在的堆栈溢出问题,只要你不介意额外的编码工作。因此,如果我要构建一个反复使用的util函数,我应该始终使用迭代。这逻辑正确吗?或者有什么标准技巧可以避免递归中的堆栈溢出,即使对于非常大的n也是如此?仍然假设数据结构本身不太大,不适合RAM。

1 回复 | 直到 7 年前

Spektre 7 年前

基本上,你说得对,通用编译器的迭代在内存消耗和性能上都是优越的,但是不要忘了,有一些语言通常专注于函数编程和/或人工智能,它们针对递归进行了优化,而使用它们,递归更优越……

不管怎样,如果我可以的话,我总是根据你提到的原因使用迭代。然而,递归方法往往比迭代方法更简单,转换为迭代所需的编码量太大…在这种情况下,您可以执行以下操作:

限制堆/堆垃圾

只需去掉尽可能多的操作数、返回值和局部变量,因为每一个递归都会生成它的副本/实例…

你可以使用 static 局部变量,甚至是操作数的全局变量,但请注意不要使用它破坏功能。

你不会相信我有多少次看到将数组作为操作数传入递归…
极限递归

如果您有多个拆分递归(一个递归层有一个以上的递归调用),那么您可以有一些内部全局计数器,当前有多少个递归处于活动状态… 如果达到某个阈值,则不再使用递归调用…相反,将它们调度到称为优先级队列的全局数组/列表IIRC中,一旦所有挂起的递归停止处理该队列,直到其为空。然而,这种方法并不总是适用的。这种方法的好例子是:洪水填充,网格A*路径查找,…
增加堆/堆栈大小

可执行文件有一个表,告诉操作系统为其部分分配多少内存…所以只需在编译器/linker/ide中找到设置,并将该值设置为合理的大小。

我相信还有更多的技巧,但这些是我使用的…

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

1 年前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

1 年前

b39b332d · 使用C++标准库实现高效间隔存储

1 年前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

1 年前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

1 年前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

1 年前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

1 年前