recursion - 再帰とは何ですか? また、いつ使用する必要がありますか?

Question

メーリングリストやオンラインディスカッションで定期的に取り上げられるトピックの 1 つは、コンピューターサイエンスの学位を取得することのメリット (またはメリットの欠如) です。否定派にとって何度も出てくる議論は、彼らは何年もコーディングをしており、再帰を一度も使用したことがないというものです。

質問は次のとおりです。

再帰とは
再帰はいつ使用しますか?
なぜ人々は再帰を使わないのですか?

score 86 · Accepted Answer

このスレッドには再帰の良い説明がたくさんあります。この答えは、ほとんどの言語で再帰を使用すべきではない理由についてです。*主要な命令型言語の実装の大部分（つまり、C、C ++、Basic、Pythonのすべての主要な実装）、Ruby、Java、およびC＃）の反復は、再帰よりも非常に望ましいです。

理由を確認するには、上記の言語が関数を呼び出すために使用する手順を実行してください。

関数の引数とローカル変数用のスペースがスタックに刻まれています
関数の引数がこの新しいスペースにコピーされます
コントロールが機能にジャンプします
関数のコードが実行されます
関数の結果は戻り値にコピーされます
スタックは前の位置に巻き戻されます
コントロールは、関数が呼び出された場所にジャンプして戻ります

これらのすべての手順を実行するには時間がかかります。通常、ループを繰り返すのにかかる時間よりも少し長くなります。ただし、実際の問題はステップ1にあります。多くのプログラムが起動すると、スタックに1つのメモリチャンクが割り当てられ、そのメモリが不足すると（多くの場合、再帰が原因であるとは限りません）、スタックオーバーフローが原因でプログラムがクラッシュします。

したがって、これらの言語では、再帰が遅くなり、クラッシュに対して脆弱になります。しかし、それを使用するためのいくつかの議論がまだあります。一般に、再帰的に記述されたコードは、読み方がわかれば、短く、少しエレガントになります。

言語実装者が使用できる末尾呼び出しの最適化と呼ばれる手法があり、スタックオーバーフローのいくつかのクラスを排除できます。簡潔に言えば、関数の戻り式が単に関数呼び出しの結果である場合、スタックに新しいレベルを追加する必要はなく、呼び出されている関数に現在のレベルを再利用できます。残念ながら、末尾呼び出しの最適化が組み込まれている命令型言語の実装はほとんどありません。

*再帰が大好きです。私のお気に入りの静的言語はループをまったく使用していません。再帰は何かを繰り返し行う唯一の方法です。再帰が調整されていない言語では、一般的に再帰が良い考えだとは思いません。

**ちなみに、マリオでは、ArrangeString関数の一般的な名前は「join」です。選択した言語にまだ実装されていない場合は驚きます。

score 63 · Accepted Answer

再帰の簡単な英語の例.

A child couldn't sleep, so her mother told her a story about a little frog,
    who couldn't sleep, so the frog's mother told her a story about a little bear,
         who couldn't sleep, so the bear's mother told her a story about a little weasel... 
            who fell asleep.
         ...and the little bear fell asleep;
    ...and the little frog fell asleep;
...and the child fell asleep.

score 49 · Accepted Answer

最も基本的なコンピューターサイエンスの意味では、再帰はそれ自体を呼び出す関数です。リンクされたリスト構造があるとします:

struct Node {
    Node* next;
};

そして、リンクされたリストの長さを知りたい場合は、再帰を使用してこれを行うことができます:

int length(const Node* list) {
    if (!list->next) {
        return 1;
    } else {
        return 1 + length(list->next);
    }
}

(もちろん、これは for ループでも実行できますが、概念の説明として役立ちます)

score 46 · Accepted Answer

関数が自分自身を呼び出してループを作成するときはいつでも、それは再帰です。何でもそうであるように、再帰には良い使い方と悪い使い方があります。

最も単純な例は、関数の最後の行がそれ自体への呼び出しである末尾再帰です。

int FloorByTen(int num)
{
    if (num % 10 == 0)
        return num;
    else
        return FloorByTen(num-1);
}

ただし、これは、より効率的な反復に簡単に置き換えることができるため、ほとんど意味のない、不十分な例です。結局のところ、再帰は関数呼び出しのオーバーヘッドに悩まされます。これは、上記の例では、関数自体の内部の操作と比較してかなりの量になる可能性があります。

したがって、反復ではなく再帰を行う全体的な理由は、呼び出しスタックを利用して巧妙なことを行うためです。たとえば、同じループ内で異なるパラメーターを使用して関数を複数回呼び出す場合、それは分岐を実現する方法です。古典的な例は、シェルピンスキーの三角形です。

ここに画像の説明を入力

コールスタックが 3 方向に分岐する再帰を使用して、これらの 1 つを非常に簡単に描画できます。

private void BuildVertices(double x, double y, double len)
{
    if (len > 0.002)
    {
        mesh.Positions.Add(new Point3D(x, y + len, -len));
        mesh.Positions.Add(new Point3D(x - len, y - len, -len));
        mesh.Positions.Add(new Point3D(x + len, y - len, -len));
        len *= 0.5;
        BuildVertices(x, y + len, len);
        BuildVertices(x - len, y - len, len);
        BuildVertices(x + len, y - len, len);
    }
}

