8

私は最近Erlangについて読んでいて、反復ループを使用するのが難しいため、末尾再帰がどのように頻繁に使用されているかを読んでいます。

このように再帰を頻繁に使用すると、速度が低下しませんか？すべての関数呼び出しとそれらがスタックに与える影響はどうでしょうか？または、末尾再帰はこれのほとんどを無効にしますか？

4

5 に答える 5

19

重要なのは、Erlangが末尾呼び出しを最適化することです（再帰だけでなく）。末尾呼び出しの最適化は非常に簡単です。戻り値が別の関数の呼び出しによって計算される場合、この他の関数は、呼び出し元の関数の上にある関数呼び出しスタックに配置されるだけでなく、現在の関数のスタックフレームは次のようになります。呼び出された関数の1つに置き換えられました。これは、末尾呼び出しがスタックサイズに追加されないことを意味します。

したがって、末尾再帰を使用してもErlangの速度が低下したり、スタックオーバーフローのリスクが発生したりすることはありません。

末尾呼び出しの最適化を使用すると、単純な末尾再帰だけでなく、いくつかの関数の相互の末尾再帰も使用できます（末尾呼び出しb、末尾呼び出しc、末尾呼び出しa ...）。これは、計算の優れたモデルになる場合があります。

于 2009-07-09T18:35:25.340 に答える
8

反復的な末尾再帰は、通常、末尾呼び出しを使用して実装されます。これは基本的に、再帰呼び出しから単純なループへの変換です。

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の末尾再帰の最適化には、デバッグ用のスタックトレースの削除も含まれます。

たとえば、ErlangFAQのポイント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 に答える