11

私は C++ で末尾再帰関数をいじっていましたが、g++ コンパイラで少し問題が発生しました。

numbers[]次のコードでは、サイズが数百の整数を超えるとスタック オーバーフローが発生します。以下の g++ によって生成されたアセンブリ コードを調べると、twoSum_Helper がcallそれ自体に対して再帰命令を実行していることがわかります。

問題は、次のうちどれがこれを引き起こしているかです。

  • 私が見落としている以下の間違いは、末尾再帰を妨げています。
  • 私のg ++​​の使い方の間違い。
  • g++ コンパイラ内の末尾再帰関数の検出に問題があります。

g++ -O3 -Wall -fno-stack-protector test.cg++ 4.5.0 を使用して MinGW 経由で Wi​​ndows Vista x64 でコンパイルしています。

struct result
{
    int i;
    int j;
    bool found;
};

struct result gen_Result(int i, int j, bool found)
{
    struct result r;
    r.i = i;
    r.j = j;
    r.found = found;
    return r;
}

// Return 2 indexes from numbers that sum up to target.
struct result twoSum_Helper(int numbers[], int size, int target, int i, int j)
{
    if (numbers[i] + numbers[j] == target)
        return gen_Result(i, j, true);
    if (i >= (size - 1))
        return gen_Result(i, j, false);
    if (j >= size)
        return twoSum_Helper(numbers, size, target, i + 1, i + 2);
    else
        return twoSum_Helper(numbers, size, target, i, j + 1);
}
4

8 に答える 8

4

C または C++ でのテール コールの最適化は非常に制限されており、ほとんど原因がありません。その理由は、ポインターまたはローカル変数への参照を (問題の呼び出しへの引数として、または実際には同じ関数内の他の呼び出しとして) 渡す関数から末尾呼び出しを行う安全な方法が一般にないためです。もちろん、これは C/C++ の世界のいたるところで起こっており、それなしでは生きていくことはほとんど不可能です。

あなたが見ている問題はおそらく関連しています.GCCは、呼び出し元のスタックに割り当てられた隠し変数のアドレスを実際に渡すことにより、構造体を返すようにコンパイルする可能性があります。これにより、上記のシナリオに陥ります。

于 2013-03-12T09:12:22.673 に答える
2

-O3 の代わりに -O2 でコンパイルしてみてください。

gcc が末尾再帰の最適化を実行しているかどうかを確認するにはどうすればよいですか?

まあ、とにかくO2では機能しません。機能しているように見える唯一のことは、resultオブジェクトをパラメーターとして指定された参照に返すことです。

しかし実際には、Tail 呼び出しを削除して代わりにループを使用する方がはるかに簡単です。TCO は、インライン化時またはアグレッシブな展開の実行時に検出されるテール コールを最適化するためにここにありますが、とにかく大きな値を処理するときに再帰を使用しようとするべきではありません。

于 2010-12-21T08:54:57.477 に答える
1

この単純な関数でも、g++ 4.4.0 (mingw の下) で末尾再帰を実行できません。

static void f (int x)
  {
  if (x == 0) return ;
  printf ("%p\n", &x) ; // or cout in C++, if you prefer
  f (x - 1) ;
  }

-O3、、、C および C++ バリアント-O2を試しました。-fno-stack-protector末尾再帰はありません。

于 2011-01-25T21:56:10.507 に答える
0

私は2つのことを見ます。

  1. ifステートメントの return 呼び出しは、呼び出し後に解決する必要がある関数の現在の実行のスタック フレームに、 elseの分岐ターゲットを持ちます (これは、TCO の試みが実行中のスタックを上書きできないことを意味します)。フレームを使用するため、TCO が削減されます)

  2. numbers[]配列引数は可変長データ構造であり、TCO では同じスタック フレームが何らかの方法で使用されるため、TCO を防ぐこともできます。呼び出しが (あなたのもののように) 自己参照である場合、スタックで定義された変数 (またはローカルで定義された変数) を新しい呼び出しの値/参照で上書きします。末尾の呼び出しが別の関数に対するものである場合、スタック フレーム全体が新しい関数で上書きされます (TCO が A => B => C で実行できる場合、TCO はこれをメモリ内で A => C のように見せることができます)。実行中）。ポインターを試してみます。

C++ で何かをビルドしてから数か月が経過したため、テストを実行していませんが、それらの 1 つまたは両方が最適化を妨げていると思います。

于 2011-01-25T20:33:24.453 に答える
0

コードを次のように変更してみてください。

// Return 2 indexes from numbers that sum up to target.
struct result twoSum_Helper(int numbers[], int size, int target, int i, int j)
{
    if (numbers[i] + numbers[j] == target)
        return gen_Result(i, j, true);
    if (i >= (size - 1))
        return gen_Result(i, j, false);

    if(j >= size)
        i++; //call by value, changing i here does not matter
    return twoSum_Helper(numbers, size, target, i, i + 1);
}

編集：質問者からのコメントに従って不要なパラメータを削除しました

// Return 2 indexes from numbers that sum up to target.
struct result twoSum_Helper(int numbers[], int size, int target, int i)
{
    if (numbers[i] + numbers[i+1] == target || i >= (size - 1))
        return gen_Result(i, i+1, true);

    if(i+1 >= size)
        i++; //call by value, changing i here does not matter
    return twoSum_Helper(numbers, size, target, i);
}
于 2013-03-10T20:40:23.620 に答える
-2

末尾再帰は gcc でのみ最適化され、g++ では最適化されないという不満を他の人が聞いたことがあります。gcc を使用してみてください。

于 2013-03-10T20:09:32.007 に答える
-3

のコードはtwoSum_Helperそれ自体を呼び出しているので、アセンブリがまさにその出来事を示していることは驚くべきことではありません。これが再帰の要点です:-)したがって、これはg++とは何の関係もありません。

再帰ごとに新しいスタックフレームが作成され、デフォルトではスタックスペースが制限されています。スタックサイズを増やすことはできますが（Windowsではその方法がわかりません。UNIXではulimitコマンドが使用されます）、それはクラッシュを遅らせるだけです。

本当の解決策は、再帰を取り除くことです。たとえば、この質問とこの質問を参照してください。

于 2010-12-21T08:49:36.030 に答える