“必要"命令式语言中递归的使用 [英] "Necessary" Uses of Recursion in Imperative Languages

问题描述

我最近在几个不同的地方看到类似这样的评论:我在学校学习了递归，但从那时起就再也没有使用过或觉得有必要使用它."(递归似乎是特定程序员群体中书本学习"的一个流行例子.)

I've recently seen in a couple of different places comments along the lines of, "I learned about recursion in school, but have never used it or felt the need for it since then." (Recursion seems to be a popular example of "book learning" amongst a certain group of programmers.)

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

Well, it's true that in imperative languages such as Java and Ruby[1], we generally use iteration and avoid recursion, in part because of the risk of stack overflows, and in part because it's the style most programmers in those languages are used to.

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

Now I know that, strictly speaking, there are no "necessary" uses of recursion in such languages: one can always somehow replace recursion with iteration, no matter how complex things get. By "necessary" here, I'm talking about the following:

你能想出在这样的语言中递归比迭代好得多的任何特定代码示例(出于清晰、效率或其他原因)，你无论如何都使用递归，而转换为迭代将是一个很大的损失?

Can you think of any particular examples of code in such languages where recursion was so much better than iteration (for reasons of clarity, efficiency, or otherwise) that you used recursion anyway, and converting to iteration would have been a big loss?

在答案中多次提到了递归行走树:您对它的特殊使用究竟是什么使递归比使用库定义的迭代器更好，它是否可用?

Recursively walking trees has been mentioned several times in the answers: what was it exactly about your particular use of it that made recursion better than using a library-defined iterator, had it been available?

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

[1]: Yes, I know that these are also object-oriented languages. That's not directly relevant to this question, however.

推荐答案

没有必要"的递归使用.所有递归算法都可以转换为迭代算法.我似乎记得有一个堆栈是必要的，但我想不起来确切的结构.

There are no "necessary" uses of recursion. All recursive algorithms can be converted to iterative ones. I seem to recall a stack being necessary, but I can't recall the exact construction off the top of my head.

实际上，如果您没有对以下内容使用递归(即使在命令式语言中)，您有点生气:

Practically speaking, if you're not using recursion for the following (even in imperative languages) you're a little mad:

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

这篇关于“必要"命令式语言中递归的使用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！