35

再帰関数を説明するプログラミング例を提案できる人はいますか? フィボナッチ数列やハノイの塔などおなじみの古馬もありますが、それ以外も面白そうですね。

4

22 に答える 22

126

この図は、実際のプログラミング言語ではなく英語ですが、技術的でない方法でプロセスを説明するのに役立ちます。

子供が眠れなかったので、お母さんが小さなカエルの話をしました。
  眠れなかったので、カエルのお母さんは小さなクマの話をしました。
     眠れなかったので、クマのお母さんは小さなイタチの話をしました
       ...眠りに落ちた人。
     ...そして小さなクマは眠りに落ちました。
  ...そして小さなカエルは眠りに落ちました。
...そして、子供は眠りに落ちました。
于 2008-09-24T12:20:54.080 に答える
36

再帰を理解 するには、まず再帰を理解する必要があります。

于 2008-09-24T20:44:23.057 に答える
22

再帰の経験則は、「各反復でタスクが2つ以上の同様のタスクに分割される場合にのみ、再帰を使用する」です。

したがって、フィボナッチは再帰適用の良い例ではありませんが、ハノイは良い例です。

したがって、再帰の良い例のほとんどは、さまざまな議論におけるツリー トラバーサルです。

例: グラフ トラバーサル - 訪問したノードが二度と訪問されないという要件により、実質的にグラフがツリーになります (ツリーは、単純なサイクルのない接続されたグラフです)。

分割統治アルゴリズム (クイック ソート、マージ ソート) - 「分割」の後の部分は子ノードを構成し、「征服」は親ノードから子ノードへのエッジを構成します。

于 2013-02-27T11:21:46.437 に答える
17

文字列が回文であるかどうかをテストするのはどうですか?

bool isPalindrome(char* s, int len)
{
  if(len < 2)
    return TRUE;
  else
    return s[0] == s[len-1] && isPalindrome(&s[1], len-2);
}

もちろん、ループを使用するとより効率的にそれを行うことができます。

于 2008-09-24T13:42:32.387 に答える
13

再帰降下パーサーを書きましょう!

于 2008-09-24T12:19:38.170 に答える
11

数学の世界から、アッカーマン関数があります:

Ackermann(m, n)
{
  if(m==0)
    return n+1;
  else if(m>0 && n==0)
    return Ackermann(m-1, 1);
  else if(m>0 && n>0)
    return Ackermann(m-1, Ackermann(m, n-1));
  else
    throw exception; //not defined for negative m or n
}

常に終了しますが、非常に小さな入力でも非常に大きな結果が得られます。たとえば、Ackermann(4, 2) は 2 65536 − 3 を返します。

于 2008-09-24T13:36:49.840 に答える
10

もう 1 つの「通常の疑い」は、 Quicksortと MergeSort です。

于 2008-09-24T12:23:41.140 に答える
6

多くの人が再帰を見つけられないので、インタプリタのデザインパターンは非常に良い例です。ウィキペディアの記事にリストされているサンプルコードは、これをどのように適用できるかをよく示しています。ただし、インタープリターパターンを実装するはるかに基本的なアプローチは、ToStringネストされたリストの関数です。

class List {
    public List(params object[] items) {
        foreach (object o in items)
            this.Add(o);
    }

    // Most of the implementation omitted …
    public override string ToString() {
        var ret = new StringBuilder();
        ret.Append("( ");
        foreach (object o in this) {
            ret.Append(o);
            ret.Append(" ");
        }
        ret.Append(")");
        return ret.ToString();
    }
}

var lst = new List(1, 2, new List(3, 4), new List(new List(5), 6), 7);
Console.WriteLine(lst);
// yields:
// ( 1 2 ( 3 4 ) ( ( 5 ) 6 ) 7 )

（はい、…という関数を期待している場合、上記のコードでインタープリターパターンを見つけるのは簡単ではありEvalませんが、実際には、インタープリターパターンは、関数が何と呼ばれているのか、それが何をしているのか、そしてGoFブックを明示的に教えてくれません。上記のパターンの例として上記をリストします。）

于 2008-09-24T12:57:55.097 に答える
6

私の意見では、再帰は知っておくとよいことですが、再帰を使用できるほとんどのソリューションは反復を使用して実行することもでき、反復ははるかに効率的です。

ここでは、ネストされたツリー (ASP.NET や Winforms など) でコントロールを見つける再帰的な方法を示します。

public Control FindControl(Control startControl, string id)
{
      if (startControl.Id == id)
           return startControl

      if (startControl.Children.Count > 0)
      {
           foreach (Control c in startControl.Children)
           {
                return FindControl(c, id);
           }
      }
      return null;
}
于 2008-09-24T13:50:36.907 に答える
6

ファイルシステムの世界からの実用的な例を次に示します。このユーティリティは、指定されたディレクトリの下にあるファイルを再帰的にカウントします。（理由は覚えていませんが、実は昔からこういうのが欲しかったんです…）

public static int countFiles(File f) {
    if (f.isFile()){
        return 1;
    }

    // Count children & recurse into subdirs:
    int count = 0;
    File[] files = f.listFiles();
    for (File fileOrDir : files) {
        count += countFiles(fileOrDir);
    }
    return count;
}

(Java では、Fileインスタンスは通常のファイルまたはディレクトリのいずれかを表すことができることに注意してください。このユーティリティは、カウントからディレクトリを除外します。)

一般的な実世界の例は、たとえばCommons IOライブラリFileUtils.deleteDirectory()からのものです。API ドキュメントとソースを参照してください。

于 2010-05-04T13:17:48.283 に答える
5