繰り返しで同じことをしようとすると、達成するのにもっと多くのコードが必要になることがわかると思います。

その他の一般的な使用例には、階層のトラバース (Web サイトクローラー、ディレクトリ比較など) が含まれる場合があります。

結論

実際には、繰り返し分岐が必要な場合はいつでも再帰が最も理にかなっています。

score 27 · Accepted Answer

再帰は、分割統治の考え方に基づいて問題を解決する方法です。基本的な考え方は、元の問題をそれ自体の小さな (より簡単に解決できる) インスタンスに分割し、それらの小さなインスタンスを (通常は同じアルゴリズムを再度使用して) 解決し、最終的なソリューションに再構築するというものです。

標準的な例は、n の階乗を生成するルーチンです。n の階乗は、1 から n までのすべての数値を乗算して計算されます。C# での反復ソリューションは次のようになります。

public int Fact(int n)
{
  int fact = 1;

  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }

  return fact;
}

反復ソリューションは驚くべきことではなく、C# に慣れている人なら理解できるはずです。

再帰的な解は、n 番目の階乗が n * Fact(n-1) であることを認識することによって見つかります。別の言い方をすれば、特定の階乗数が何であるかを知っていれば、次の階乗数を計算できます。C# での再帰的なソリューションは次のとおりです。

public int FactRec(int n)
{
  if( n < 2 )
  {
    return 1;
  }

  return n * FactRec( n - 1 );
}

この関数の最初の部分はBase Case (または Guard Clause) と呼ばれ、アルゴリズムが永久に実行されるのを防ぎます。関数が 1 以下の値で呼び出されるたびに、値 1 を返すだけです。2 番目の部分はより興味深いもので、Recursive Stepとして知られています。ここでは、わずかに変更されたパラメーター (1 だけデクリメント) を使用して同じメソッドを呼び出し、その結果に n のコピーを掛けます。

最初にこれに遭遇したとき、これは一種の混乱を招く可能性があるため、実行時にどのように機能するかを調べることは有益です. FactRec(5) を呼び出すとします。ルーチンに入りますが、基本ケースでは取り上げられないため、次のようになります。

// In FactRec(5)
return 5 * FactRec( 5 - 1 );

// which is
return 5 * FactRec(4);

パラメータ 4 を指定してメソッドを再入力すると、ガード句によって停止されないため、最終的には次のようになります。

// In FactRec(4)
return 4 * FactRec(3);

この戻り値を上記の戻り値に代入すると、

// In FactRec(5)
return 5 * (4 * FactRec(3));

これにより、最終的なソリューションに到達する方法の手がかりが得られるはずです。そのため、各ステップをすばやく追跡して示します。

return 5 * (4 * FactRec(3));
return 5 * (4 * (3 * FactRec(2)));
return 5 * (4 * (3 * (2 * FactRec(1))));
return 5 * (4 * (3 * (2 * (1))));

その最終的な置換は、基本ケースがトリガーされたときに発生します。この時点で、そもそも階乗の定義に直接等しい、解くべき単純な代数公式が得られました。

メソッドを呼び出すたびに、ベースケースがトリガーされるか、パラメーターがベースケースに近い同じメソッドが呼び出される (再帰呼び出しと呼ばれることが多い) ことに注意してください。そうでない場合、メソッドは永久に実行されます。

score 12 · Accepted Answer

再帰は、自分自身を呼び出す関数で問題を解決しています。これの良い例は、階乗関数です。階乗は、たとえば 5 の階乗が 5 * 4 * 3 * 2 * 1 である数学の問題です。この関数は、正の整数について C# でこれを解決します (テストされていません - バグがある可能性があります)。

public int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}

score 9 · Accepted Answer

再帰とは、問題の小さなバージョンを解決し、その結果と他の計算を使用して元の問題に対する答えを定式化することによって、問題を解決する方法を指します。多くの場合、小さなバージョンを解決する過程で、メソッドは問題のさらに小さなバージョンを解決し、解決するのが簡単な「基本ケース」に到達するまで続きます。

たとえば、数値の階乗を計算するには、次のようXに表すことができX times the factorial of X-1ます。したがって、メソッドはの階乗を見つけるために「再帰」し、X-1得られたものを乗算しXて最終的な答えを出します。もちろん、の階乗を見つけるには、X-1まずの階乗を計算しますX-2。基本ケースは whenXが 0 または 1 であり、その場合は1sinceを返すことがわかってい0! = 1! = 1ます。

score 9 · Accepted Answer

古いよく知られた問題を考えてみましょう:

数学では、2 つ以上のゼロ以外の整数の最大公約数(gcd) は、数値を割り切れる正の最大の整数です。

gcd の定義は驚くほど単純です。

gcd精細

ここで、mod はモジュロ演算子(つまり、整数除算後の剰余) です。

英語では、この定義は、任意の数とゼロの最大公約数はその数であり、2 つの数値mとnの最大公約数はnとmをnで割った余りの最大公約数であると述べています。

これが機能する理由を知りたい場合は、ユークリッドアルゴリズムに関するウィキペディアの記事を参照してください。

