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

Question

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

そこで質問は次のとおりです。

1. 再帰とは何ですか?
2. 再帰をどのような場合に使用すればよいでしょうか?
3. なぜ人々は再帰を使用しないのでしょうか?

Answer 1

良い説明がたくさんあります 再帰 このスレッドでは、この回答は、ほとんどの言語でそれを使用すべきではない理由についてのものです。* 主要な命令型言語の実装 (つまり、C、C++、Basic、Python、Ruby、Java、および C# のすべての主要な実装) 反復 再帰よりもはるかに好ましいです。

その理由を確認するには、上記の言語が関数を呼び出すために使用する手順を見てみましょう。

1. 空間が切り取られる スタック 関数の引数とローカル変数の場合
2. 関数の引数はこの新しい空間にコピーされます
3. コントロールは関数にジャンプします
4. 関数のコードが実行される
5. 関数の結果は戻り値にコピーされます
6. スタックは前の位置に巻き戻されます
7. コントロールは関数が呼び出された場所に戻ります

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

したがって、これらの言語では再帰が遅くなり、クラッシュしやすくなります。ただし、それを使用することについてはまだいくつかの議論があります。一般に、再帰的に記述されたコードは、読み方がわかれば短く、より洗練されます。

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

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

** ところで、マリオ、ArrangeString 関数の一般的な名前は「join」ですが、あなたの選択した言語にその関数がまだ実装されていないとしたら驚くでしょう。

Answer 2

再帰の簡単な英語の例。

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.

Answer 3

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

struct Node {
    Node* next;
};

そして、再帰を使用してこれを実行できるリンク リストの長さを調べたいとします。

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

(もちろん、これは for ループでも同様に実行できますが、概念を説明するのに役立ちます)

Answer 4

関数がそれ自体を呼び出してループを作成するとき、それが再帰です。他のものと同様、再帰にも良い使い方と悪い使い方があります。

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

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

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

したがって、反復ではなく再帰を行う理由は、 コールスタック 賢いことをするために。たとえば、同じループ内で異なるパラメーターを使用して関数を複数回呼び出す場合、これは次のことを実現する方法です。 分岐する. 。古典的な例としては、 シェルピンスキー・トライアングル.

再帰を使用すると、そのうちの 1 つを非常に簡単に描画できます。呼び出しスタックは 3 方向に分岐します。

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 サイト クローラー、ディレクトリ比較など。

結論

実際には、反復分岐が必要な場合には、再帰が最も合理的です。

Answer 5

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

標準的な例は、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 );
}

この関数の最初の部分は、 規範事例 (または場合によっては Guard 条項)、アルゴリズムが永久に実行されないようにするものです。関数が 1 以下の値で呼び出された場合には、値 1 を返すだけです。2 番目の部分はより興味深いもので、 再帰的なステップ. 。ここでは、パラメーターを少し変更して (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))));

この最後の置換は、基本ケースがトリガーされたときに行われます。この時点で、そもそも階乗の定義に直接等しい、単純な代数式を解くことができます。

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

Answer 6

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

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

    return n * Factorial(n - 1);
}

Answer 7

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

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

Answer 8

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

数学では、 最大公約数 (gcd) … 2 つ以上の非ゼロ整数のうち、剰余なしで数値を割る最大の正の整数です。

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

modはどこにありますか モジュロ演算子 (つまり、整数を除算した後の剰余)。

英語では、この定義は、任意の数の最大公約数とゼロがその数であり、2 つの数の最大公約数であることを示します。 メートル そして n はの最大公約数です n そして割った余り メートル による n.

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

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

1. gcd(10, 8)
2. gcd(10, 10 mod 8)
3. gcd(8, 2)
4. gcd(8, 8 mod 2)
5. gcd(2, 0)
6. 2

最初のステップでは、8 はゼロに等しくないため、定義の 2 番目の部分が適用されます。8 は 10 に 1 回入り、余りは 2 になるため、10 mod 8 = 2 となります。ステップ 3 で 2 番目の部分が再度適用されますが、今回は 8 を 2 で割っても余りがないため、8 mod 2 = 0 となります。ステップ 5 では、2 番目の引数は 0 なので、答えは 2 です。

