为什么OCaml中的递归比C++或Java更有效？

Question

本文C++/Java程序员对caml.inria.fr网站上的Objective Caml的介绍说...

与C++和Java相反,O'Caml [sic]中的递归与迭代一样有效

对于类似于阶乘的东西,似乎带有可变变量的循环比递归调用所涉及的堆栈操作更有效.

OCaml真的有一种机制使递归比C++和Java更有效吗？

Answer 1

是的,在某些情况下.它被称为尾调用优化.例如,采用以下C-ish阶乘函数:

int factorial(int n) 
{
        if (n < = 1)
                return 1;
        else
                return n * factorial(n – 1);
}

在"展开"备份以获得结果之前,此函数在调用堆栈中深入n级.以下是OCaml等价物:

let factorial n = if n <= 1 then 1 else n * factorial (n - 1) 

实际上,上面的代码也将深入到调用堆栈中,就像上面的C-ish代码一样.这是C-ish函数,它实现了相同但循环:

int factorial(int n)
{
        int ret = 1;
        for (; n > 1; n--)
                ret *= n;
        return ret;
} 

当然,这个函数可以被调用任意次,而不会溢出堆栈(即使你快速溢出32位int).实际上可以在OCaml中编写同义函数.现在,OCaml的版本将再次使用递归.但是,如果我们在第一个函数中添加"accumulator"参数,则可以将其重写为:

let factorial acc n = if n <= 1 then acc else factorial (acc * n) (n – 1)

acc参数可以被认为是"累积"所有先前递归调用到阶乘的结果.关键效果是上面的表达式"n*factorial(n-1)"变形为下面的"factorial(acc*n)(n-1)"表达式.在第二个表达式中,对factorial的递归调用是表达式的顶级,这意味着不需要执行额外的操作来获取函数的返回值.第一个表达式不是这样,其中顶级操作是n - 1的阶乘结果与n的乘积.当递归函数调用是顶级表达式时,它被认为是"尾调用",编译器可以并且将其优化为有效的循环.在第一个函数上调用"factorial 2000000"将(可能)导致堆栈溢出,但在第二个函数上调用"factorial 1 2000000"将不会.此外,您可能会发现第二个OCaml函数与C等效的性能相当(可能稍微慢一点,但不是数量级或任何其他).

顺便说一下,你可能会问自己,"但是,尾部递归函数有一个不必要的额外'acc'参数,在用户最初调用时应始终为1,这不是很笨拙吗？"是的,是的.通过将尾递归函数嵌套到"包装器"函数中可以很容易地解决这个问题,该函数使用正确的初始累积值调用它,如下所示:

let factorial n =
    let loop acc n' = if n' <= 1 then acc else loop (acc * n') (n' – 1) in
    loop 1 n

在这里,我将上面的尾递归因子函数重命名为"循环"并将其嵌套在函数中,然后函数使用正确的初始累加器1调用它.

通常情况下,可以使用标准库中的高阶函数替换这些尾递归模式,例如List.fold,但并非总是如此.