例として gcd(10, 8) を計算してみましょう。各ステップは、その直前のステップと同じです。

gcd(10, 8)
gcd(10, 10 mod 8)
gcd(8, 2)
gcd(8, 8 mod 2)
gcd(2,0)
2

最初のステップでは、8 はゼロに等しくないため、定義の 2 番目の部分が適用されます。10 mod 8 = 2 は、8 が 10 に 1 回入り、剰余が 2 であるためです。手順 5 では、2 番目の引数が 0 であるため、答えは 2 です。

gcd が等号の左右両方にあることに気付きましたか? 数学者は、定義している式がその定義内で再帰するため、この定義は再帰的であると言うでしょう。

再帰的な定義は洗練されている傾向があります。たとえば、リストの合計の再帰的な定義は次のとおりです。

sum l =
    if empty(l)
        return 0
    else
        return head(l) + sum(tail(l))

whereheadはリストの最初の要素で、はリストtailの残りの要素です。sum最後にその定義内で繰り返されることに注意してください。

代わりにリスト内の最大値を好むかもしれません:

max l =
    if empty(l)
        error
    elsif length(l) = 1
        return head(l)
    else
        tailmax = max(tail(l))
        if head(l) > tailmax
            return head(l)
        else
            return tailmax

非負の整数の乗算を再帰的に定義して、一連の加算に変換できます。

a * b =
    if b = 0
        return 0
    else
        return a + (a * (b - 1))

掛け算を一連の足し算に変換することが意味をなさない場合は、いくつかの簡単な例を拡張して、それがどのように機能するかを確認してください。

マージソートには素敵な再帰的定義があります:

sort(l) =
    if empty(l) or length(l) = 1
        return l
    else
        (left,right) = split l
        return merge(sort(left), sort(right))

何を探すべきかを知っていれば、再帰的な定義はどこにでもあります。これらの定義のすべてが、gcd(m, 0) = m のように非常に単純な基本ケースを持っていることに注意してください。再帰的なケースは、問題を少しずつ減らして簡単な答えにたどり着きます。

この理解により、ウィキペディアの再帰に関する記事にある他のアルゴリズムを理解できるようになりました。

score 8 · Accepted Answer

自分自身を呼び出す関数
関数を (簡単に) 単純な操作と、問題の小さな部分に対する同じ関数に分解できる場合。むしろ、これは再帰の良い候補になると言わざるを得ません。
彼らはそうします！

標準的な例は、次のような階乗です。

int fact(int a) 
{
  if(a==1)
    return 1;

  return a*fact(a-1);
}

一般に、再帰は必ずしも高速ではなく (再帰関数は小さい傾向があるため、関数呼び出しのオーバーヘッドが高くなる傾向があります。上記を参照)、いくつかの問題が発生する可能性があります (スタックオーバーフローはありますか?)。自明ではないケースでは「正しく」取得するのが難しい傾向があると言う人もいますが、私はそれを受け入れません. 状況によっては、再帰が最も理にかなっており、特定の関数を記述する最もエレガントで明確な方法です。一部の言語は再帰的なソリューションを優先し、それらをさらに最適化することに注意してください (LISP が思い浮かびます)。

score 6 · Accepted Answer

再帰関数は、自分自身を呼び出す関数です。これを使用する最も一般的な理由は、ツリー構造をトラバースすることです。たとえば、チェックボックス付きの TreeView (新しいプログラムのインストール、「インストールする機能の選択」ページを考えてください) がある場合、次のような「すべてをチェック」ボタンが必要になる場合があります (疑似コード):

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

function checkRecursively(Node n) {
    n.Checked = True;
    foreach ( n.Children as child ) {
        checkRecursively(child);
    }
}

したがって、checkRecursively は最初に渡されたノードをチェックし、次にそのノードの各子に対して自身を呼び出していることがわかります。

再帰には少し注意が必要です。無限再帰ループに入ると、Stack Overflow 例外が発生します :)

適切な場合に、人々がそれを使用すべきではない理由が思いつきません。状況によっては便利ですが、そうでない場合もあります。

これは興味深い手法であるため、一部のコーダーは正当な理由もなく、必要以上に頻繁に使用してしまう可能性があると思います。これにより、一部のサークルでは再帰に悪い名前が付けられました。

score 5 · Accepted Answer

再帰は、それ自体を直接または間接的に参照する式です。

簡単な例として再帰的頭字語を考えてみましょう。

GNUはGNUのNotUnixの略です
PHPはPHPの略です：ハイパーテキストプリプロセッサ
YAMLはYAMLAin'tMarkupLanguageの略です
WINEはWineIsNotaEmulatorの略です
VISAはVisaInternationalServiceAssociationの略です

ウィキペディアの他の例

score 4 · Accepted Answer

再帰は、私が「フラクタル問題」と呼んでいるもので最もうまく機能します。この問題では、大きなものの小さなバージョンで構成された大きなものを扱っており、それぞれが大きなもののさらに小さなバージョンなどです。ツリーや入れ子になった同一の構造などをトラバースまたは検索する必要がある場合は、再帰の良い候補となる問題があります。