gcd が等号の左側と右側の両方に表示されていることに気づきましたか?数学者は、定義している式が次のとおりであるため、この定義は再帰的であると言うでしょう。 再発する その定義の内側。

再帰的な定義はエレガントになる傾向があります。たとえば、リストの合計の再帰的定義は次のようになります。

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

どこ head はリストの最初の要素であり、 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。再帰的なケースでは問題を徹底的に削り、簡単な答えにたどり着きます。

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

Answer 9

1. 自分自身を呼び出す関数
2. 関数を単純な演算と、問題のより小さな部分に対する同じ関数に (簡単に) 分解できる場合。むしろ、これが再帰の良い候補になると言うべきです。
3. そうですよ！

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

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

  return a*fact(a-1);
}

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

Answer 10

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

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

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

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

再帰には少し注意する必要があります。無限再帰ループに入ると、スタック オーバーフロー例外が発生します:)

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

これは興味深いテクニックなので、プログラマーの中には、本当の理由もなく、必要以上に頻繁に使用してしまう人もいるのではないかと思います。このため、一部のサークルでは再帰に悪名が与えられています。

Answer 11

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

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

• GNU を意味する GNU は Unix ではありません
• PHP を意味する PHP:ハイパーテキストプリプロセッサ
• YAML を意味する YAMLはマークアップ言語ではない
• ワイン を意味する Wine はエミュレータではありません
• ビザ を意味する ビザ国際サービス協会

他の例はウィキペディアにあります

Answer 12

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

人々はさまざまな理由で再帰を避けます。

1. ほとんどの人 (私も含めて) は、関数型プログラミングではなく、手続き型プログラミングまたはオブジェクト指向プログラミングに興味を持っています。そのような人にとっては、反復的なアプローチ (通常はループを使用する) の方が自然に感じられます。

2. 手続き型プログラミングやオブジェクト指向プログラミングの基礎を身につけた人は、再帰はエラーが発生しやすいため、再帰を避けるようによく言われます。

3. 再帰が遅いとよく言われます。ルーチンの呼び出しとルーチンからの戻りを繰り返し行うと、大量のスタックのプッシュとポップが発生し、ループよりも遅くなります。一部の言語は他の言語よりもこれをうまく処理できると思いますが、それらの言語はおそらく、主要なパラダイムが手続き型またはオブジェクト指向である言語ではありません。

4. 私が使用した少なくとも 2 つのプログラミング言語では、スタックがそれほど深くないため、特定の深さを超える場合は再帰を使用しないようにという推奨事項を聞いたことを覚えています。

Answer 13

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

たとえば、階乗を考えます。

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)

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

お役に立てれば...

Answer 14

私はこの定義が好きです。
再帰では、ルーチンは問題自体の小さな部分を解決し、問題をより小さな部分に分割し、その後、ルーチン自体を呼び出して、より小さな部分のそれぞれを解決します。

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

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

コンピューターサイエンスの教科書の問題の1つは、再帰の愚かな例を提示することです。典型的な例は、ファクタリールを計算するか、フィボナッチシーケンスを計算することです。再帰は強力なツールであり、どちらの場合でもそれを使用することは本当に馬鹿げています。私のために働いていたプログラマーが再帰を使用して要因を計算した場合、私は他の誰かを雇います。

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

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

Answer 15

1.）メソッドは、それ自体を呼び出すことができる場合、再帰的です。直接的に:

void f() {
   ... f() ... 
}

または間接的に:

void f() {
    ... g() ...
}

void g() {
   ... f() ...
}

2.) 再帰を使用する場合

Q: Does using recursion usually make your code faster? 
A: No.
Q: Does using recursion usually use less memory? 
A: No.
Q: Then why use recursion? 
A: It sometimes makes your code much simpler!

