1

そこで、2つの関数が相互に再帰的になるとどうなるかを想像する思考実験をいじっていました。そのようなものの1つは、両方の関数が無限ループに陥る可能性がある場合はどうなるかということです。

そのために、私はこの簡単な例を考えました。

#include <iostream>
#include <cstdlib>

int foo(int x);
int bar(int x);


int foo(int x)
{
    return bar(x + 1);
}

int bar(int x)
{
    return foo(x - 1);
}

int main(int argc, char **argv)
{
    if (argc > 1)
        std::cout << "The value is: " << foo(atoi(argv[1])) << std::endl;

    return 0;
}

興味深いことに、g ++でコンパイルした場合、これは実際にはまったく何も出力しません。-Oスイッチを使用してコンパイルすると、無限ループに陥ります。

考え？これは潜在的にコンパイラのバグですか、それとも予想されることですか？-O最適化の場合、foo（x）とbar（x）がxだけを返すことがわかります。

実際に呼び出しを「最適化」して、標準入力への「値は」の出力を完全に無視するとは思っていませんでした。

編集：GCC 4.5.0を使用してCygwinで、これをg ++ source.cpp（-O1 / 2/3）としてコンパイルしました。-OXバージョンは、実際にはスタックがオーバーフローすることなく無限にループします。

4

3 に答える 3

2

使用しているC++を指定しなかったので、C++0xの答えを示します。

これは実際、C++0xでは未定義の動作です。

C ++ 03を使用している場合の動作を完全に説明することはできませんが、スタックが最終的にオーバーフローするため、実際には実装に依存する動作の領域内にあります。ここで何か正気が起こることを期待するのはばか者の用事です。

于 2011-06-19T00:38:14.213 に答える
1

数学的な観点から、f （x）= b（x + 1）およびb（x）= f（x --1）は、 fおよびbを定義するのに十分ではありません。考えられる解決策の1つはf（x）= xおよびb（x）= x --1であり、もう1つはf（x）= 0およびg（x）= 0です（さらに多くの方法があります）。したがって、数学的には、関数が何を返す必要があるかという質問には答えがありません。計算の観点からは、状況はさらに悪化します。結局のところ、数学関数を定義しているのではなく、計算の実行方法を指定しているからです。foo(x - 1)foo()は、「の値をパラメータとして渡すときに関数で指定された計算を実行する」ことを意味しx - 1、同様にbar(x + 1)。したがって、各関数が無条件に他の関数を呼び出すように指示する場合、無限再帰が発生することを指定したことになります。他の人が述べたように、一部の言語（または言語バージョン）はこれを明確に定義された状況として扱い（望ましい結果はプログラムがハングすることです）、他の言語はそれを未定義の状況として扱います（つまり、コンパイラーは好きなことをするかもしれません） ）。

于 2011-06-19T00:55:38.407 に答える
0

再帰には停止条件がないため、無限ループに入るのは当然です。これらの関数が「ちょうどx」を返すというあなたの仮定は誤りです。彼らは二度と戻らないはずです。

コンパイラは、再帰を最適化するだけでは不十分です。

于 2011-06-19T00:31:58.643 に答える