人々は多くの理由で再帰を避けます:

ほとんどの人 (私自身を含む) は、関数型プログラミングではなく、手続き型またはオブジェクト指向プログラミングでプログラミングの経験を積んでいます。そのような人々には、反復的なアプローチ (通常はループを使用) がより自然に感じられます。
手続き型またはオブジェクト指向プログラミングでプログラミングの経験を積んだ私たちは、エラーが発生しやすいため、再帰を避けるようによく言われてきました。
再帰は遅いとよく言われます。ルーチンの呼び出しと戻りを繰り返すと、スタックのプッシュとポップが大量に発生し、ループよりも遅くなります。一部の言語は他の言語よりもこれをうまく処理すると思いますが、それらの言語は、手続き型またはオブジェクト指向が支配的なパラダイムである言語ではない可能性が高いです。
私が使用した少なくともいくつかのプログラミング言語では、スタックがそれほど深くないため、特定の深さを超えた場合は再帰を使用しないという推奨事項を聞いたことを覚えています。

score 4 · Accepted Answer

簡単な例を次に示します。セット内の要素の数です。(物事を数えるにはもっと良い方法がありますが、これは単純な再帰的な例です。)

まず、2 つのルールが必要です。

セットが空の場合、セット内のアイテムの数はゼロです (当たり前!)。
セットが空でない場合、カウントは、1 つのアイテムが削除された後のセット内のアイテムの数に 1 を加えたものになります。

[xxx] のようなセットがあるとします。アイテムがいくつあるか数えてみましょう。

セットは空ではない [xxx] であるため、ルール 2 を適用します。アイテムの数は、[xx] 内のアイテムの数に 1 を加えたものです (つまり、アイテムを削除しました)。
セットは [xx] であるため、ルール 2 を再度適用します: 1 + [x] 内のアイテムの数。
セットは [x] であり、ルール 2 に一致します: one + [] 内のアイテムの数。
セットは [] になり、ルール 1 に一致します: カウントはゼロです!
ステップ 4 (0) の答えがわかったので、ステップ 3 (1 + 0) を解くことができます。
同様に、ステップ 3 (1) の答えがわかったので、ステップ 2 (1 + 1) を解くことができます。
最後に、ステップ 2 (2) の答えがわかったので、ステップ 1 (1 + 2) を解き、[xxx] 内のアイテムの数を取得します。これは 3 です。万歳!

これは次のように表すことができます。

count of [x x x] = 1 + count of [x x]
                 = 1 + (1 + count of [x])
                 = 1 + (1 + (1 + count of []))
                 = 1 + (1 + (1 + 0)))
                 = 1 + (1 + (1))
                 = 1 + (2)
                 = 3

再帰的なソリューションを適用する場合、通常、少なくとも 2 つのルールがあります。

基本は、すべてのデータを「使い果たした」ときに何が起こるかを示す単純なケースです。これは通常、「処理するデータが不足している場合、答えは X です」のバリエーションです。
まだデータがある場合に何が起こるかを示す再帰規則。これは通常、「データセットを小さくするために何かを行い、小さいデータセットにルールを再適用する」というある種のルールです。

上記を疑似コードに変換すると、次のようになります。

numberOfItems(set)
    if set is empty
        return 0
    else
        remove 1 item from set
        return 1 + numberOfItems(set)

他の人がカバーすると確信している、より多くの有用な例 (たとえば、ツリーのトラバース) があります。

score 4 · Accepted Answer

再帰ステートメントは、入力と既に実行したことの組み合わせとして、次に何をするかのプロセスを定義するステートメントです。

たとえば、階乗を取ります。

factorial(6) = 6*5*4*3*2*1

しかし、 factorial(6) も次のようになることは簡単にわかります。

6 * factorial(5) = 6*(5*4*3*2*1).

したがって、一般的に：

factorial(n) = n*factorial(n-1)

もちろん、再帰の厄介な点は、既に行ったことの観点から物事を定義したい場合は、開始する場所が必要だということです。

この例では、factorial(1) = 1 を定義して特別なケースを作成しています。

下から順に見ていきます。

factorial(6) = 6*factorial(5)
                   = 6*5*factorial(4)
                   = 6*5*4*factorial(3) = 6*5*4*3*factorial(2) = 6*5*4*3*2*factorial(1) = 6*5*4*3*2*1

factorial(1) = 1 を定義したので、「底」に到達します。

一般に、再帰的手続きには次の 2 つの部分があります。

1) 再帰部分。これは、同じ手順を介して「既に行った」ことと組み合わせた新しい入力に関して、いくつかの手順を定義します。(つまりfactorial(n) = n*factorial(n-1))

2) 開始する場所を与えることにより、プロセスが永久に繰り返されないようにする基本部分 (つまりfactorial(1) = 1)

最初は理解するのに少し混乱するかもしれませんが、たくさんの例を見るだけですべてがまとまるはずです。概念をより深く理解したい場合は、数学的帰納法を勉強してください。また、再帰呼び出しを最適化する言語と最適化しない言語があることに注意してください。注意しないと、非常に遅い再帰関数を作成するのは非常に簡単ですが、ほとんどの場合、パフォーマンスを向上させるためのテクニックもあります。

