5

再帰を使って関数を書きました。それをテストしている間、再帰がまだ実行されている間に、関数が明白な理由なしに強制終了されることが判明しました。

これをテストするために、私は無限再帰を作成しました。

私のPCでは、この関数は約2秒後に終了し、最後の出力は約327400です。最後の数値は常に同じではありません。

私はUbuntuLucidLynx、GCCコンパイラ、およびEclipseをIDEとして使用しています。誰かが問題が何であるか、そしてどうすればプログラムが終了するのを防ぐことができるかについての考えを持っているなら、私は本当に嬉しいです。

#include <iostream>

void rek(double x){
    std::cout << x << std::endl;
    rek(x + 1);
}

int main(int argc, char **argv) {
    rek(1);
}
4

8 に答える 8

5

スタックがオーバーフローしている可能性が高く、その時点でプログラムはすぐに強制終了されます。スタックの深さは、再帰できる量を常に制限します。その制限に達した場合は、アルゴリズムを変更する必要があることを意味します。

于 2011-05-18T14:03:02.317 に答える
3

で説明されているように、コードが永久に実行されることを期待するのは正しいと思います

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

gccが末尾再帰を実行している場合、コードはいつまでも実行できるはずです。私のマシンでは、-O3が実際にgccに末尾呼び出しを生成させ、実際にスタックをフラット化するように見えます。:-)

最適化フラグをO2またはO3に設定することをお勧めします。

于 2011-05-18T14:12:06.440 に答える
2

終了条件を提供していないため、スタック オーバーフロー (スタック領域の不足) が発生しています。

void rek(double x){
   if(x > 10)
      return;
   std::cout << x << std::endl;
   rek(x + 1);
}
于 2011-05-18T14:04:38.480 に答える
1

これが永遠に機能することを期待していますか？

そうではありません。ある時点で、スタックが不足します。

于 2011-05-18T14:03:36.317 に答える
1

無限再帰によるスタック オーバーフローを回避したい場合は、残念ながら、新しいアクティベーション レコードが常にスタックにプッシュされないように、スタックを変更するためにアセンブリを掘り下げる必要があります。オーバーフローを引き起こします。関数の最後で再帰呼び出しを行うため、これは、再帰が一般的な他の言語 (つまり、Lisp、Scheme、Haskell など) では、トレイル コールの最適化として呼び出されます。基本的に末尾呼び出しをループに変換することで、スタック オーバーフローを防ぎます。Cでは次のようになります（注：x86でgccでインラインアセンブリを使用しており、引数をintからに変更しましたdouble組み立てを簡単にするため。また、関数名の名前マングリングを避けるために、C++ から C に変更しました。最後に、各ステートメントの末尾にある "\n\t" は実際のアセンブリ コマンドではありませんが、gcc でのインライン アセンブリに必要です):

#include <stdio.h>

void rek(int x)
{
    printf("Value for x: %d\n", x);

    //we now duplicate the equvalent of `rek(x+1);` with tail-call optimization

    __asm("movl 8(%ebp), %eax\n\t"   //get the value of x off the stack
          "incl %eax\n\t"            //add 1 to the value of x
          "movl 4(%ebp), %ecx\n\t"   //save the return address on the stack
          "movl (%ebp), %edx\n\t"    //save the caller's activation record base pointer
          "addl $12, %ebp\n\t"       //erase the activation record
          "movl %ebp, %esp\n\t"      //reset the stack pointer
          "pushl %eax\n\t"           //push the new value of x on the stack for function call
          "pushl %ecx\n\t"           //push the return value back to the caller (i.e., main()) on the stack
          "movl %edx, %ebp\n\t"      //restore the old value of the caller's stack base pointer
          "jmp rek\n\t");            //jump to the start of rek()
}

int main()
{
    rek(1);
    printf("Finished call\n");  //<== we never get here

    return 0;
}

Ubuntu 10.04 で gcc 4.4.3 を使用してコンパイルすると、これはスタック オーバーフローのない無限ループでほとんど「永久に」実行されましたが、末尾呼び出しの最適化がないと、セグメンテーション フォールトですぐにクラッシュしました。このセクションのコメントから、__asmスタック アクティベーション レコード スペースがどのように「リサイクル」されているかがわかります。これにより、新しい呼び出しごとにスタックのスペースが使い果たされなくなります。これには、古いアクティベーション レコード (前の呼び出し元のアクティベーション レコードのベース ポインターと戻りアドレス) にキー値を保存し、それらを復元することが含まれますが、関数の次の再帰呼び出しのために引数が変更されます。

繰り返しますが、他の言語、主に関数型言語は、言語の基本機能として末尾呼び出しの最適化を実行します。したがって、Scheme/Lisp/etc の末尾呼び出し再帰関数。このタイプのスタック操作は、既存の関数の最後のステートメントとして新しい関数呼び出しが行われたときに内部で行われるため、スタックがオーバーフローすることはありません。

于 2011-05-18T15:37:01.423 に答える
1

これは、stackoverflow.com でのスタック オーバーフローの話です。;) 呼び出しスタックは制限されています (プロジェクト設定からカスタマイズできます) が、ある時点で、無限ループ呼び出しがあると、それを超えてプログラムが終了します。

于 2011-05-18T14:06:34.117 に答える
0

さて、無限再帰とスタックのオーバーフローを定義しました。これにより、アプリが強制終了されます。本当にすべての数字を印刷したい場合; 次にループを使用します。

int main(...)
{
   double x = 1;
   while (true)
   {
       std:cout << x << std::endl;
       x += 1;
   }
 }
于 2011-05-18T14:07:31.317 に答える
0

各再帰メソッドは終了条件を実装する必要があります。そうしないと、スタック オーバーフローが発生し、プログラムが終了します。

あなたの場合、関数に渡すパラメータに条件がないため、永久に実行され、最終的にクラッシュします。

于 2011-05-18T14:11:43.070 に答える