函数式编程中的有效递归与不同范式中的低效递归

Question

据我所知,递归非常优雅,但在OOP和程序编程方面效率不高(参见精彩的"High Order perl",Mark Jason Dominus).我有一些信息,在函数式编程递归中很快 - 保持其优雅和简洁.有人可以确认并可能放大这个吗？我正在考虑XSLT和Haskell(我的下一个语言学习列表的高位)

谢谢

丹尼尔

Answer 1

尾递归是任何体面的函数式语言实现中的迭代.这是使用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条指令.

这就是为什么函数组合和递归在良好的优化函数语言中非常有效的原因.

Answer 2

OOP/Procedural语言倾向于在每次进行递归调用时将数据放在堆栈上 - 因此递归不如这些语言中的迭代有效.

相比之下,函数式语言的编译器/解释器通常被设计为优化尾递归,以便与迭代一样高效:

递归可能需要维护堆栈,但是尾部递归可以由编译器识别和优化为用于在命令式语言中实现迭代的相同代码.Scheme编程语言标准要求实现识别和优化尾递归.尾递归优化可以通过在编译期间将程序转换为连续传递样式以及其他方法来实现.

什么是尾部调用优化和哪些语言支持尾部递归优化有更详细的信息.

Answer 3

如果使用的编译器支持尾调用优化并且您构造代码以利用它,则递归效率不高.

由于函数式编程中递归的出现,函数式语言的编译器更有可能实现程序性的尾部调用优化.