recursion - 意味 - 再帰的 わかりやすく



再帰とは何ですか。いつ使用しますか。 (20)

メーリングリストやオンラインディスカッションで定期的に登場すると思われるトピックの1つは、コンピュータサイエンス学位を取得することのメリット(またはその欠如)です。 否定的な政党のために何度も何度も登場するように思われる議論は、彼らが数年前からコーディングしていて、彼らが再帰を使ったことがないということです。

それで問題は次のとおりです。

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

Answer #1
  1. 自分自身を呼び出す機能
  2. 関数が(簡単に)単純な操作に加えて問題のいくつかの小さな部分で同じ関数に分解されることができるとき。 むしろ、これは再帰の良い候補になると言うべきです。
  3. 彼らはします!

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

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

  return a*fact(a-1);
}

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


Answer #2

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 #3

このスレッドには recursion についての recursion の良い説明がありますが、この答えはあなたがほとんどの言語でそれを使うべきではない理由についてです。*主要な命令型言語実装の大部分(すなわちC、C ++、Basic、Pythonのすべての主要実装) 、Ruby、Java、およびC#)の iteration は、再帰よりもはるかに望ましいです。

その理由を調べるために、上記の言語が関数を呼び出すために使用するステップを見てください。

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

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

そのため、これらの言語では再帰が遅くなり、クラッシュに対して脆弱になります。 それを使用するための引数がまだいくつかあります。 一般的に、再帰的に書かれたコードは、読み方を知っていれば、短くて少し上品です。

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

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

**ところで、Marioでは、ArrangeString関数の一般的な名前は "join"です。選択した言語にまだ実装されていないのであれば、私は驚きます。


Answer #4

これが簡単な例です。セット内の要素数。 (数を数えるより良い方法がありますが、これは良い単純な再帰的な例です。)

まず、2つの規則が必要です。

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

[xxx]のようなセットがあるとしましょう。 アイテムの数を数えましょう。

  1. セットは[xxx]で、空ではないので、ルール2を適用します。アイテムの数は、1と[xx]内のアイテムの数の合計です(つまり、アイテムを削除しました)。
  2. 集合は[xx]なので、ルール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)を解いて[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)

他にも多くの人がカバーすると思いますが、もっと役に立つ例があります(例えば木を横切るなど)。


Answer #5

こんにちは、私の意見が誰かと一致すれば申し訳ありませんが、私は単純な英語で再帰を説明しようとしています。

Jack、John、Morganの3人のマネージャがいるとします。 Jackは2人のプログラマー、John - 3とMorgan - 5を管理しています。あなたはすべてのマネージャに300ドルを与え、それがいくらかかるのか知りたいのです。 答えは明白です - しかし、2人のMorganの従業員が管理者でもあるとしたらどうでしょうか。

ここに再帰があります。 あなたは階層の一番上から始めます。 サマリーコストは0 $です。 あなたはジャックから始めて、それから彼が従業員としてマネージャーを持っているかどうかチェックしてください。 あなたがそれらのうちのどれかがいるならば、彼らが従業員としてマネージャを持っているかどうかなどをチェックしてください。 あなたがマネージャーを見つけるたびに、サマリーコストに300 $を加えてください。 あなたがジャックを使い終わったら、ジョン、その従業員そしてモーガンへ行きなさい。

あなたは、あなたが何人のマネージャを持っているか、そしてあなたがあなたがどれくらいの予算を使うことができるかを知っているけれども、あなたが答えを得る前にどれくらいのサイクルをあなたがたどるかについて知ることはないでしょう。

再帰は、それぞれ親と子と呼ばれる枝と葉を持つ木です。 再帰アルゴリズムを使うとき、あなたは多かれ少なかれ意識的にデータから木を作っています。


Answer #6

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

人々が「再帰」と呼ぶとき、彼らは通常彼らが書いた関数について話しています。 再帰は、データ構造内の階層をトラバースするときに役立ちます。


Answer #7

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


Answer #8

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

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


Answer #9

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


Answer #10

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

標準的な例は、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 Clause)と呼ばれ、アルゴリズムが永遠に実行されるのを妨げるものです。 関数が1以下の値で呼び出されるときはいつでも、単に値1を返します。 2番目の部分はもっと興味深く、 再帰的ステップ として知られています。 ここでは、わずかに変更されたパラメーターを使用して同じメソッドを呼び出し(1ずつデクリメントし)、次に結果にnのコピーを掛けます。

最初に遭遇したとき、これは一種の混乱を招く可能性があるので、実行時にそれがどのように機能するかを調べることは有益です。 FactRec(5)を呼び出すことを想像してください。 私たちはルーチンに入り、基本ケースに拾われないので、このようになります。

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

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

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

// 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 #11

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

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

    return n * Factorial(n - 1);
}

