据我所知，递归在 OOP 和过程编程中非常优雅但效率低下（参见精彩的“High Order perl”，Mark Jason Dominus）。我有一些信息表明，在函数式编程中，递归很快——保持其优雅和简单。有人可以确认并可能放大这一点吗？我正在考虑 XSLT 和 Haskell（在我的下一门语言学习列表中排名靠前）
谢谢
丹尼尔
问问题
3258 次
8 回答
20
尾递归是任何体面的函数式语言实现中的迭代。这是一个使用 GHC Haskell 的示例。一个简单的程序来添加一个数字序列。它从几个递归函数的组合开始：
import qualified Data.Vector as U
main = print (U.sum (U.enumFromTo 1 (10000000 :: Int)))
编译器将其优化为单个尾递归函数（在源到源转换中）：
loop x y = case y <= y 10000000 of
False -> x
True -> loop (x + y) (y + 1)
然后将此递归函数编译为直接循环：
loop:
.Lc216:
cmpq $10000000,%rsi
jle .Lc219
movq %r14,%rbx
movq (%rbp),%rax
jmp *(%rax)
.Lc219:
addq %rsi,%r14
incq %rsi
jmp loop
或者使用 GHC LLVM 后端，对程序的命令式表示应用额外的优化：
loop:
leaq 1(%rsi), %rax
addq %rsi, %r14
cmpq $10000001, %rax
jge .LBB1_5
addq $2, %rsi
addq %rax, %r14
test: # %tailrecurse
cmpq $10000001, %rsi
jl loop
注意尾递归标签是如何标记的。
所以我们有一个递归函数管道，它们被编译成一个尾递归函数，它被编译成一个不使用堆栈的命令式循环。最后是8条指令。
这就是为什么函数组合和递归在优秀的优化函数语言中都非常有效的原因。
于 2010-02-26T17:00:24.950 回答
7
OOP/过程语言倾向于在每次进行递归调用时将数据放在堆栈上 - 因此递归不如这些语言中的迭代有效。
相比之下，函数式语言的编译器/解释器通常旨在优化尾递归，使其与迭代一样高效：
递归可能需要维护一个堆栈，但尾递归可以被编译器识别并优化为用于在命令式语言中实现迭代的相同代码。Scheme 编程语言标准要求实现来识别和优化尾递归。尾递归优化可以通过在编译期间将程序转换为继续传递样式等方法来实现。
what-is-tail-call-optimization和which-languages-support-tail-recursion-optimization有更详细的信息。
于 2010-02-26T16:03:20.843 回答
6
如果使用的编译器支持尾调用优化并且您构建代码以利用它，那么递归并不是低效的。
由于函数式编程中递归的普遍存在，函数式语言的编译器更有可能实现与过程式语言相比的尾调用优化。
于 2010-02-26T16:17:10.067 回答
3
XSLT 中的高效递归
在 XSLT 中实现高效递归有两种主要方法：
- 尾递归优化
- 分而治之 (DVC)
有很多关于尾递归的答案，所以这里只是一个简单的例子：
<xsl:function name="my:sum">
<xsl:param name="pAccum" as="xs:double*"/>
<xsl:param name="pNums" as="xs:double*"/>
<xsl:sequence select=
"if(empty($pNums))
then $pAccum
else
my:sum($pAccum + $pNums[1], $pNums[position() >1])
"
/>
</xsl:function>
可以检查 my:sum(0, 1 to 100) 是否被评估为：5050。
以下是如何sum()以 DVC 方式实现该功能：
<xsl:function name="my:sum2">
<xsl:param name="pNums" as="xs:double*"/>
<xsl:sequence select=
"if(empty($pNums))
then 0
else
if(count($pNums) eq 1)
then $pNums[1]
else
for $half in count($pNums) idiv 2
return
my:sum2($pNums[not(position() gt $half)])
+
my:sum2($pNums[position() gt $half])
"
/>
</xsl:function>
DVC 背后的主要思想是将输入序列细分为两个（通常）或多个部分，并彼此独立地处理它们，然后将结果组合起来以产生整个输入序列的结果。
请注意，对于一系列N项目，调用堆栈在任何时间点的最大深度都不会超过log2(N)，这对于大多数实际用途来说已经绰绰有余了。例如，在处理 1000000 (1M) 个项目的序列时，调用堆栈的最大深度仅为 19。
虽然有些 XSLT 处理器不够智能，无法识别和优化尾递归，但 DVC 递归模板适用于任何 XSLT 处理器。
于 2010-02-26T20:44:30.620 回答
2
The only thing I have to add to dons's answer is that many language are hostage to legacy calling conventions. Nowhere is this more true than languages that conform to the C calling convention on x86: every parameter goes on the stack. Functional languages pass at least some parameters in registers, and so on the 32-bit platforms, even the non-tail calls (which can't be optimized) are still more efficient than in, say, C.
Thank God the x86-64 has a decent C calling convention!
于 2010-02-28T03:18:00.600 回答
1
如果编译器没有对语言进行优化，递归很可能比迭代慢，因为在下降到给定的车道之上，这几乎等同于迭代，你必须在完成后回溯你的步骤回到顶部工作。
否则，它几乎是等价的，只是它可能更优雅，因为您让编译器和系统在幕后处理循环。当然，在某些任务（例如处理树状结构）中，递归是唯一的方法（或者至少是唯一不会令人绝望地复杂化的方法）。
于 2010-02-26T16:07:53.190 回答
0
函数式语言中递归快速的原因是编译器可以在内部使用尾递归消除（或更一般地，尾调用消除）将递归转换为迭代。基本上，如果递归调用是函数返回之前的最后一个操作，并且函数的返回值是递归调用的返回值，那么程序不会创建新的堆栈帧，而是重用当前帧。参数变量设置为新值，PC 设置为函数的开头。
利用尾递归消除需要程序员有一定的意识。您需要确保您的递归调用实际上是尾调用。例如，下面是 OCaml 中用于计算阶乘的代码：
let rec factorial n =
if n = 0 then
1
else
n * factorial (n - 1)
尾调用消除在这里不会直接起作用，因为必须在递归调用之后执行乘法。但是，如果函数被重写为：
let factorial n =
let rec fac_helper n p =
if n = 0 then
p
else
fac_helper (n - 1) (p * n)
in
fac_helper n 1
现在可以使用尾调用消除。这将被转换成这样的东西（在伪代码中）：
factorial p n =
p = 1
while n > 0
n = n - 1
p = p * n
return p
这种风格可能看起来违反直觉，但它与迭代版本一样有意义。计算的每一步都是在调用递归函数时执行的。在整个计算中使用的归纳变量（如上述）被声明为p参数。n
应该注意的是，大多数命令式和函数式语言的编译器都利用了这种优化。事实上，LLVM 的优化版本甚至允许递归调用和返回之间的关联操作，因此您可以编写阶乘的第一个版本并且仍然使用优化。但是，JVM 不支持尾调用消除，因此 JVM 上的函数式语言（如 Scala）对它的支持有限。
于 2010-02-26T16:45:02.100 回答
0
不要假设递归与迭代是您应该关注的地方。
通常，在您首先消除了一系列较大的性能问题后，这会变得很重要。
于 2010-02-26T23:46:39.967 回答