1

Programming Interviews Exposed (第 3 版) で再帰について読みました。そこでは、次の再帰factorial関数が提示されています。

int factorial(int n){
    if (n > 1) { /* Recursive case */
        return factorial(n-1) * n;
    } else {     /* Base case */
        return 1;
    }
}

同じページの下部 (108 ページ) で、末尾再帰関数について説明しています。

上記の の定義のように、再帰呼び出しによって返される値自体がすぐに返されるfactorial場合、関数は末尾再帰であることに注意してください。

しかし、これは本当にここに当てはまりますか？関数の最後の呼び出しは*呼び出しなので、このスタック フレームは保持されませんか (コンパイラの最適化を考慮しない場合)。これは本当に末尾再帰ですか？

4

4 に答える 4

5

末尾再帰に書き換えることができます。

int factorial(int n){
    return factorial2(n, 1);
}
int factorial2(int n, int accum) {
    if (n < 1) {
       return accum;
    } else {
        return factorial2(n - 1, accum * n);
    }
}
于 2013-04-20T01:51:22.237 に答える
4

いいえ、末尾再帰ではありません。によって返される結果は、factorial(n-1)さらに で乗算する必要があります。これには、制御nを取り戻す必要がありますfactorial(n)(したがって、呼び出しをfactorial(n-1)ジャンプではなく呼び出しにする必要があります)。

そうは言っても、末尾再帰であっても、コンパイラは TCO を実行しない可能性があります。コンパイラと、コンパイラに要求する最適化に依存します。

于 2013-04-20T01:45:26.170 に答える
1

このリンクからの引用:階乗を例として使用した末尾再帰

 factorial(n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
 }//equivalent to your code

 This definition is NOT tail-recursive since the recursive call to 
 factorial is not the last thing in the function 
 (its result has to be multiplied by n)
于 2013-04-20T01:45:48.357 に答える
0

Tail Recursive関数の最後の操作が再帰呼び出しである再帰の特殊なケースです。末尾再帰関数では、再帰呼び出しから戻ったときに実行される保留中の操作はありません。あなたが言及した関数は、保留中の操作、つまり再帰呼び出しからの戻り時に実行される乗算があるため、末尾再帰ではありません。これを行った場合：

    int factorial(int n,int result)
    {
        if (n > 1)
        { /* Recursive case */
             return factorial(n-1,n*result);
        }
        else
        {     /* Base case */
            return result;
        }
    }

テール再帰関数になります。再帰呼び出しから戻ったときに保留中の操作がないためです。

于 2013-04-20T01:57:11.027 に答える