26

重複の可能性：
再帰の実際の
例再帰関数の例

ほとんどのプログラミング言語のチュートリアルでは、フィボナッチ数列を生成する方法である簡単な例を使用して再帰を教えていることがわかります。私の質問は、再帰がどのように機能するかを説明するためにフィボナッチ数列を生成する以外に別の良い例がありますか？

4

23 に答える 23

38

古典は二分木検索です：

def findval (node,val):
    if node == null:
        return null
    if node.val = val:
        return node
    if node.val > val:
        return findval (node.left,val)
    return findval (node.right,val)

findval (root,thing_to_find)

これは単純な式よりも少し複雑かもしれませんが、再帰の「パンとバター」の使用であり、再帰レベルが最小化されている、それを使用するのに最適な場所を示しています。

つまり、次のように2つの非負の数を追加できます。

def add (a,b):
    if b == 0:
        return a
    return add (a+1,b-1)

ただし、大量の場合、スタックスペースがすぐに不足することに気付くでしょう（もちろん、コンパイラがテールエンドの再帰を最適化しない限り、関心のある教育レベルでは無視する必要があります）。

于 2011-02-09T12:58:03.087 に答える
29

他の回答はさまざまなアルゴリズムに言及していますが、これは完全に問題ありませんが、もう少し「具体的な」例が必要な場合は、いくつかのディレクトリとそのサブディレクトリにあるすべてのファイルを一覧表示できます。階層ファイルシステムは、再帰（ツリー）構造のよく知られた例であり、この具体的な例を使用して、深さ優先検索と幅優先検索を表示できます。

于 2011-02-09T13:20:50.317 に答える
26

再帰の私のお気に入りの例は、ハノイの塔です。ピースのスタックをポールAからポールBに移動するには、一番下のピースの上のすべてをAまたはBではないポールに移動してから、一番下のピースをBに移動します。次に、一番下のピースの上にある「ヘルパーポール」に置いたスタックを移動します。最初と3番目のステップでは、この指示を再帰的に実行します。詳細な説明については、リンクを参照してください:)

于 2011-02-09T13:07:21.763 に答える
20

回文を確認してください：

bool recursivePalindrome(std::string str, unsigned int index = 0) {
    if (index > str.length()/2) return true;
    else if (str[index] == str[str.length()-index-1])
        return recursivePalindrome(str, ++index);
    else return false;
}

またはそれほど深刻ではないことに:)

void StackOverflow()
{
   StackOverflow();
}
于 2011-02-09T12:59:02.777 に答える
16

階乗を見つけるのはどうですか。

int GetFactorial(int n )
{
  if ( n==0) return 1;
  return n*GetFactorial(n-1);
}

階乗は、nと（n-1）の階乗の積として再帰的に定義されます。そして、再帰的定義から、再帰を取得します。

于 2011-02-09T12:59:12.613 に答える
12

ファイルシステムの一部としてディレクトリツリーのフォルダ階層をトラバースすることは、実際の良い例です。C ++の例については、このSO投稿を調べてください。

ディレクトリを再帰的に削除するときに問題が発生するのはなぜですか？

于 2011-02-09T13:15:53.877 に答える
10

マージソートは、再帰的に実装すると読みやすく理解しやすいアルゴリズムの非常に良い例です。

マージソートの少し高レベルの擬似コードバージョンは次のとおりです。

def merge_sort(List sortlist)
    if sortlist.length <= 1 return sortlist
    split sortlist into leftlist and rightlist
    return merge(merge_sort(leftlist), merge_sort(rightlist))   

def merge(List leftlist, List rightlist)
    while(leftlist and rightlist not empty)
        compare leftlist.first to rightlist.first
        pop lowest value off its list and append to resultlist
    append any remains of leftlist onto resultlist
    append any remains of rightlist onto resultlist
    return resultlist

これの反復バージョンは、記述と視覚化がはるかに複雑になります。

于 2011-02-09T13:04:09.063 に答える
10
  • ここに示されている他の例のほとんどは数学の例であり、実際には同じ再帰の適用を再示しています。
  • 検索と並べ替えのバリアントは優れたアルゴリズムの例ですが、初心者には少し複雑すぎることがよくあります。
  • ハノイの塔は古典的ですが、実際にはかなり工夫されています。

================

再帰の単純な力を示すために使用する例は、ディレクトリツリーでの再帰的なファイル処理です。

これがC＃の例です

void ProcessFiles( string sFolder )
{
    foreach( string f in Directory.GetFiles( sFolder ) )
    {
        DoSomethingTo( f );
    }
    foreach( string d in Directory.GetDirectories( sFolder ))
    {
        ProcessFiles( d );
    }
}
于 2011-02-09T16:34:47.837 に答える
5

いくつかのサンプルがあります：

カタラン数：

T(n) = Sum(T(i)*T(n-i)) for all 1 <= i < n

アッカーマン関数：

A(x,y) = y+1 (if x = 0)
A(x,y) = A(x-1,1) (if y=0)
A(x,y) = A(x-1, A(x,y-1)) otherwise.

単純な迷路の問題

ハミルトン閉路問題を見つける

階乗。

他の参考資料については、 wikiページを参照してください。

于 2011-02-09T13:10:04.223 に答える
5

