language-agnostic - "Necessary"命令式语言中递归的使用

Question

我最近在几个不同的地方看到了类似这样的评论:“我在学校学到了递归，但从那以后从未使用过它或感觉需要它。” (递归似乎是某些程序员群体中“书本学习”的流行示例。)

确实，在 Java 和 Ruby[1] 等命令式语言中，我们通常使用迭代并避免递归，部分原因是堆栈溢出的风险，部分原因是这是这些语言中大多数程序员的风格已经习惯了。

现在我知道，严格来说，在此类语言中没有“必要”使用递归:无论事情变得多么复杂，人们总是可以以某种方式用迭代代替递归。这里的“必要”是指以下内容:

您能想到此类语言中的任何特定代码示例，其中递归比迭代好得多(出于清晰、效率或其他原因)，您无论如何都使用了递归，并且转换为迭代将是一个巨大的损失？

递归行走树在答案中已经多次提到:您对它的特殊使用到底是什么使递归比使用库定义的迭代器更好，如果它可用的话？

[1]:是的，我知道这些也是面向对象的语言。然而，这与这个问题没有直接关系。

Answer 1

没有“必要”使用递归。所有递归算法都可以转换为迭代算法。我似乎记得有一个堆栈是必要的，但我记不起具体的结构。

实际上，如果您不使用递归来执行以下操作(即使在命令式语言中)，您就会有点生气:

1. 树遍历
2. 图表
3. 词法分析/解析
4. 排序