"必要"命令式语言中递归的使用 [英] "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:
- 树遍历
- 图表
- Lexing / Parsing
- 排序
- Tree traversal
- Graphs
- Lexing/Parsing
- Sorting
这篇关于"必要"命令式语言中递归的使用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
