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

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

如果正在使用的编译器支持尾部调用优化，并且您构建代码以利用它，则递归的效率并不低。

Answer 3

如果语言没有被编译器优化，递归很可能比迭代慢，因为在给定的车道上下降，这相当于迭代，你必须在完成工作后回溯你的步骤回到顶部。

除此之外，它几乎是等同的，除了它可能更优雅，因为您让编译器和系统在幕后处理循环。当然，有些任务(比如处理树形结构)中，递归是唯一的方法(或者至少是唯一不会令人绝望地纠结的方法)。