お役に立てれば...

score 4 · Accepted Answer

私はこの定義が気に入っています。
再帰では、ルーチンは問題自体の小さな部分を解決し、問題を小さな部分に分割してから、小さな部分のそれぞれを解決するためにそれ自体を呼び出します。

私はまた、Steve McConnell の Code Complete での再帰に関する議論も好きです。彼は、再帰に関するコンピューターサイエンスの本で使用されている例を批判しています。

階乗またはフィボナッチ数に再帰を使用しないでください

コンピューターサイエンスの教科書の問題の 1 つは、再帰のばかげた例を示していることです。典型的な例は、階乗の計算またはフィボナッチ数列の計算です。再帰は強力なツールであり、これらのケースのいずれかで使用するのは本当にばかげています。私の下で働いていたプログラマーが再帰を使って階乗を計算していたら、私は他の誰かを雇うでしょう。

これは提起するのに非常に興味深い点であり、再帰がしばしば誤解される理由かもしれないと思いました。

編集：これはDavの回答を掘り下げたものではありません-これを投稿したとき、私はその返信を見ていませんでした

score 3 · Accepted Answer

まあ、それはあなたが持っているかなりまともな定義です。ウィキペディアにも適切な定義があります。そこで、別の (おそらくもっと悪い) 定義を追加します。

人々が「再帰」に言及するとき、彼らは通常、その作業が完了するまで自分自身を繰り返し呼び出す関数について話している。再帰は、データ構造の階層をトラバースするときに役立ちます。

score 3 · Accepted Answer

3

例: 階段の再帰的定義は次のとおりです: 階段は以下で構成されます:

于 2010-05-04T13:34:56.237 に答える

score 2 · Accepted Answer

平易な英語で: 3 つのことができると仮定します。

りんごを1つとる
集計マークを書き留める
集計マークを数える

目の前のテーブルにたくさんのりんごがあり、りんごがいくつあるか知りたいとします。

start
  Is the table empty?
  yes: Count the tally marks and cheer like it's your birthday!
  no:  Take 1 apple and put it aside
       Write down a tally mark
       goto start

完了するまで同じことを繰り返すプロセスは、再帰と呼ばれます。

これがあなたが探している「平易な英語」の答えであることを願っています!

score 2 · Accepted Answer

解決した問題を再帰するには: 何もしないで、完了です。
未解決の問題を再帰するには: 次のステップを実行してから、残りを再帰します。

score 2 · Accepted Answer

再帰関数は、それ自体への呼び出しを含む関数です。再帰構造体は、それ自体のインスタンスを含む構造体です。この 2 つを再帰クラスとして組み合わせることができます。再帰アイテムの重要な部分は、それ自体のインスタンス/呼び出しが含まれていることです。

向かい合った 2 つの鏡を考えてみましょう。私たちは、それらが生み出すきちんとした無限の効果を見てきました. 各反射は、ミラーの別のインスタンス内に含まれるミラーのインスタンスなどです。それ自体の反射を含むミラーは再帰です。

二分探索木は、再帰の良いプログラミング例です。この構造は再帰的で、各ノードにはノードの 2 つのインスタンスが含まれています。二分探索木で動作する関数も再帰的です。

score 2 · Accepted Answer

これは古い質問ですが、論理的な観点から (つまり、アルゴリズムの正確性の観点やパフォーマンスの観点からではなく) 回答を追加したいと思います。

仕事で Java を使用していますが、Java はネストされた関数をサポートしていません。そのため、再帰を実行したい場合は、外部関数を定義する必要がある場合があります (これは、コードが Java の官僚的な規則に違反しているためにのみ存在します)、またはコードを完全にリファクタリングする必要がある場合があります (これは本当にやりたくないことです)。

したがって、私はしばしば再帰を避け、代わりにスタック操作を使用します。これは、再帰自体が本質的にスタック操作であるためです。

score 1 · Accepted Answer

「私がハンマーを持っているなら、すべてを釘のように見せてください。」

再帰は、大きな問題の問題解決戦略であり、すべてのステップで、毎回同じハンマーで「2つの小さなものを1つの大きなものに変える」だけです。

例

あなたの机が1024枚の紙のまとまりのない混乱で覆われていると仮定します。再帰を使用して、混乱から1つのきちんとしたきれいな紙のスタックをどのように作成しますか？

分割：すべてのシートを広げて、各「スタック」に1枚のシートを配置します。
征服：
1. 各シートを他のシートの上に置いて、周りを回ってください。これで2つのスタックができました。
2. 各2スタックを別の2スタックの上に置いて回ります。これで、4つのスタックができました。
3. 各4スタックを別の4スタックの上に置いて回ります。これで8つのスタックができました。
4. ... 延々と ...
5. これで、1024枚の巨大なスタックが1つできました。

すべてを数えることを除けば、これは非常に直感的であることに注意してください（厳密には必要ありません）。実際には、1枚のスタックまで下がらない場合もありますが、それでも機能します。重要な部分はハンマーです。腕を使って、いつでも一方のスタックをもう一方のスタックの上に置いて、より大きなスタックを作成できます。どちらのスタックがどれほど大きいかは（理由の範囲内で）関係ありません。

