在Erlang中使用大量的尾递归会减慢它吗？

Question

我最近一直在阅读关于Erlang的内容,以及由于使用迭代循环的困难,尾部递归如此频繁使用.

递归的这种高使用是否会降低它的速度,所有函数调用以及它们对堆栈的影响是什么？或者尾部递归否定了大部分内容？

Answer 1

关键是Erlang优化尾调用(不仅是递归).优化尾调用非常简单:如果返回值是通过调用另一个函数计算的,那么另一个函数不仅仅放在调用函数顶部的函数调用堆栈上,而是当前函数的堆栈帧是被一个被调用的函数取代.这意味着尾调用不会增加堆栈大小.

所以,不,使用尾递归不会减慢Erlang的速度,也不会造成堆栈溢出的风险.

通过尾调用优化,您不仅可以使用简单的尾递归,还可以使用多个函数的相互尾递归(尾调用b,尾调用c,尾调用...).这有时可能是一个很好的计算模型.

Answer 2

迭代尾递归通常使用Tail调用来实现.这基本上是递归调用到简单循环的转换.

C#示例:

uint FactorialAccum(uint n, uint accum) {
    if(n < 2) return accum;
    return FactorialAccum(n - 1, n * accum);
};
uint Factorial(uint n) {
    return FactorialAccum(n, 1);
};

至

uint FactorialAccum(uint n, uint accum) {
start:
    if(n < 2) return accum;
    accum *= n;
    n -= 1;
goto start;
};
uint Factorial(uint n) {
    return FactorialAccum(n, 1);
};

甚至更好:

uint Factorial(uint n) {
    uint accum = 1;
start:
    if(n < 2) return accum;
    accum *= n;
    n -= 1;
goto start;
};

C#不是真正的尾递归,这是因为返回值被修改,大多数编译器不会将其分解为循环:

int Power(int number, uint power) {
    if(power == 0) return 1;
    if(power == 1) return number;
    return number * Power(number, --power);
}

至

int Power(int number, uint power) {
    int result = number;
start:
    if(power == 0) return 1;
    if(power == 1) return number;
    result *= number;
    power--;
goto start;
}