命令式语言中"递归"的"必要"用法

Question

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

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

现在我知道,严格地说,在这样的语言中没有"必要的"递归用法:无论事情多么复杂,都可以用迭代替换递归.在这里"必要",我说的是以下内容:

您是否可以想到这些语言中代码的任何特定示例,其中递归比迭代(为了清晰,效率或其他原因)更好,无论如何您使用递归,转换为迭代会是一个很大的损失？

在答案中已经多次提到了递归行走的树:如果它可用,那么它使用它的确切原因是什么使得递归比使用库定义的迭代器更好？

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

Answer 1

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

实际上,如果你没有使用递归来表示以下内容(即使是在命令式语言中),你会有点生气:

Answer 2

例如,当您走任何类型的树结构时

另外,每个调用对象成员的toString()的toString()方法也可以被认为是递归的.所有对象序列化算法都是递归的.

Answer 3

在我的工作中,递归很少用于任何算法.使用简单的循环可以更加可读地(并且有效地)解决诸如阶乘等问题.当它出现时,通常是因为您正在处理一些本质上递归的数据.例如,可以递归地处理树结构上的节点.

例如,如果您要编写一个程序来遍历二叉树的节点,您可以编写一个处理一个节点的函数,并调用它来处理每个节点的子节点.这比在环绕每个子节点时尝试维护所有不同状态更有效.

Answer 4

最着名的例子可能是CAR Hoare开发的quicksort算法.

另一个例子是遍历目录树以查找文件.

Answer 5

在我看来，当数据结构也是递归的时，递归算法是很自然的选择。

def traverse(node, function):
    function(this)
    for each childnode in children:
        traverse(childnode, function)

我不明白为什么我想迭代地写它。