score 1 · Accepted Answer

すべてのオプションが使用されるように、無期限に何度も何度も行う方法です。

たとえば、HTML ページのすべてのリンクを取得する場合は、1 ページ目のすべてのリンクを取得するときに、最初のページにある各リンクのすべてのリンクを取得する必要があるため、再帰が必要になります。次に、新しいページへの各リンクに対して、それらのリンクなどが必要になります...つまり、それは内部から自分自身を呼び出す関数です。

これを行うときは、いつ停止するかを知る方法が必要です。そうしないと、無限ループになるため、整数パラメーターを関数に追加してサイクル数を追跡します。

c# では、次のようになります。

private void findlinks(string URL, int reccursiveCycleNumb)    {
   if (reccursiveCycleNumb == 0)
        {
            return;
        }

        //recursive action here
        foreach (LinkItem i in LinkFinder.Find(URL))
        {
            //see what links are being caught...
            lblResults.Text += i.Href + "<BR>";

            findlinks(i.Href, reccursiveCycleNumb - 1);
        }

        reccursiveCycleNumb -= reccursiveCycleNumb;
}

score 1 · Accepted Answer

プログラミングに適用される再帰は、基本的に、タスクを達成するために異なるパラメーターを使用して、独自の定義内 (それ自体内) から関数を呼び出すことです。

score 1 · Accepted Answer

ツリー構造があるときはいつでも使用したい。XML の読み取りに非常に役立ちます。

score 1 · Accepted Answer

再帰は、関数、セット、またはアルゴリズムをそれ自体で定義する手法です。

例えば

n! = n(n-1)(n-2)(n-3)...........*3*2*1

今では次のように再帰的に定義できます:-

n! = n(n-1)!   for n>=1

プログラミング用語では、特定の条件が満たされるまで、関数またはメソッドが繰り返し自身を呼び出すとき、このプロセスは再帰と呼ばれます。ただし、終了条件が必要であり、関数またはメソッドが無限ループに入ってはなりません。

score 1 · Accepted Answer

非常に多くの問題は、次の 2 種類の部分で考えることができます。

見るだけで解決できる初歩的なものであるベースケースと、
小さな断片 (初歩的またはその他) からより大きな問題を構築する再帰的なケース。

では、再帰関数とは何ですか？それは、直接的または間接的に、それ自体に関して定義された関数がある場所です。わかりました、それが上記の種類の問題に対して賢明であることに気付くまでは、それはばかげているように聞こえます: 基本ケースを直接解決し、再帰呼び出しを使用して内部に埋め込まれた問題の小さな部分を解決することにより、再帰ケースを処理します。

再帰 (または再帰に非常によく似た何か) が必要な場所の真に古典的な例は、ツリーを扱っている場合です。ツリーの葉は基本ケースで、枝は再帰ケースです。(疑似 C で)

struct Tree {
    int leaf;
    Tree *leftBranch;
    Tree *rightBranch;
};

これを順番に出力する最も簡単な方法は、再帰を使用することです。

function printTreeInOrder(Tree *tree) {
    if (tree->leftBranch) {
        printTreeInOrder(tree->leftBranch);
    }
    print(tree->leaf);
    if (tree->rightBranch) {
        printTreeInOrder(tree->rightBranch);
    }
}

透明度が高いので、それが機能することは簡単にわかります。(非再帰的な同等のものはかなり複雑で、処理するもののリストを管理するためにスタック構造を内部的に必要とします。) もちろん、誰も循環接続を行っていないと仮定します。

数学的に、再帰が飼いならされていることを示す秘訣は、引数のサイズのメトリックを見つけることに集中することです。ツリーの例では、最も簡単なメトリックは、現在のノードの下にあるツリーの最大の深さです。葉ではゼロです。その下に葉しかない分岐では、それは 1 つです。次に、ツリーを処理するために関数が呼び出される引数のサイズに厳密に順序付けられたシーケンスがあることを単純に示すことができます。再帰呼び出しへの引数は、全体的な呼び出しへの引数よりもメトリックの意味で常に「小さい」です。厳密に減少するカーディナルメトリックを使用すると、並べ替えられます。

無限再帰も可能です。これは厄介で、多くの言語ではスタックが爆発するため機能しません。（それが機能する場合、言語エンジンは、関数が何らかの形で返されないため、スタックの保持を最適化できると判断している必要があります。一般的にトリッキーなことです。末尾再帰は、これを行う最も簡単な方法です.)

score 1 · Accepted Answer

基本的に、データ型の各ケースのケースを持つ switch-statement で構成されている場合、アルゴリズムはデータ型で構造的再帰を示します。

たとえば、型を扱っているとき

  tree = null 
       | leaf(value:integer) 
       | node(left: tree, right:tree)

構造再帰アルゴリズムは次の形式になります。

 function computeSomething(x : tree) =
   if x is null: base case
   if x is leaf: do something with x.value
   if x is node: do something with x.left,
                 do something with x.right,
                 combine the results

これは、データ構造で機能するアルゴリズムを記述する最も明白な方法です。

ここで、ペアノの公理を使用して定義された整数 (まあ、自然数) を見ると、

 integer = 0 | succ(integer)

