67

C++ で簡単な末尾再帰関数を教えてもらえますか?

末尾再帰が優れているのはなぜですか?

末尾再帰以外にどんな種類の再帰がありますか?

4

6 に答える 6

65

単純な末尾再帰関数:

unsigned int f( unsigned int a ) {
   if ( a == 0 ) {
      return a;
   }
   return f( a - 1 );   // tail recursion
}

末尾再帰は基本的に次の場合です。

  • 再帰呼び出しは 1 回だけです
  • その呼び出しは関数の最後のステートメントです

また、優れたコンパイラが再帰を削除してループに変換できるという意味を除いて、「より良い」わけではありません。これはより高速であり、スタックの使用量を確実に節約します。GCC コンパイラは、この最適化を行うことができます。

于 2010-04-22T19:09:47.497 に答える
44

C++ の末尾再帰は、C やその他の言語と同じように見えます。

void countdown( int count ) {
    if ( count ) return countdown( count - 1 );
}

末尾再帰 (および一般的な末尾呼び出し) では、末尾呼び出しを実行する前に、呼び出し元のスタック フレームをクリアする必要があります。プログラマーにとって、末尾再帰はループに似ていますが、 のreturnように機能しgoto first_line;ます。ただし、コンパイラはユーザーが何を行っているかを検出する必要があり、検出されない場合でも追加のスタック フレームが存在します。ほとんどのコンパイラはこれをサポートしていますgotoが、通常、ループ or を記述する方が簡単でリスクが低くなります。

非再帰的な末尾呼び出しは、ランダムな分岐 (goto他の関数の最初の行など) を有効にすることができます。これは、よりユニークな機能です。

returnC++ では、ステートメントのスコープ内に非自明なデストラクタを持つオブジェクトは存在できないことに注意してください。関数の終わりのクリーンアップでは、呼び出し先が呼び出し元に戻る必要があり、末尾呼び出しがなくなります。

また、(どの言語でも) 末尾再帰では、各ステップで関数の引数リストを介してアルゴリズムの状態全体を渡す必要があることに注意してください。(これは、次の呼び出しが開始される前に関数のスタック フレームを削除する必要があることから明らかです。ローカル変数にデータを保存することはできません。)さらに、末尾が返される前に、関数の戻り値に操作を適用することはできません。 .

int factorial( int n, int acc = 1 ) {
    if ( n == 0 ) return acc;
    else return factorial( n-1, acc * n );
}
于 2010-04-22T19:13:17.393 に答える
28

末尾再帰は、末尾呼び出しの特殊なケースです。末尾呼び出しは、呼び出された関数からの戻り時に実行する必要がある操作がないことをコンパイラが確認できる場所です。つまり、呼び出された関数の戻り値をそれ自体に変換します。コンパイラは、多くの場合、いくつかのスタック修正操作を実行してから、呼び出された関数の最初の命令のアドレスに (呼び出すのではなく) ジャンプできます。

これに関する優れた点の 1 つは、いくつかのリターン コールを排除することに加えて、スタックの使用量も削減できることです。一部のプラットフォームまたは OS コードでは、スタックがかなり制限される可能性があり、デスクトップの x86 CPU のような高度なマシンでは、このようにスタックの使用を減らすと、データ キャッシュのパフォーマンスが向上します。

末尾再帰は、呼び出された関数が呼び出し元の関数と同じである場合です。これはループに変えることができます。これは、上記のテール コール最適化のジャンプとまったく同じです。これは同じ関数 (呼び出し先と呼び出し元) であるため、ジャンプの前に行う必要があるスタックの修正が少なくなります。

以下は、コンパイラがループに変換するのがより困難な再帰呼び出しを行う一般的な方法を示しています。

int sum(int a[], unsigned len) {
     if (len==0) {
         return 0;
     }
     return a[0] + sum(a+1,len-1);
}

これは非常に単純なので、多くのコンパイラがおそらくそれを理解できるでしょう。

あなたがした場合：

static int sum_helper(int acc, unsigned len, int a[]) {
     if (len == 0) {
        return acc;
     }
     return sum_helper(acc+a[0], len-1, a+1);
}
int sum(int a[], unsigned len) {
     return sum_helper(0, len, a);
}

テールコールである両方の関数の呼び出しを利用できます。ここで、sum 関数の主な仕事は、値を移動し、レジスタまたはスタック位置をクリアすることです。sum_helper がすべての計算を行います。

質問でC++について言及したので、それについていくつか特別なことを述べます。C++ は、C にはないいくつかのことを隠します。これらのデストラクタのうち、テール コールの最適化を妨げる主なものは次のとおりです。

int boo(yin * x, yang *y) {
    dharma z = x->foo() + y->bar();
    return z.baz();
}

この例では、baz からの戻り後に z を破棄する必要があるため、baz への呼び出しは実際にはテール コールではありません。次のように、呼び出し中に変数が必要ない場合でも、C++ の規則により最適化がより困難になる可能性があると思います。

