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

wqnecbli  于 2022-12-08  发布在  Erlang
关注(0)|答案(5)|浏览(213)

我最近阅读了一些关于Erlang的文章,以及尾递归是如何被大量使用的,这是因为使用迭代循环很困难。
递归的频繁使用是否会降低它的速度,因为所有的函数调用和它们对堆栈的影响?或者尾部递归会否定大部分这些?

lsmd5eda

lsmd5eda1#

重点是Erlang优化了尾部调用(不仅仅是递归)。优化尾部调用非常简单:如果返回值是通过调用另一个函数计算出来的,那么这个函数不仅会被放在调用函数的调用栈上,而且当前函数的栈帧会被一个被调用的函数 * 替换 *。这意味着尾部调用不会增加栈的大小。
所以,不,使用尾递归不会减慢Erlang的速度,也不会造成堆栈溢出的风险。
有了尾调用优化,你不仅可以使用简单的尾递归,还可以使用几个函数的相互尾递归(a尾调用b,b尾调用c,c尾调用a ......)。这有时是一个很好的计算模型。

iih3973s

iih3973s2#

迭代尾递归通常使用Tail calls实现,这基本上是一个递归调用到简单循环的转换。
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;
}
q5lcpyga

q5lcpyga3#

在大多数情况下,它应该不会影响性能。您要寻找的不仅仅是尾部调用,但是尾部调用优化尾部调用优化是一种编译器或运行时技术,它可以计算出何时对函数的调用相当于“弹出堆栈”以返回到正确的函数,而不仅仅是返回。一般尾调用的优化只能在递归调用是函数中的最后一个操作时才能完成,所以必须小心。

q9yhzks0

q9yhzks04#

有一个与尾递归相关的问题,但它与性能无关- Erlang尾递归优化还涉及消除用于调试的堆栈跟踪。
例如,请参阅Erlang常见问题解答的第9.13点:
为什么堆栈回溯不能显示出这段代码的正确函数:

-module(erl).
-export([a/0]).

a() -> b().
b() -> c().
c() -> 3 = 4.           %% will cause badmatch

堆栈回溯只显示函数c(),而不是a()、b()和c()。这是因为上次调用优化;编译器知道它不需要为a()或B()生成堆栈帧,因为它所做的最后一件事是调用另一个函数,因此堆栈帧不会出现在堆栈回溯中。
当您遇到崩溃时,这可能会有点痛苦(但它确实有点符合函数式编程的领域...)

k7fdbhmy

k7fdbhmy5#

将程序文本函数调用与实现函数调用分离类似优化是'内嵌'在现代/有思想语言中,函数调用与机器级函数调用关系不大

相关问题