整数の構造再帰アルゴリズムは次のようになります。

 function computeSomething(x : integer) =
   if x is 0 : base case
   if x is succ(prev) : do something with prev

あまりにも有名な階乗関数は、この形式の最も自明な例です。

score 1 · Accepted Answer

コンピューティングにおける再帰は、単一の関数 (メソッド、プロシージャ、またはブロック) 呼び出しからの通常の戻りに続く結果または副作用を計算するために使用される手法です。

再帰関数は、定義上、終了条件または満たされていない条件に応じて、直接または間接的に (他の関数を介して) 自分自身を呼び出す機能を備えている必要があります。終了条件が満たされた場合、特定の呼び出しは呼び出し元に戻ります。これは、最初の呼び出しが返されるまで続き、その時点で目的の結果または副作用が利用可能になります。

例として、Scala でクイックソートアルゴリズムを実行する関数を次に示します ( Wikipedia の Scala エントリからコピー) 。

def qsort: List[Int] => List[Int] = {
  case Nil => Nil
  case pivot :: tail =>
    val (smaller, rest) = tail.partition(_ < pivot)
    qsort(smaller) ::: pivot :: qsort(rest)
}

この場合、終了条件は空のリストです。

score 1 · Accepted Answer

再帰とは、メソッドが自分自身を呼び出して特定のタスクを実行できるようにするプロセスです。コードの冗長性を減らします。ほとんどの再帰関数またはメソッドには、再帰呼び出しを中断する条件が必要です。つまり、条件が満たされた場合に再帰呼び出しを停止します。これにより、無限ループの作成が防止されます。すべての関数が再帰的な使用に適しているわけではありません。

score 1 · Accepted Answer

再帰とは平易な英語で、何かを何度も繰り返すことを意味します。

プログラミングの 1 つの例は、関数自体を呼び出すことです。

数値の階乗を計算する次の例を見てください。

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}

score 1 · Accepted Answer

ねえ、私の意見が誰かに同意する場合は申し訳ありませんが、再帰を平易な英語で説明しようとしています.

ジャック、ジョン、モーガンの 3 人のマネージャーがいるとします。ジャックは 2 人のプログラマー、ジョン - 3 とモーガン - 5 を管理しています。あなたはすべてのマネージャーに 300 ドルを与え、その費用を知りたいと考えています。答えは明らかですが、Morgan-s の従業員のうち 2 人が管理職でもある場合はどうなるでしょうか。

ここに再帰が来ます。階層の最上位から開始します。夏の費用は0ドルです。ジャックから始めて、従業員としてマネージャーがいるかどうかを確認します。それらのいずれかが見つかった場合は、従業員としてマネージャーがいるかどうかなどを確認してください。マネージャーを見つけるたびに、夏の費用に 300 ドルを追加します。ジャックが終わったら、ジョンと彼の従業員、そしてモーガンに行きます。

何人のマネージャーがいて、どれだけの予算を費やすことができるかはわかっていても、回答を得るまでにどれくらいのサイクルが必要かはわかりません。

再帰は、それぞれ親と子と呼ばれる枝と葉を持つツリーです。再帰アルゴリズムを使用する場合、多かれ少なかれ意識的にデータからツリーを構築しています。

score 1 · Accepted Answer

1

関数自体を呼び出すか、独自の定義を使用します。

于 2010-05-04T13:59:55.677 に答える

score 1 · Accepted Answer

再帰とは、それ自体を使用する操作がある場合です。おそらく停止点があるでしょう。さもなければ、それは永遠に続くでしょう。

辞書で単語を調べたいとしましょう。「ルックアップ」と呼ばれる操作を自由に使用できます。

あなたの友達は、「今なら本当にプリンをスプーンで食べられるよ！」と言います。彼が何を意味するのかわからないので、辞書で「スプーン」を調べると、次のようになります。

スプーン：名詞 - 端に丸いスクープが付いた道具。Spoon: 動詞 - 何かにスプーンを使うこと Spoon: 動詞 - 後ろから抱きしめる

さて、あなたは英語が本当に苦手なので、これは正しい方向を示していますが、もっと情報が必要です. そこで、「道具」と「抱きしめる」を選択して、さらに情報を探します。

Cuddle: 動詞 - 寄り添う Utensil: 名詞 - 道具、多くの場合、食器

おい！あなたは寄り添うことが何であるかを知っています、そしてそれはプリンとは何の関係もありません. また、プリンは食べるものであることも知っているので、今では理にかなっています。あなたの友達はスプーンでプリンを食べたいに違いない。

わかりました、わかりました、これは非常に不十分な例でしたが、再帰の 2 つの主要な部分を (おそらく不十分に) 示しています。1) それは自分自身を使用します。この例では、単語を理解するまで意味のある単語を調べたことはありません。それは、より多くの単語を調べることを意味する可能性があります。これはポイント 2 につながります。2) どこかで停止します。ある種のベースケースが必要です。そうしないと、辞書内のすべての単語を検索することになり、おそらくあまり役に立ちません。私たちの基本的なケースは、あなたが以前に理解していたことと理解していなかったことを関連付けるのに十分な情報を得たというものでした。