int boo(yin * x, yang *y) {
    dharma z = x->foo() + y->bar();
    int u = z.baz();
    return qwerty(u);
}

z は、ここで qwerty から戻った後に破棄する必要がある場合があります。

もう 1 つのことは暗黙の型変換です。これは C でも発生する可能性がありますが、C++ ではより複雑で一般的な可能性があります。例えば：

static double sum_helper(double acc, unsigned len, double a[]) {
     if (len == 0) {
        return acc;
     }
     return sum_helper(acc+a[0], len-1, a+1);
}
int sum(double a[], unsigned len) {
     return sum_helper(0.0, len, a);
}

ここで、sum_helper への sum の呼び出しは末尾呼び出しではありません。sum_helper は double を返し、sum はそれを int に変換する必要があるからです。

C++ では、すべての種類の異なる解釈を持つ可能性があるオブジェクト参照を返すことは非常に一般的であり、それぞれが異なる型変換になる可能性があります。たとえば、次のようになります。

bool write_it(int it) {
      return cout << it;
}

ここでは、最後のステートメントとして cout.operator<< への呼び出しが行われています。cout はそれ自体への参照を返します (これが、 << で区切られたリストに多くのものをつなぎ合わせることができる理由です)。これを bool として強制的に評価し、最終的に cout の別のメソッド operator bool( ）。この場合、この cout.operator bool() は末尾呼び出しとして呼び出すことができましたが、operator<< はできませんでした。

編集：

言及する価値のあることの 1 つは、C でテール コールの最適化が可能である主な理由は、呼び出された関数が戻り値を同じ場所に格納することをコンパイラが認識していることです。に格納されます。

于 2010-04-22T19:57:52.133 に答える
2

末尾再帰は、実際に同時に 2 つの問題に対処するためのトリックです。1 つ目は、実行する反復回数を知るのが難しい場合にループを実行することです。

これは単純な再帰で解決できますが、再帰呼び出しが何度も実行されることによるスタック オーバーフローという 2 つ目の問題が発生します。テール コールは、「コンピュート アンド キャリー」手法を伴う場合のソリューションです。

基本的な CS では、コンピューター アルゴリズムには不変条件と終了条件が必要であることを学びます。これは末尾再帰を構築するためのベースです。

  1. すべての計算は、引数の受け渡しで行われます。
  2. すべての結果を関数呼び出しに渡す必要があります。
  3. テール コールは最後のコールであり、終了時に発生します。

簡単に言えば、 function の戻り値に対して計算を行ってはなりません。

たとえば、10 のべき乗の計算を考えてみましょう。これは自明であり、ループによって記述できます。

次のように見えるはずです

template<typename T> T pow10(T const p, T const res =1)
{
return p ? res: pow10(--p,10*res);
}

これにより、実行が得られます。たとえば、4:

ret,p,res

-,4,1

-,3,10

-,2,100

-,1,1000

-,0,10000

10000、-、-

コンパイラがスタック ポインタを変更せずに値をコピーするだけでよく、末尾呼び出しが発生したときに結果を返すだけであることは明らかです。

末尾再帰は非常に重要です。なぜなら、既製のコンパイル時間評価を提供できるからです。たとえば、上記のようにすることができます。

template<int N,int R=1> struct powc10
{
int operator()() const
{
return  powc10<N-1, 10*R>()();
}
};

template<int R> struct powc10<0,R>
{
    
int operator()() const
{
return  R;
}

};

powc10<10>()()これは、コンパイル時に 10 乗を計算するために使用できます。

ほとんどのコンパイラにはネストされた呼び出しの制限があるため、末尾呼び出しのトリックが役立ちます。明らかに、メタ プログラミング ループがないため、再帰を使用する必要があります。

于 2015-11-30T02:32:35.620 に答える
1

C++ のコンパイラ レベルでは、末尾再帰は実際には存在しません。

末尾再帰を使用するプログラムを作成することはできますが、コンパイラ/インタープリター/言語をサポートすることによって実装される末尾再帰の利点を継承することはできません。たとえば、Scheme は末尾再帰の最適化をサポートしているため、基本的に再帰を反復に変更します。これにより、スタックオーバーフローに対してより高速で無敵になります。C++ にはそのようなものはありません。（少なくとも私が見たコンパイラはありません）

どうやら末尾再帰の最適化は MSVC++ と GCC の両方に存在します。詳細については、この質問を参照してください。

于 2010-04-22T19:13:23.157 に答える
0

ウィキペディアには末尾再帰に関する適切な記事があります。基本的に、末尾再帰は通常の再帰よりも優れています。反復ループに最適化するのは簡単であり、反復ループは一般に再帰関数呼び出しよりも効率的です。これは、ループがない関数型言語では特に重要です。

C++ の場合、末尾再帰を使用して再帰ループを記述できる場合は、最適化を改善できるため、それでも良いのですが、そのような場合は、通常、最初から反復的に実行できるため、ゲインはそれほど大きくありません。関数型言語であること。

于 2010-04-22T19:16:17.673 に答える