1

私は C を学んでいるので、言語を練習するために C でいくつかの小さな演習を書いています。

関数型コードの経験があるので、再帰が大好きです。C の静的変数を使用して末尾再帰を実現できれば素晴らしいと思います。そのため、追加の引数やヘルパー関数は必要ありません。

再帰を使用して階乗を計算するこのコードは失敗します。

long long int fact(int n)
{
    static long long int result = -1;

    if(n <= 0) {
        if(result < 0)
            return 1;
        else {
            long long int temp = result;
            result = -1;
            return temp;
        }
    } else {
        result *= n;
        fact(n - 1);
    }
}

しかし、何らかの理由で、C でこれを行うことはできません。同じイディオムはありますか? それは私のコンパイラだけですか？メモ化はどうですか？

どうもありがとう。

4

3 に答える 3

4

値を返さない制御パスがあるため、コードが壊れています。これはうまくいきます：

long long int fact(int n)
{
    static long long int result = 1;

    if(n <= 1) {
        long long int temp = result;
        result = 1;
        return temp;
    } else {
        result *= n;
        return fact(n - 1);
    }
}

GCC は末尾再帰を iteration に正常に変換します。

一般に、末尾再帰に static を使用しない理由は、単に関数が再入可能性を失うためだと思います。最近では非常に多くのコードをマルチスレッド環境で実行する必要があるため、関数ローカルの静的な "地雷" をコードに残すことを正当化するのは困難です。これが技術的な議論と同じくらい意見であることは認めます。非静的末尾再帰コード:

static inline long long int fact_(int n, long long int result)
{
    if(n <= 1) {
        return result;
    } else {
        return fact_(n - 1, result * n);
    }
}

long long int fact(int n)
{
    return fact_(n, 1);
}

どちらかと言えば書きやすいです - 特に両方のバージョンが正確に 13 LOC です - そして静的データを必要とせずに同じように効率的に繰り返しコンパイルします。

于 2013-08-07T06:39:02.823 に答える
1

else ブロックからの明示的な戻り値がないようです。その上でコンパイラの警告が表示されていませんか? すべての警告をオンにしてコンパイルしていることを確認してください。

基本的に、else ブロックの最後に追加する必要がありreturn result;ます。それ以外の場合、元の呼び出し元に結果を返すにはどうすればよいでしょうか? return は 1 つの関数呼び出しのみをポップすることを忘れないでください。else ブロックで行った fact() へのすべての再帰呼び出しのために、return を呼び出すときは任意の深さになります。

于 2013-08-07T06:00:39.913 に答える
1 
int factorial(int n)
{
    static int m = 1;
    m *= n;
    if (n > 1)
        factorial(n - 1);
    return m;
}
于 2013-08-07T06:08:23.123 に答える