与えられた従来の例は階乗で、5 階乗は 1*2*3*4*5 (120) です。基本ケースは 0 (場合によっては 1) です。したがって、任意の整数 n に対して、次のようにします。

n は 0 ですか? それ以外の場合は 1 を返し、n * (n-1 の階乗) を返します

4 の例でこれを行いましょう (事前に 1*2*3*4 = 24 であることがわかっています)。

4 の階乗 ... 0 ですか? いいえ、4 * 3 の階乗でなければなりませんが、3 の階乗とは何ですか? それは 3 * 2 の階乗 2 の階乗は 2 * 1 の階乗 1 の階乗は 1 * 0 の階乗そして私たちは 0 の階乗を知っています! :-D 1 です。1 の階乗は 1 * 0 の階乗であり、これは 1 でした... 1*1 = 2 の 1 階乗は 2 * 1 の階乗であり、1 でした... 2* の定義です1 = 2 の 3 の階乗は 3 * 2 の階乗で、これは 2 でした... 3*2 = 6 の 4 の階乗 (ついに!!) は 4 * 3 の階乗で、これは 6 でした... 4*6 は24

階乗は、「基本ケース、およびそれ自体を使用する」という単純なケースです。

ここで、まだ階乗の 4 に取り組んでいることに注意してください。同様に、辞書で調べるあいまいな単語を見つけた場合、慣れ親しんだつながりが見つかるまで、他の単語を調べて文脈の手がかりを探す必要があるかもしれません。再帰的メソッドは、処理に時間がかかる場合があります。ただし、正しく使用して理解すれば、複雑な作業が驚くほど簡単になります。

score 1 · Accepted Answer

再帰の最も単純な定義は「自己参照」です。自分自身を参照する関数、つまり自分自身を呼び出す関数は再帰的です。心に留めておくべき最も重要なことは、再帰関数には「基本ケース」が必要であるということです。つまり、true の場合はそれ自体を呼び出さず、再帰を終了するという条件です。そうしないと、無限再帰になります。

再帰 http://cart.kolix.de/wp-content/uploads/2009/12/infinite-recursion.jpg

score 0 · Accepted Answer

再帰を使用します。それはCSの学位を持っていることと何の関係がありますか...（ちなみに、私は知りません）

私が見つけた一般的な用途：

サイトマップ- ドキュメントルートから始まるファイルシステムを再帰します。
スパイダー- Web サイトをクロールして、電子メールアドレスやリンクなどを見つけます。
?

score 0 · Accepted Answer

マリオ、なぜその例で再帰を使用したのか理解できません.各エントリを単純にループしないのはなぜですか? このようなもの：

String ArrangeString(TStringList* items, String separator)
{
    String result = items->Strings[0];

    for (int position=1; position < items->count; position++) {
        result += separator + items->Strings[position];
    }

    return result;
}

上記の方法はより速く、より簡単です。単純なループの代わりに再帰を使用する必要はありません。このような例が、再帰が評判の悪い理由だと思います。標準的な階乗関数の例でさえ、ループを使用して実装する方が適切です。

score 0 · Accepted Answer

文字列のリストを区切り記号で連結する再帰関数を作成しました。フィールドのリストを「 items」として渡し、「コンマ + スペース」を区切り文字として渡すことにより、主に SQL 式を作成するために使用します。関数は次のとおりです (Borland Builder のネイティブデータ型を使用しますが、他の環境に合わせて調整できます)。

String ArrangeString(TStringList* items, int position, String separator)
{
  String result;

  result = items->Strings[position];

  if (position <= items->Count)
    result += separator + ArrangeString(items, position + 1, separator);

  return result;
}

私はそれを次のように呼んでいます：

String columnsList;
columnsList = ArrangeString(columns, 0, ", ");

「 fields」という名前の配列があり、その中に「 albumName」、「releaseDate」、「labelId」のデータがあるとします。次に、関数を呼び出します。

ArrangeString(fields, 0, ", ");

関数が動作を開始すると、変数「結果」は、配列の位置 0 の値である「アルバム名」を受け取ります。

次に、扱っている位置が最後の位置かどうかをチェックします。そうではないので、結果をセパレーターと関数の結果に連結します。これは、神よ、これと同じ関数です。しかし今回は、確認してください。位置に 1 を追加して呼び出します。

ArrangeString(fields, 1, ", ");

処理されている位置が最後の位置に到達するまで LIFO パイルを作成して繰り返し続けるため、関数はリストのその位置にあるアイテムのみを返し、それ以上連結しません。次に、パイルが後方に連結されます。

とった？そうでない場合は、別の方法で説明します。:o)

score 0 · Accepted Answer

実際には階乗のより良い再帰的な解決策は次のようになります。

int factorial_accumulate(int n, int accum) {
    return (n < 2 ? accum : factorial_accumulate(n - 1, n * accum));
}

int factorial(int n) {
    return factorial_accumulate(n, 1);
}

このバージョンはTail Recursiveであるため

recursion - 再帰とは何ですか? また、いつ使用する必要がありますか?

40 に答える 40

階乗またはフィボナッチ数に再帰を使用しないでください

例

Related

Reference