C++ コンパイル エラー: 再帰が深すぎるとスタック オーバーフローが発生します。解決方法は?

C は広く使用されているプログラミング言語であり、コンパイルおよび実行中にさまざまなエラーが発生することは避けられません。よくある間違いの 1 つは、再帰を深くしすぎてスタック オーバーフローを引き起こすことです。

再帰では、再帰レベルが多すぎると、プログラムでスタック オーバーフロー エラーが発生します。これは、再帰関数では、各再帰中にローカル変数と関数呼び出しを保存するために一定量のメモリ スペースが必要になるためです。各再帰により、これらのローカル変数と関数呼び出しが関数呼び出しスタックにプッシュされます。スタックのサイズには制限があります。この制限を超えると、スタック オーバーフローが発生し、プログラムがクラッシュします。

それでは、深すぎる再帰によって引き起こされるスタック オーバーフローをどのように解決すればよいでしょうか?ここではいくつかの解決策を紹介します。

1. 再帰をループとして書き直す

再帰関数の本質はバックトラックを伴うループであるため、プログラム ロジックに影響を与えることなく、再帰関数をサイクルとして書き直すことができます。これにより、再帰によって生じるオーバーヘッドが軽減され、スタック オーバーフローのリスクが軽減されます。

たとえば、次はフィボナッチ数列を計算する再帰関数です:

int fib(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

これを次のループ形式で書き直すことができます:

int fib(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

2. Increase the stack Space

スタック スペースのサイズを設定することで、スタック オーバーフローを回避できます。 Windows では、プログラムの実行可能ファイルのスタック スペース サイズを変更することでこれを実現できます。Linux では、ulimit コマンドを使用してスタック サイズを制御できます。このアプローチで注意すべき点は、スタック領域が多すぎるとシステム リソースを占有してしまうため、メリットとデメリットを比較検討する必要があることです。

3. 再帰アルゴリズムを調整する

再帰アルゴリズム自体に問題があり、再帰レベルが多すぎる場合があります。この場合、再帰アルゴリズムを最適化し、再帰呼び出しの数を減らし、スタック オーバーフローのリスクを減らす必要があります。

たとえば、次はフィボナッチ数列を解くための再帰アルゴリズムです:

int fib(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

メモ化された検索を通じてこのアルゴリズムを最適化し、再帰呼び出しの数を減らすことができます:

int fib(int n, unordered_map<int, int>& memo) {
    if (n == 0 || n == 1) {
        return n;
    }
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }
    int ans = fib(n - 1, memo) + fib(n - 2, memo);
    memo[n] = ans;
    return ans;
}

int fib(int n) {
    unordered_map<int, int> memo;
    return fib(n, memo);
}

4. 再帰関数の計算の繰り返しを避ける

再帰関数では、計算の繰り返しによる副次的な問題が発生する可能性があります。キャッシュ メカニズムを使用して再帰呼び出しの数を減らすことで、これを回避できます。

たとえば、カタロニア数を計算する必要がある場合、キャッシュ メカニズムを使用して計算の繰り返しを避けることができます。

int catalan(int n, unordered_map<int, int>& memo) {
    if (n <= 1) {
        return 1;
    }
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += catalan(i, memo) * catalan(n - 1 - i, memo);
    }
    memo[n] = ans;
    return ans;
}

int catalan(int n) {
    unordered_map<int, int> memo;
    return catalan(n, memo);
}

つまり、次のような原因によるスタック オーバーフローを回避する方法はたくさんあります。深い再帰. 特定の状況に応じて適切なメソッドを選択する必要があります。再帰関数を作成するときは、再帰の深さに必ず注意し、プログラムが正しく実行されることを確認するために十分なテストを行ってください。

以上がC++ コンパイル エラー: 再帰が深すぎるとスタック オーバーフローが発生します。解決方法は?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。