algorithm - 在递归算法中避免堆栈溢出的通常做法是什么？

由于潜在的堆栈溢出问题，我曾经认为迭代算法总是优于递归算法，只要不介意编码方面的额外努力。因此，如果我要构建一个 util 函数以反复使用，我应该始终使用迭代。这个逻辑正确吗？或者是否有任何标准技巧可以避免递归中的堆栈溢出，即使对于非常大的 N？仍然假设数据结构本身不会太大而无法放入 RAM。

标签： algorithmrecursion

基本上你是对的，常见的编译器迭代在内存消耗和性能方面都优越，但不要忘记有些语言通常专注于函数式编程和/或针对递归进行优化的人工智能，而递归则更优越......

无论如何，如果可以的话，出于您提到的原因，我总是使用迭代。然而，递归方法通常比迭代方法更简单，并且转换为迭代所需的编码量太多......在这种情况下，您可以执行以下操作：

限制堆/堆栈垃圾

只需尽可能多地摆脱操作数、返回值和局部变量，因为每次递归都会对其进行复制/实例...

您可以将static变量用于局部变量，甚至可以将全局变量用于操作数，但请注意不要使用它来破坏功能。

你不会相信有多少次我看到将数组作为操作数传递给递归......
限制递归

如果你有多重分割递归（一个递归层有超过1个递归调用），那么你可以有一些内部全局计数器当前有多少递归处于活动状态......如果你达到某个阈值，请不要再使用递归调用......而是将它们安排到一些称为优先级队列的全局数组/列表 IIRC 中，一旦所有挂起的递归停止处理此队列，直到其为空。然而，这种方法并不总是适用。这种方法的好例子是：Flood Fill，网格 A* 路径查找，...
增加堆/堆栈大小

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

我相信还有更多的技术，但这些是我使用的......