8

我最近一直在阅读有关 Erlang 的文章，以及尾递归是如何被大量使用的，因为使用迭代循环很困难。

递归的大量使用不会减慢它的速度吗？所有的函数调用以及它们对堆栈的影响是什么？还是尾递归否定了大部分？

4

5 回答 5

19

关键是 Erlang 优化了尾调用（不仅仅是递归）。优化尾调用非常简单：如果返回值是通过调用另一个函数来计算的，那么这个另一个函数不仅仅是放在调用函数顶部的函数调用堆栈上，而是当前函数的堆栈帧是替换为调用函数之一。这意味着尾调用不会增加堆栈大小。

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

有了尾调用优化，您不仅可以使用简单的尾递归，还可以使用多个函数的相互尾递归（a 尾调用 b，哪个尾调用 c，哪个尾调用 a ...）。这有时可能是一个很好的计算模型。

于 2009-07-09T18:35:25.340 回答
8

迭代尾递归通常使用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;
}
于 2009-07-09T18:25:15.110 回答
3

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

于 2009-07-09T18:35:25.400 回答
2

有一个与尾递归有关的问题，但它与性能无关 - Erlang 尾递归优化还涉及消除堆栈跟踪以进行调试。

例如，参见Erlang FAQ的第 9.13 点：

Why doesn't the stack backtrace show the right functions for this code:

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

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

The stack backtrace only shows function c(), rather than a(), b() and c().
This is because of last-call-optimisation; the compiler knows it does not need
to generate a stack frame for a() or b() because the last thing it did was
call another function, hence the stack frame does not appear in the stack
backtrace.

当你遇到崩溃时，这可能会有点痛苦（但它确实有点符合函数式编程的领域......）

于 2009-07-09T21:50:32.450 回答
1

将程序文本函数调用与实现函数调用分开的类似优化是“内联”。在现代/周到的语言中，函数调用与机器级函数调用关系不大。

于 2009-07-09T18:52:40.547 回答