10

再帰的な別の関数fooBを呼び出すmain（）から関数fooAを呼び出しています。戻りたいときは、exit（1）を使い続けて実行を停止します。再帰ツリーが深いときに終了する正しい方法は何ですか？

再帰スタックを介して戻ることは、通常、私が構築したパーツソリューションをクリアし、それを実行したくないため、役に立たない場合があります。main（）からさらに多くのコードを実行したいと思います。

例外を使用できることを読みました。コードスニペットを取得できれば便利です。

4

2 に答える 2

14

のgotoある関数から別の関数に戻るステートメントは機能しません。Nikos C. は、行った呼び出しのそれぞれのスタック フレームを解放することを考慮していないことは正しいので、移動先の関数に到達すると、スタック ポインターは次のスタック フレームを指します。あなたがちょうどいた機能...いいえ、それはうまくいきません。同様に、アルゴリズムが完了したときに目的の関数を (直接または関数ポインターを介して間接的に) 単純に呼び出すことはできません。再帰アルゴリズムに飛び込む前のコンテキストに戻ることはありません。このようにシステムを設計することも考えられますが、本質的には、これを行うたびに、現在スタック上にあるものを「リーク」します (ヒープ メモリのリークとはまったく同じではありませんが、同様の効果です)。

いいえ、何らかの方法で呼び出し元のコンテキストに戻る必要があります。C++ でこれを行うには、次の 3 つの方法しかありません。

  1. 各関数から呼び出し元に戻り、呼び出しチェーンを順番にバックアップして、各関数を順番に終了します。
  2. 例外をスローし、再帰アルゴリズムを起動した直後の時点でそれをキャッチします (スタック上の各関数によって作成されたオブジェクトを規則正しく自動的に破棄します)。
  3. setjmp() & longjmp() を使用して、例外をスローしてキャッチするのと同様のことを行いますが、longjmp() を「スロー」してもスタック上のオブジェクトは破棄されません。そのようなオブジェクトがヒープ割り当てを所有している場合、それらの割り当てはリークされます。

オプション1を実行するには、再帰関数を作成して、解決策に到達すると、呼び出し元（同じ関数である可能性があります）に完了したことを示す何らかの兆候を返し、呼び出し元がその事実を認識して中継するようにする必要があります最終的に再帰アルゴリズムのすべてのスタックフレームが解放され、再帰アルゴリズムの最初の関数を呼び出した関数に戻るまで、呼び出し元に戻ることで呼び出し元に事実を伝えます (これは同じ関数である可能性があります)。

オプション 2 を実行するには、再帰アルゴリズムへの呼び出しを でラップし、try{...}その直後にcatch(){...}、予想されるスローされたオブジェクト (計算の結果である可能性があるか、呼び出し元に「やあ、私は完了したら、結果がどこにあるかがわかります」)。例：

try
{
    callMyRecursiveFunction(someArg);
}
catch( whateverTypeYouWantToThrow& result )
{
    ...do whatever you want to do with the result,
    including copy it to somewhere else...
}

...そして再帰関数では、結果を終了すると、次のようになります。

throw(whateverTypeYouWantToThrow(anyArgsItsConstructorNeeds));

オプション 3 を実行するには...

#include <setjmp.h>
static jmp_buf jmp; // could be allocated other ways; the longjmp() user just needs to have access to it.
    .
    .
    .
if (!setjmp(jmp)) // setjmp() returns zero 1st time, or whatever int value you send back to it with longjmp()
{
    callMyRecursiveFunction(someArg);
}

...そして再帰関数では、結果を終了すると、次のようになります。

longjmp(jmp, 1); // this passes 1 back to the setjmp().  If your result is an int, you
                 // could pass that back to setjmp(), but you can't pass zero back.

setjmp()/longjmp() を使用することの悪い点は、longjmp() を呼び出したときに、スタックに割り当てられたオブジェクトがまだスタック上に「生きている」場合、実行が setjmp() ポイントに戻り、デストラクタをスキップすることです。それらのオブジェクトのために。アルゴリズムが POD タイプのみを使用する場合、それは問題ではありません。また、アルゴリズムが使用する非 POD 型にヒープ割り当てが含まれていない場合も問題ではありません (例: frommalloc()またはnew）。アルゴリズムがヒープ割り当てを含む非 POD タイプを使用している場合、上記のオプション 1 と 2 でのみ安全です。しかし、アルゴリズムが setjmp()/longjmp() で問題ないという基準を満たしている場合、およびアルゴリズムが終了した時点で大量の再帰呼び出しに埋もれている場合は、setjmp()/longjmp() が最速の方法である可能性があります。最初の呼び出しコンテキストに。それがうまくいかない場合は、オプション 1 がおそらく速度の点で最善の策です。オプション 2 は便利に思えるかもしれませんが (各再帰呼び出しの開始時に条件チェックが不要になる可能性があります)、システムが自動的に呼び出しスタックをアンワインドすることに関連するオーバーヘッドが多少大きくなります。

通常、「例外的なイベント」 (非常にまれであると予想されるイベント) に対して例外を予約する必要があると言われていますが、コールスタックの巻き戻しに関連するオーバーヘッドがその理由です。古いコンパイラは setjmp()/longjmp() に似たものを使用して例外を実装していました ( try&の場所で setjmp() catch、 a の場所で longjmp() ) throw。そのようなオブジェクトがなくても、スタック上で破棄する必要があります。さらに、 に出くわすたびに、コンテキストがあった場合tryに備えてコンテキストを保存する必要があります。throw、そして例外が本当に例外的なイベントである場合、そのコンテキストの保存に費やされた時間は単に無駄になりました. 新しいコンパイラは、「ゼロ コスト例外」(別名テーブル ベースの例外) として知られるものを使用する可能性が高くなりました。これにより、世界中の問題がすべて解決されるように見えますが、そうではありません.に出くわすたびにコンテキストを保存する必要はなくなりましたがtry、 がthrow実行された場合、ランタイムが把握するために処理しなければならない大規模なテーブルに格納された情報のデコードに関連するさらに多くのオーバーヘッドが発生します。スタックを展開する場所に基づいてスタックを巻き戻す方法throwが検出され、ランタイム スタックの内容。したがって、例外は非常に便利ですが、無料ではありません。インターネット上には、それらがどれほど不当に高価であり、コードの速度がどれだけ遅くなるかについて人々が主張している多くのものが見つかります。彼らの主張を裏付けるデータ。引数から取り除かなければならないのは、例外がめったに発生しないと予想される場合、例外を使用することは素晴らしいことです。なぜなら、関数呼び出しを行うたびに「悪さ」をチェックする大量の条件から解放された、よりクリーンなインターフェイスとロジックが得られるからです。ただし、呼び出し元とその呼び出し先の間の通常の通信手段として例外を使用しないでください。

于 2012-12-09T04:49:37.307 に答える