0

私のプログラムは次のとおりです。

#include <stdio.h>

int collatz(int seed, int count) {
    int next = 0;
    if (seed % 2 == 0) {
        next = seed / 2;
    } else {
        next = 3 * seed + 1;
    }
    count++;
    if (next == 1) {
        return count;
    } else {
        return collatz(next, count);
    }
}

int main() {
    int max = 0;
    int index = 0;
    int i;
    for (i=1; i<1000000; i++) {
        int current = collatz(i, 1);
        if (current > max) {
            max = current;
            index = i;
        }
    }
    printf("%i\n", index);
    return 0;
}

通常、再帰は特定の深さまでしか進まないことを理解しています。ただし、私が知る限り、セグフォルトを停止する末尾再帰を実装しました。i を 100,000 に設定すると、プログラムが実行され、基礎となるアルゴリズムが正しいと信じるようになります。ただし、100万で次のようになります。

セグメンテーション違反: 11

私は何を間違っていますか？

4

3 に答える 3

10

デバッガーを使用すると、実際に関数が末尾再帰ではないことがわかる場合があります。しかし、なぜですか？おそらく、コンパイル中に最適化を有効にするのを単に忘れたためです。私のシステム (Mac OS 上の GCC) では、デフォルトのビルドはクラッシュしますが、-O3オプションを使用してビルドすると実行できます (少なくとも、そうでない場合よりもずっと長く、バッテリー テストを強制終了したくなかったからです)。

于 2013-04-17T12:20:14.240 に答える
1

100万で実行している場合、おそらくスタックスペースが不足していて、セグメンテーション違反が発生していると思います

VSで使用しているコンパイラ/OSのスタックサイズはデフォルトで1MBですが、増やすことができます。他のコンパイラと OS の組み合わせについてはわかりません

于 2013-04-17T12:21:04.520 に答える
0

collat​​z関数は、計算の途中でオーバーフローを引き起こしています。（それはスタックオーバーフローです）。

注:末尾再帰のコンパイラ最適化は、実行される場合と実行されない場合があります。

long long (Int64) を使用します。

int collatz(long long seed, int count) {
    long long next = 0;
    if (seed % 2 == 0) {
        next = seed / 2;
    } else {
        next = 3 * seed + 1;
    }
    count++;
    if (next == 1) {
        return count;
    } else {
        return collatz(next, count);
    }
}
于 2013-04-17T17:24:51.373 に答える