再帰の良い例は、基礎となるデータ構造または問題自体が再帰的である場合に関連することがよくあります：ツリー、グラフ、分割統治アプローチを使用するアルゴリズム（多くの種類のように）、再帰的文法のパーサー（一般的な算術表現のように）、チェスのような2人のプレーヤーのゲーム（単純な例ではNimを検討してください）、組み合わせ問題など。

于 2011-02-09T15:44:59.227 に答える
3

再帰的なバイナリ検索を試してください：http： //www.fredosaurus.com/notes-cpp/algorithms/searching/rbinarysearch.html

または再帰的なクイックソート： http ：//www.dreamincode.net/forums/topic/72311-recursive-quicksort-algorithm/

これらは、再帰関数の広大な世界における2つの小さな例にすぎません。

于 2011-02-09T12:59:35.163 に答える
3

算術式の評価は、スタックを使用して再帰的または反復的に実行できます。2つのアプローチを比較することは非常に有益です。

于 2011-02-09T13:13:34.087 に答える
1

ことばのはしごを検索するプログラムを書くことで再帰 を理解したことを覚えています。与えられた辞書で。

于 2011-02-09T18:27:07.357 に答える
1

私の義母はCで入門コースを受講しました。彼女は宿題の問題を抱えていました。

金属の棒（長さlen）と、金属をさまざまな長さに切断するための注文数（n）があります。使用する金属の量を最大にしたいが、全長を超えることはできません。

インストラクターは、最大合計を追跡しながら、対応するビットが0の場合は順序を除外し、ビットが1の場合は順序を含めて、バイナリで1から2**nまで繰り返すことを提案しました。彼の提案は多項式時間で実行されます。

再帰的なナップサックアルゴリズムを使用する別の解決策があります。lenから1まで繰り返し、深さ優先探索を実行して、長さの合計を再帰的に見つけることができます。

私が再帰を使用した別の領域は、ハフマンコーディング（文字列を圧縮するため）でしたが、これにはナップサック問題の直感的な感覚がありません。

再帰は根本的に異なる素晴らしい概念です。それを学んだり教えたりすることをお祈りします。

于 2011-02-09T14:39:48.780 に答える
1

アッカーマン関数：

/* undefined if m and n are negative */
uint32 ackermann( uint32 m, uint32 n )
{
  if( m < 0 && n < 0 ) { exit(1); /* invalid m and n */ }

  if( m == 0 ){ return n + 1; }

  if( m > 0 && n == 0 ){ return ackermann( m - 1, 1 ); }

  if( m > 0 && n > 0 ){ return ackermann( m - 1, ackermann(m, n - 1) ); }
}

m> 0の多重比較は冗長です（そして単純化することができます）。ただし、そのままにしておくと、アッカーマン関数の標準的な定義がわかります。

しかし、フィボナッチ数以外の興味深い再帰関数を見つけるために、数学的なエッジから遠く離れる必要はありません。

最大公約数（GDC）関数、クイックソート、および常に一般的なバイナリ検索アルゴリズムがあります。

于 2011-02-09T17:00:34.817 に答える
1

階層を持つもの。たとえば、上司の下にすべての従業員を一覧表示します。

于 2011-02-09T17:20:46.040 に答える
1

再帰は数学的帰納法にその資金を見出しており、そのように教えられるべきです。

誘導による関数の定義は、リスト処理で明確に公開できます。たとえば、言うべきことがたくさんありfoldます。

次に、木に移動します。

于 2011-02-09T17:24:44.030 に答える
1

明らかにC++ではありませんが、概念は健全です。

ネストされた多次元配列を再帰的にトラバースするPHP：

public function recurse_me($collection) {
    foreach ($collection as $value) {
        if (is_array($value)) {
            $this->recurse_me($value);
        } else {
            // process value.
        }
    }
}
于 2011-02-09T17:43:03.253 に答える
0

リンクノードタイプの構造体に対する多くの操作は再帰的になる可能性があります。他の人はBSTについて言及していますが、それらが何であるかを説明する必要がない場合は、線形のソートされていないリストで最大値を検索することを検討してください。

int MaxValue(Node node)
{
    if (node == null)
        return 0;

    if (node.Next == null)
        return node.Value;

    int maxNext = MaxValue(node.Next);
    return node.Value > maxNext ? node.Value : maxNext;
}

リスト（この場合、リンクリスト）は、実際の用語で非常に簡単に説明できます。視聴者はプログラミングのバックグラウンドを持っている必要はありません。並べ替えられていないボックスのグループ、または番号のリストとして簡単に説明できます。

于 2011-02-09T17:05:15.220 に答える
0

学術的な例は階乗です

n！

計算。実生活では、数学のライブラリを取得します。

于 2011-02-09T12:57:54.420 に答える
0

再帰に依存するソートアルゴリズムがあります。

そして、再帰で実装される二分探索があります。

于 2011-02-09T12:59:09.237 に答える
0

パスカルの三角形

于 2011-02-09T13:01:58.830 に答える
0

ヒープソートも良い例です。これについては、Cormen、Rivestなどによる「IntroductiontoAlgorithms」で読むことができます。素晴らしい本です。そこにたくさんの興味深い本が見つかることを願っています。

于 2011-02-09T13:06:45.630 に答える