Answer #12

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

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

  1. ほとんどの人は(私も含めて)関数型プログラミングとは対照的に、手続き型プログラミングまたはオブジェクト指向プログラミングにプログラミングの歯を切りました。 そのような人々にとって、反復的なアプローチ(通常はループを使う)はより自然に感じられます。

  2. 手続き型またはオブジェクト指向プログラミングにプログラミングの歯を切る私たちはエラーを起こしやすいので再帰を避けるように言われることがよくあります。

  3. 再帰は遅いとよく言われます。 ルーチンからの呼び出しと呼び出しを繰り返し行うと、スタックのプッシュとポップが多くなります。これは、ループするよりも遅くなります。 私はいくつかの言語が他の言語よりこれをうまく処理すると思います、そして、それらの言語は支配的なパラダイムが手続き型またはオブジェクト指向であるものではないでしょう。

  4. 私が使ったプログラミング言語の少なくともいくつかでは、スタックがそれほど深くないので、ある深さを超えたら再帰を使わないことをお勧めします。


Answer #13

再帰関数はそれ自身を呼び出すものです。 私がそれを使うことを私が見つけた最も一般的な理由は木構造を横断することです。 例えば、私がチェックボックス付きのTreeViewを持っているなら(新しいプログラムのインストール、インストールする機能の選択 "ページを考えてください)、私は次のような"全てチェック "ボタンが欲しいかもしれません(擬似コード):

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

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

つまり、checkRecursivelyは最初に渡されたノードをチェックしてから、そのノードの各子に対して自分自身を呼び出しています。

あなたは再帰に少し注意する必要があります。 無限再帰ループに陥った場合、例外が発生します。

適切なときに人々がそれを使うべきでない理由を考えることはできません。 ある状況では役に立ちますが、他の状況では役に立ちません。

面白いテクニックなので、正当な理由がない限り、最終的には必要以上に頻繁に使用されるコーダもあると思います。 これはいくつかの円で再帰に悪い名前を与えました。


Answer #14

基本的にデータ型の各ケースのケースを持つ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

これは、データ構造に対して機能する任意のアルゴリズムを作成するための最も明白な方法です。

さて、あなたがPeano公理を使って定義された整数(まあ、自然数)を見ると

 integer = 0 | succ(integer)

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

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

あまりにもよく知られている階乗関数は、この形式の最も些細な例です。


Answer #15

平易な英語で:3つのことができるとしましょう:

  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 #16

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

struct Node {
    Node* next;
};

そして、あなたはリンクリストがどれくらいの期間あなたが再帰でこれをすることができるかについて知りたいです:

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

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


Answer #17

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


Answer #18

関数が自分自身を呼び出してループを作成するたびに、それが再帰です。 何にも言えることですが、再帰には良い用途と悪い用途があります。

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

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

しかし、これは、もっと効率的な反復で簡単に置き換えることができるので、怠惰でほとんど無意味な例です。 結局のところ、再帰は関数呼び出しのオーバーヘッドを被ります。これは上の例では関数自体の中の操作に比べてかなりの量になる可能性があります。

したがって、反復ではなく再帰を実行する全体的な理由は、 呼び出しスタック を利用していくつかの巧妙な処理を実行するためです。 たとえば、同じループ内で異なるパラメータを使用して関数を複数回呼び出すと、それは branching を達成 branching ための方法です。 典型的な例は Sierpinskiの三角形 です。

呼び出しスタックが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サイトのクローラ、ディレクトリの比較など、トラバース階層を含めることができます。

結論

実際的には、反復分岐が必要なときはいつでも再帰が最も理にかなっています。


Answer #19

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

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

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

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

英語では、この定義は任意の数の最大公約数と0がその数であり、2つの数 m nの 最大公約数は nの 最大公約数と m nを 除算した後の余りです。

なぜこれが機能するのか知りたいのなら、 ユークリッドアルゴリズム に関するウィキペディアの記事を見てください。

例として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番目の部分が適用されます。 ステップ3では、2番目の部分が再び適用されますが、今回は8 mod 2 = 0が2を8で除算して余りを求めないため、10 mod 8 = 2となります。 ステップ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 #20

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

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

あなたの机が1024枚の論文の混乱した混乱で覆われているとしましょう。 再帰を使用して、どのようにして混乱からきちんとしたきれいな紙の束を作成しますか。

  1. 分割: すべてのシートを広げると、各「スタック」に1枚のシートしかありません。
  2. 征服する:
    1. 各シートを他のシートの上に重ねて移動します。 あなたは今2のスタックを持っています。
    2. 各2スタックを別の2スタックの上に置いて、周回します。 あなたは今4のスタックを持っています。
    3. 各4スタックを別の4スタックの上に置いて、周回します。 あなたは今8のスタックを持っています。
    4. ... 延々と ...
    5. これで、1024枚の巨大なスタックができました。

すべてを数えることを除けば、これはかなり直感的に理解できることに注意してください(これは厳密には必要ではありません)。 実際には、1枚のスタックまでいっぱいに行くことはできないかもしれませんが、それでもうまくいくでしょう。 重要な部分はハンマーです:あなたの腕を使うと、より大きなスタックを作るためにあなたは常に1つのスタックを他のものの上に置くことができます、そしてそれはどちらのスタックがどれほど大きくても構いません。





computer-science