一个reddit线程提出了一个显然有趣的问题:
尾递归函数可以简单地转换为迭代函数.其他的,可以通过使用显式堆栈进行转换.可每次递归转化为迭代？
帖子中的(计数器？)示例是对:
(define (num-ways x y)
(case ((= x 0) 1)
((= y 0) 1)
(num-ways2 x y) ))
(define (num-ways2 x y)
(+ (num-ways (- x 1) y)
(num-ways x (- y 1))
我最近在几个不同的地方看到过这样的评论:"我在学校学习了递归,但从那时起就没有使用它或感觉到需要它." (递归似乎是某一类程序员中"书本学习"的一个流行的例子.)
嗯,在Java和Ruby [1]等命令式语言中,我们通常使用迭代并避免递归,部分原因是存在堆栈溢出的风险,部分原因是因为这些语言中的大多数程序员都习惯使用.
现在我知道,严格地说,在这样的语言中没有"必要的"递归用法:无论事情多么复杂,都可以用迭代替换递归.在这里"必要",我说的是以下内容:
您是否可以想到这些语言中代码的任何特定示例,其中递归比迭代(为了清晰,效率或其他原因)更好,无论如何您使用递归,转换为迭代会是一个很大的损失？
在答案中已经多次提到了递归行走的树:如果它可用,那么它使用它的确切原因是什么使得递归比使用库定义的迭代器更好？
[1]:是的,我知道这些也是面向对象的语言.然而,这与这个问题没有直接关系.