3.) 再帰を使用するのは、反復コードの記述が非常に複雑な場合のみです。たとえば、preorder、postorder などのツリー トラバーサル手法は、反復的および再帰的に行うことができます。しかし、その単純さのため、通常は再帰を使用します。

Answer 16

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

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

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

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

1. セットは空ではない [x x x] であるため、ルール 2 を適用します。項目の数は、[x x] 内の項目の数に 1 を加えたものです (つまり、アイテムを削除しました）。
2. セットは [x x] なので、ルール 2 を再度適用します。1 + [x] 内の項目の数。
3. セットは [x] ですが、これでもルール 2 に一致します。1 + [] 内の項目の数。
4. 現在のセットは [] であり、ルール 1 に一致します。カウントはゼロです！
5. ステップ 4 (0) の答えがわかったので、ステップ 3 (1 + 0) を解くことができます。
6. 同様に、ステップ 3 (1) の答えがわかったので、ステップ 2 (1 + 1) を解くことができます。
7. そして最後に、ステップ 2 (2) の答えがわかったので、ステップ 1 (1 + 2) を解決して、[x x x] の項目数 (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)

他にも役立つ例 (木を横断するなど) はたくさんありますが、それらについては他の人が取り上げると思います。

Answer 17

そうですね、それはかなりまともな定義です。ウィキペディアにもきちんとした定義があります。そこで、別の（おそらくもっと悪い）定義を追加します。

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

Answer 18

例：階段の再帰的定義は次のとおりです。階段は次のもので構成されます。- 単一のステップと階段（再帰） - または単一のステップ（終了）のみ

Answer 19

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

Answer 20

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

1. リンゴを1個取ってください
2. タリーマークを書き留める
3. タリーマークをカウントする

目の前のテーブルの上にたくさんのリンゴがあり、そこにリンゴが何個あるか知りたいとします。

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

完了するまで同じことを繰り返すプロセスを再帰といいます。

これがあなたが探している「わかりやすい英語」の答えであることを願っています。

Answer 21

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

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

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

Answer 22

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

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

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

Answer 23

ツリー構造があるときはいつでも使用したいと思います。XMLを読むのに非常に便利です。

Answer 24

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

Answer 25

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

再帰は問題解決戦略です。 巨大な 問題は、どの段階でも、毎回同じハンマーで「2 つの小さなものを 1 つの大きなものに変える」だけです。

例

あなたの机の上が 1,024 枚の書類の乱雑な状態で覆われているとします。再帰を使用して、混乱した書類の束を 1 つにまとめて整理するにはどうすればよいでしょうか?

1. 分ける： すべてのシートを広げて、各「スタック」に 1 枚のシートだけが入るようにします。
2. 征服する:
   2. 各シートをもう 1 枚重ねていきます。これでスタックが 2 個になりました。
   3. それぞれの 2 つのスタックを別の 2 つのスタックの上に置きます。これで 4 つのスタックができました。
   4. それぞれの 4 つのスタックを別の 4 つのスタックの上に置きながら回ります。これでスタックが 8 個になりました。
   5. ...延々と ...
   6. これで、1024 枚の巨大なスタックが完成しました。

すべてを数える (厳密には必要ではありません) を除けば、これは非常に直感的であることに注意してください。実際には、1 枚のシートのスタックまでは実行できないかもしれませんが、それでも実行できますし、それでも機能します。重要な部分はハンマーです。腕を使えば、いつでも 1 つのスタックをもう 1 つのスタックの上に重ねて、より大きなスタックを作ることができます。どちらのスタックがどれだけ大きいかは (合理的な範囲内で) 問題ではありません。

Answer 26

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

Answer 27

ねえ、私の意見が誰かに同意したらごめんなさい、私は再帰をわかりやすい英語で説明しようとしているだけです。

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

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

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

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

Answer 28

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

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

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

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

Answer 29

あらゆるアルゴリズムの展示 構造的な データ型の再帰は、基本的に、データ型の各ケースに対応する switch ステートメントで構成されます。

たとえば、型に取り組んでいるとき

  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

あまりにも知られている要因関数は、この形式の最も些細な例についてです。

Answer 30

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