実際の例として、「部品表のコスト計算」の問題があります。

最終製品を製造する製造会社があるとします。各製品は、その部品のリストとそれらの部品を組み立てるのに必要な時間で説明できます。例えば手持ち式の電動ドリルは、ケース、モーター、チャック、スイッチ、コードから5分で製作。

標準的な 1 分あたりの人件費を考えると、各製品を製造するのにかかる費用はいくらですか?

あ、ちなみに一部の部品（コードなど）は購入しているので、その値段は直接わかります。

しかし、実際には一部の部品を自社で製造しています。ハウジング、ステーター、ローター、シャフト、ベアリングからモーターを作ります。所要時間は 15 分です。

そして、スタンピングとワイヤーからステーターとローターを作ります...

したがって、最終製品のコストを決定することは、実際には、プロセス内のすべての部品リストと全体の関係を表すツリーをトラバースすることになります。これは、再帰アルゴリズムでうまく表現されています。確かに反復的に行うこともできますが、核となるアイデアは日曜大工の簿記と混ざり合っているため、何が起こっているのかは明確ではありません.

于 2009-02-03T13:49:13.043 に答える
2

他の人がすでに言っているように、多くの正規の再帰の例は学術的です。

私が過去に遭遇したいくつかの実用的な使用法は次のとおりです。

1-ファイルシステムやレジストリなどのツリー構造をナビゲートする

2-他のコンテナコントロール（PanelsやGroupBoxesなど）を含む可能性のあるコンテナコントロールの操作

于 2008-10-03T14:38:23.297 に答える
2

私が知っている最も毛深い例は、Knuth のMan or Boy Testです。再帰だけでなく、ネストされた関数定義 (クロージャ)、関数参照、および定数/関数の二重性 (名前による呼び出し) の Algol 機能を使用します。

于 2008-09-24T12:49:04.870 に答える
1

私の個人的なお気に入りは二分探索です

編集：また、ツリートラバーサル。たとえば、フォルダーファイル構造をたどります。

于 2008-09-24T12:18:28.563 に答える
1

Guido van Rossum によるグラフの実装には、グラフ内の 2 つのノード間のパスを見つけるための Python の再帰関数がいくつかあります。

于 2008-09-24T12:20:05.937 に答える
1

お気に入りの並べ替え、マージ並べ替え

（アルゴリズムを覚えていて、パフォーマンス的にも悪くないのでお気に入りです）

于 2008-09-24T12:20:54.330 に答える
0

昔々、そしてそれほど昔ではありませんが、小学生はロゴとタートルグラフィックスを使用して再帰を学びました。http://en.wikipedia.org/wiki/Turtle_graphics

再帰は、徹底的な試行によってパズルを解くのにも最適です。「塗りつぶし」（Google it）と呼ばれる一種のパズルがあります。このパズルでは、クロスワードパズルのようなグリッドと単語が表示されますが、手がかりや番号付きの正方形は表示されません。私はかつて、既知の解決策が一意であることを確認するために、パズル発行者がパズルを解決するために再帰を使用するプログラムを作成しました。

于 2008-10-02T21:22:21.330 に答える
0

再帰関数は、再帰的に定義されたデータ型を操作するのに最適です。

  • 自然数がゼロまたは別の自然数の後継である
  • リストは、空のリストまたは前に要素がある別のリストです
  • ツリーは、いくつかのデータと0個以上の他のサブツリーを持つノードです。

等。

于 2008-10-03T14:33:02.763 に答える
0
  • 階乗
  • ツリーの詳細なトラバース (ファイルシステム、ゲーム空間、またはその他のケース)
于 2008-09-24T12:18:55.393 に答える
0

文字列を逆にするのはどうですか？

void rev(string s) {
  if (!s.empty()) {
    rev(s[1..s.length]);
  }
  print(s[0]);
}

これを理解すると、再帰を理解するのに役立ちます。

于 2008-09-24T12:22:40.080 に答える
0

次のようなリストを処理するものはどうですか:

  • マップ (および andmap、ormap)
  • 折りたたむ (foldl、foldr)
  • フィルター
  • 等...
于 2008-09-24T12:25:14.413 に答える
-1

スプレッドシートの列インデックスを列名に変換します。

スプレッドシートの列は '0' の数字を適切に処理しないため、思ったよりも複雑です。たとえば、Z から AA にインクリメントするときに AZ を数字として使用すると、10 ではなく 9 から 11 または 9 から 00 になるようなものになります (A が 1 か 0 かによって異なります)。Microsoft サポートの例でさえ、AAA よりも高いものに対しては間違っています!

これらの新しい桁の境界で再帰できるため、再帰的なソリューションが機能します。この実装は VB.Net にあり、最初の列 ('A') をインデックス 1 として扱います。

Function ColumnName(ByVal index As Integer) As String
    Static chars() As Char = {"A"c, "B"c, "C"c, "D"c, "E"c, "F"c, "G"c, "H"c, "I"c, "J"c, "K"c, "L"c, "M"c, "N"c, "O"c, "P"c, "Q"c, "R"c, "S"c, "T"c, "U"c, "V"c, "W"c, "X"c, "Y"c, "Z"c}

    index -= 1 'adjust index so it matches 0-indexed array rather than 1-indexed column'

    Dim quotient As Integer = index \ 26 'normal / operator rounds. \ does integer division'
    If quotient > 0 Then
        Return ColumnName(quotient) & chars(index Mod 26)
    Else
        Return chars(index Mod 26)
    End If
End Function
于 2008-09-24T16:19:33.757 に答える