14

単純な場合もありますが (自己呼び出しが最後のステートメントの場合は末尾再帰です)、それでも混乱する場合があります。「自己呼び出しの後に実行する命令がない場合は、末尾再帰です」と教授に言われました。これらの例はどうですか (あまり意味がないという事実は無視してください):

a) これは、自己呼び出しが最後のステートメントであり、その後に実行するものが残っていないことを確認して、末尾再帰にする必要があります。

function foo(n)
{
    if(n == 0)
        return 0;
    else
        return foo(n-2);
}

b) でも、これはどうですか？条件が真の場合、それ以外は何も実行されないため、末尾呼び出しにする必要がありますが、最後のステートメントではありませんか?

function foo(n)
{
    if(n != 0)
        return foo(n-2);
    else
        return 0;
}

c) これはどうですか？どちらの場合も、自己呼び出しが最後に実行されます。

function foo(n)
{
    if(n == 0)
        return 0;
    else    
    {
        if(n > 100)
            return foo(n - 2);
        else
            return foo(n - 1);
    }
}
4

4 に答える 4

19

末尾呼び出しの最適化が実際にどのように実装されているかという観点から、これについて考えると役立つ場合があります。もちろん、それは定義の一部ではありませんが、定義の動機付けになります。

通常、関数が呼び出されると、呼び出し元のコードは、後で必要になるレジスタ値をスタックに格納します。また、呼び出し後の次の命令を示す差出人住所も保存されます。スタックポインタが呼び出し先に対して正しく設定されていることを確認するために必要なことは何でも行います。次に、ターゲットアドレス[*]（この場合は同じ関数）にジャンプします。戻ると、呼び出し規約（レジスタまたはスタックスロット）で指定された場所に戻り値があることがわかります。

末尾呼び出しの場合、呼び出し元はこれを行いません。後で必要にならないことがわかっているため、レジスタ値は無視されます。呼び出し先が呼び出し元が使用したのと同じスタックを使用するようにスタックポインタを設定し、リターンアドレスとして設定せず、ターゲットアドレスにジャンプするだけです。したがって、呼び出し先は同じスタック領域を上書きし、呼び出し元が戻り値を置いたのと同じ場所に戻り値を置き、戻ったときに呼び出し元に戻らず、呼び出し元に戻ります。発信者。

したがって、非公式には、末尾呼び出しの最適化が発生する可能性がある場合、および末尾呼び出しのターゲットが関数自体である場合、関数は末尾再帰です。効果は、関数にループが含まれている場合とほぼ同じであり、それ自体を呼び出す代わりに、末尾呼び出しがループの先頭にジャンプします。これは、呼び出し後に変数が必要ないことを意味し（実際、C ++のような言語では破棄されるものがないことを意味する「実行する作業」はありません）、末尾呼び出しの戻り値は呼び出し元によって返される必要があります。

これはすべて、単純/些細な末尾再帰用です。まだ行われていない末尾再帰を作成するために使用できる変換があります。たとえば、「最下位」レベルの再帰で使用される情報を格納する追加のパラメーターを導入して、他の方法で実行される作業を実行します。逃げ道"。たとえば、次のようになります。

int triangle(int n) {
    if (n == 0) return 0;
    return n + triangle(n-1);
}

プログラマーによって、または次のように十分に賢いコンパイラーによって自動的に末尾再帰にすることができます。

int triangle(int n, int accumulator = 0) {
    if (n == 0) return accumulator;
    return triangle(n-1, accumulator + n);
}

したがって、前者の関数は、十分に賢い言語/コンパイラについて話している人によって「末尾再帰」として説明される可能性があります。そのバリアントの使用法に備えてください。

[*]リターンアドレスの格納、スタックポインタの移動、およびジャンプは、アーキテクチャによって単一のオペコードにラップされる場合とされない場合がありますが、そうでない場合でも、通常はそうなります。

于 2010-09-09T18:22:32.980 に答える
6

うん; あなたの教授は、最終的な命令が再帰的である場合、それは末尾再帰であるということを意味していたと思います。

したがって、3 つの例はすべて末尾再帰です。

于 2010-09-09T16:36:30.273 に答える
6

すべての関数は末尾再帰です。

セルフコール後に指示が残っていない

つまり、自己呼び出しの後、関数から戻ります。つまり、これ以上コードを実行する必要はなく、関数内にコード行がなくなるわけではありません。

于 2010-09-09T16:36:49.813 に答える
3

3つの例はすべて末尾再帰です。一般的に言えば、関数の結果（「return」キーワードに続く式）が関数自体への唯一の呼び出しである場合、それは末尾再帰です。式の最も外側のレベルに他の演算子を含めることはできません。それ自体への呼び出しが式の一部にすぎない場合、マシンは呼び出しを実行する必要がありますが、その後、式の評価に戻る必要があります。つまり、関数実行の最後ではなく、途中でした。表現。ただし、これは再帰呼び出しが取る可能性のあるパラメータには適用されません。それ自体への再帰呼び出しを含め、何でも許可されます（たとえば、「return foo（foo（0））;」）。もちろん、ジャンプの呼び出しの最適化は、外部の呼び出しに対してのみ可能です。

于 2010-09-09T16:52:21.777 に答える