recursion - 再帰の実例

Question

再帰的アプローチが深さ優先探索 (DFS) 以外の自然な解決策である現実世界の問題は何ですか?

(ハノイの塔、フィボナッチ数、または階乗的な現実世界の問題は考慮していません。それらは私の頭の中で少し不自然です。)

score 114 · Accepted Answer

114

再帰の実例

ひまわり

于 2008-09-19T21:51:15.047 に答える

score 65 · Accepted Answer

ファイルシステムのディレクトリ構造に関係するものはどうですか。ファイルの再帰的な検索、ファイルの削除、ディレクトリの作成など。

以下は、ディレクトリとそのサブディレクトリの内容を再帰的に出力する Java 実装です。

import java.io.File;

public class DirectoryContentAnalyserOne implements DirectoryContentAnalyser {

    private static StringBuilder indentation = new StringBuilder();

    public static void main (String args [] ){
        // Here you pass the path to the directory to be scanned
        getDirectoryContent("C:\\DirOne\\DirTwo\\AndSoOn");
    }

    private static void getDirectoryContent(String filePath) {

        File currentDirOrFile = new File(filePath);

        if ( !currentDirOrFile.exists() ){
            return;
        }
        else if ( currentDirOrFile.isFile() ){
            System.out.println(indentation + currentDirOrFile.getName());
            return;
        }
        else{
            System.out.println("\n" + indentation + "|_" +currentDirOrFile.getName());
            indentation.append("   ");

            for ( String currentFileOrDirName : currentDirOrFile.list()){
                getPrivateDirectoryContent(currentDirOrFile + "\\" + currentFileOrDirName);
            }

            if (indentation.length() - 3 > 3 ){
                indentation.delete(indentation.length() - 3, indentation.length());
            }
        }       
    }

}

score 62 · Accepted Answer

ここには数学的な例がたくさんありますが、現実世界の例が欲しかったので、少し考えて、これはおそらく私が提供できる最高のものです:

致命的ではない特定の伝染性感染症にかかった人を見つけて、すぐに治ります (タイプ A)。ただし、5 人に 1 人 (これらをタイプ B と呼びます) は永久に感染し、感染しません。症状を抑え、スプレッダーとして機能するだけです。

これは、B型が多数のA型に感染するたびに、非常に厄介な混乱の波を引き起こします.

あなたの仕事は、すべての B 型を追跡し、それらに免疫を与えて病気の根幹を止めることです。残念ながら、A型の人々はB型に有効な治療法に対して致命的なアレルギーを持っているため、すべての人に全国的な治療法を施すことはできません.

これを行う方法は、社会的発見であり、感染した人 (タイプ A) が与えられた場合、先週のすべての連絡先を選択し、各連絡先をヒープにマークします。人が感染していることをテストしたら、「フォローアップ」キューに追加します。人がタイプBの場合は、頭の「フォローアップ」に追加します（これを早く止めたいからです）。

特定の人を処理した後、キューの先頭から人を選択し、必要に応じて予防接種を適用します。以前に訪問していない連絡先をすべて取得し、感染しているかどうかをテストします。

感染者の列が0になるまで繰り返し、次の流行を待ちます。

(わかりました、これは少し反復的ですが、再帰的な問題を解決するための反復的な方法です。この場合、問題への可能性のある経路を発見しようとする人口ベースの幅優先トラバーサルであり、さらに、反復的な解決策は多くの場合、より高速で効果的です、そして私はどこでも再帰を強制的に削除するので、本能的になります. ....くそー！）

score 44 · Accepted Answer

44

Quicksort、merge sort、およびその他のほとんどの N-log N ソート。

于 2008-09-19T21:37:35.267 に答える

score 16 · Accepted Answer

再帰は、バックトラッキングアルゴリズムの実装でよく使用されます。これを「現実世界」に適用するには、数独ソルバーはどうでしょうか。

score 16 · Accepted Answer

Matt Dillard の例は良い例です。より一般的に言えば、ツリーの歩行は通常、再帰によって非常に簡単に処理できます。たとえば、解析ツリーのコンパイル、XML や HTML のウォークオーバーなどです。

score 14 · Accepted Answer

再帰は、問題を解決するために同じアルゴリズムを使用できるサブ問題に分割することによって問題を解決できる場合に適しています。ツリーとソートされたリストのアルゴリズムは自然に適合します。計算幾何学 (および 3D ゲーム) の多くの問題は、バイナリスペースパーティショニング(BSP) ツリー、ファットサブディビジョン、または世界をサブパーツに分割するその他の方法を使用して、再帰的に解決できます。

再帰は、アルゴリズムの正確性を保証しようとしている場合にも適しています。不変の入力を受け取り、入力に対する再帰呼び出しと非再帰呼び出しの組み合わせである結果を返す関数が与えられた場合、通常、数学的帰納法を使用して関数が正しい (または正しくない) ことを証明するのは簡単です。多くの場合、反復関数や変化する可能性のある入力を使用してこれを行うのは困難です。これは、正確性が非常に重要な財務計算やその他のアプリケーションを扱う場合に役立ちます。

score 11 · Accepted Answer

確かに、そこにある多くのコンパイラは再帰を多用しています。コンピュータ言語自体は本質的に再帰的です (つまり、「if」ステートメントを他の「if」ステートメント内に埋め込むことができます)。

score 9 · Accepted Answer

コンテナコントロール内のすべての子コントロールの読み取り専用を無効化/設定します。子コントロールの一部はコンテナー自体であったため、これを行う必要がありました。

public static void SetReadOnly(Control ctrl, bool readOnly)
{
    //set the control read only
    SetControlReadOnly(ctrl, readOnly);

    if (ctrl.Controls != null && ctrl.Controls.Count > 0)
    {
        //recursively loop through all child controls
        foreach (Control c in ctrl.Controls)
            SetReadOnly(c, readOnly);
    }
}

score 8 · Accepted Answer

多くの場合、再帰的な方法を使用してドキュメントのスタックを並べ替えます。たとえば、名前が付いた100個のドキュメントを並べ替えているとします。最初に最初の文字でドキュメントを山に配置し、次に各山を並べ替えます。

辞書で単語を検索することは、再帰的である二分探索のような手法によって実行されることがよくあります。

組織では、上司が部門長にコマンドを与え、部門長がマネージャーにコマンドを与えることがよくあります。

score 8 · Accepted Answer

SICPの有名な評価/適用サイクル

_{(ソース: mit.edu )}

eval の定義は次のとおりです。

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        ((definition? exp) (eval-definition exp env))
        ((if? exp) (eval-if exp env))
        ((lambda? exp)
         (make-procedure (lambda-parameters exp)
                         (lambda-body exp)
                         env))
        ((begin? exp) 
         (eval-sequence (begin-actions exp) env))
        ((cond? exp) (eval (cond->if exp) env))
        ((application? exp)
         (apply (eval (operator exp) env)
                (list-of-values (operands exp) env)))
        (else
         (error "Unknown expression type - EVAL" exp))))

apply の定義は次のとおりです。

(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure procedure arguments))
        ((compound-procedure? procedure)
         (eval-sequence
           (procedure-body procedure)
           (extend-environment
             (procedure-parameters procedure)
             arguments
             (procedure-environment procedure))))
        (else
         (error
          "Unknown procedure type - APPLY" procedure))))

eval-sequence の定義は次のとおりです。

(define (eval-sequence exps env)
  (cond ((last-exp? exps) (eval (first-exp exps) env))
        (else (eval (first-exp exps) env)
              (eval-sequence (rest-exps exps) env))))

eval-> apply-> eval-sequence->eval

score 7 · Accepted Answer

再帰は、ゲーム開発 (およびその他の同様の領域) における衝突検出のために BSP ツリーなどで使用されます。

score 7 · Accepted Answer

私が最近得た現実世界の要件：

要件 A: 要件 A を十分に理解した上で、この機能を実装してください。

score 4 · Accepted Answer

いくつかの場所で純粋な末尾再帰を使用してステートマシンをシミュレートするシステムがあります。

score 4 · Accepted Answer

パーサーとコンパイラーは、再帰降下法で作成できます。lex/yacc などのツールはより高速で効率的なパーサーを生成するため、最適な方法ではありませんが、概念的に単純で実装が簡単であるため、一般的なままです。

score 4 · Accepted Answer

再帰は問題 (状況) に適用され、問題をより小さな部分に分割 (削減) でき、各部分が元の問題に似ているように見えます。

それ自体に似た小さな部分を含むものの良い例は次のとおりです。

木構造（枝は木のようなもの）
リスト (リストの一部はまだリストです)
コンテナ（ロシア人形）
シーケンス (シーケンスの一部は次のようになります)
オブジェクトのグループ (サブグループは依然としてオブジェクトのグループです)

再帰とは、問題をさらに小さな断片に分解し、それらの断片の 1 つがケーキのように十分に小さくなるまで続ける手法です。もちろん、それらを分割した後は、元の問題の完全な解決策を形成するために、正しい順序で結果を「つなぎ合わせる」必要があります。

いくつかの再帰的ソートアルゴリズム、ツリーウォーキングアルゴリズム、マップ/リデュースアルゴリズム、分割統治法はすべて、この手法の例です。

コンピュータープログラミングでは、ほとんどのスタックベースの call-return 型言語には、再帰用の機能が既に組み込まれています。

問題をより小さな断片に分割する ==> 元のデータのより小さなサブセットで自分自身を呼び出す)、
ピースがどのように分割されているかを追跡する ==> コールスタック、
結果をつなぎ合わせる==>スタックベースのリターン

score 4 · Accepted Answer

関数型プログラミング言語には、再帰の優れた例がいくつか見られます。関数型プログラミング言語 ( Erlang、Haskell、ML / OCaml / F#など) では、リスト処理で再帰を使用することは非常に一般的です。

典型的な命令型 OOP スタイルの言語でリストを扱う場合、リンクされたリスト ([item1 -> item2 -> item3 -> item4]) として実装されたリストを見るのは非常に一般的です。ただし、一部の関数型プログラミング言語では、リスト自体が再帰的に実装されていることがわかります。リストの「先頭」はリストの最初の項目を指し、「末尾」は残りの項目を含むリストを指します ( [item1 -> [item2 -> [item3 -> [item4 -> []]]]])。私の意見では、それはかなり創造的です。

このリストの処理は、パターンマッチングと組み合わせると非常に強力です。数字のリストを合計したいとしましょう：

let rec Sum numbers =
    match numbers with
    | [] -> 0
    | head::tail -> head + Sum tail

これは基本的に、「空のリストで呼び出された場合は 0 を返す」(再帰を中断できるようにする) ことを意味し、それ以外の場合は head の値 + 残りの項目で呼び出された Sum の値を返します (したがって、再帰)。

たとえば、URLのリストがあるとします。各 URL がリンクするすべての URL を分割し、すべての URL へのリンクの総数を減らして、ページの「値」を生成します (Google が提供するアプローチ)。これはPageRankで取得され、元の MapReduceペーパーで定義されていることがわかります)。これを行うと、ドキュメント内の単語数も生成できます。そして、他にもたくさんの、たくさんの、たくさんのこと。

この機能パターンを任意のタイプのMapReduceコードに拡張して、何かのリストを取得し、それを変換して、別のもの (別のリスト、またはリストの zip コマンド) を返すことができます。

score 4 · Accepted Answer

階層構造のフィードバックループ。

トップボスは、社内の全員からフィードバックを収集するようにトップエグゼクティブに指示します.

各幹部は直属の部下を集め、直属の部下からフィードバックを集めるように指示します。

そして、順調に進んでいます。

直属の部下を持たない人 (ツリーのリーフノード) がフィードバックを提供します。

フィードバックは、各マネージャーが独自のフィードバックを追加して、ツリーを遡ります。

最終的にはすべてのフィードバックがトップのボスに戻ります。

再帰的な方法では各レベルでのフィルタリングが可能であるため、これは自然な解決策です。つまり、重複の照合と不快なフィードバックの除去です。トップボスはグローバルメールを送信し、各従業員にフィードバックを直接報告させることもできますが、「真実を処理できない」問題や「解雇された」問題があるため、ここでは再帰が最適に機能します。

score 3 · Accepted Answer

再帰によって解決される「現実世界」の問題は、人形の入れ子です。関数は OpenDoll() です。

それらのスタックが与えられると、最も内側の人形に到達するまで、必要に応じて OpenDoll() を呼び出して、人形を再帰的に開きます。

score 3 · Accepted Answer

XML、またはツリーであるすべてのトラバース。正直なところ、私は自分の仕事で再帰をほとんど使用していません。

score 2 · Accepted Answer

私の仕事では、ツリーとして記述できる一般的なデータ構造を持つシステムがあります。つまり、再帰はデータを操作するための非常に効果的な手法です。

再帰せずにそれを解決するには、多くの不要なコードが必要になります。再帰の問題は、何が起こっているのかを追跡するのが簡単ではないということです。実行の流れをたどるときは、本当に集中する必要があります。しかし、それが機能するとき、コードはエレガントで効果的です。

score 2 · Accepted Answer

WindowsフォームまたはWebフォーム（.NETWindowsフォーム/ASP.NET）のコントロールツリーを解析します。

score 2 · Accepted Answer

XMLファイルの解析。
多次元空間での効率的な検索。例）2D の quad-trees、3D の oct-trees、kd-trees など。
階層クラスタリング。
考えてみれば、階層構造を横断することは自然に再帰に役立ちます。
ループがなく、再帰が唯一の方法である C++ でのテンプレートメタプログラミング。

score 2 · Accepted Answer

たとえば、ページがツリー構造になっている Web サイト用の CMS を構築しているとします。ルートはホームページです。

また、{user|client|customer|boss} が、ツリーのどこにいるかを示すためにすべてのページにパンくずリストを配置するように要求したとします。

任意のページ n について、n の親、およびその親などを再帰的にたどって、ページツリーのルートに戻るノードのリストを作成することが必要になる場合があります。

もちろん、その例ではページごとに数回データベースにアクセスしているため、page-table を a として検索し、page-table を b として検索し、a.id を結合する SQL エイリアシングを使用することをお勧めします。 b.parent を使用して、データベースに再帰結合を実行させます。しばらく経っているので、私の構文はおそらく役に立たないでしょう。

繰り返しになりますが、これを 1 回だけ計算してページレコードと共に保存し、ページを移動した場合にのみ更新することもできます。そっちの方が効率的かも。

とにかく、それは私の 0.02 ドルです

score 2 · Accepted Answer

N レベルの深さの組織ツリーがあります。いくつかのノードがチェックされており、チェックされたノードのみに展開したいと考えています。

これは私が実際にコーディングしたものです。再帰を使えば簡単です。

score 2 · Accepted Answer

2

複合平均などの金融/物理学の計算。

于 2008-09-19T22:14:47.423 に答える

score 2 · Accepted Answer

私が知っている最良の例はquicksortです。再帰を使用すると、はるかに簡単になります。を見てみましょう：

shop.oreilly.com/product/9780596510046.do

www.amazon.com/Beautiful-Code-Leading-Programmers-Practice/dp/0596510047

(第 3 章の最初のサブタイトル「私が今までに書いた中で最も美しいコード」をクリックしてください)。

score 1 · Accepted Answer

平均的な場合のO（n）で中央値を見つける。k = n / 2の場合、n個のリストからk番目に大きいアイテムを見つけるのと同じです。

int kthLargest（list、k、first、last）{j = partition（list、first、last）if（k == j）return list [j] else if（k

ここでpartitionは、ピボット要素を選択し、データを1回通過するときに、ピボットよりも小さいアイテムが最初に来て、次にピボット、次にピボットよりも大きいアイテムが来るようにリストを再配置します。「kthLargest」アルゴリズムはクイックソートに非常に似ていますが、リストの片側でのみ繰り返されます。

私にとって、これは反復アルゴリズムよりも高速に実行される最も単純な再帰アルゴリズムです。kに関係なく、平均して2*nの比較を使用します。これは、kを実行してデータを通過させ、毎回最小値を見つけて破棄するという単純なアプローチよりもはるかに優れています。

アレホ

score 1 · Accepted Answer

概念形成のプロセスである帰納的推論は、本質的に再帰的です。あなたの脳は、現実の世界で常にそれを行っています。

score 1 · Accepted Answer

ほとんどの場合、再帰は、再帰的なデータ構造を扱うのに非常に自然です。これは基本的にリスト構造とツリー構造を意味します。しかし、再帰は、クイックソートやバイナリ検索などの分割統治法によって、何らかの方法でその場でツリー構造を/作成/するための優れた自然な方法でもあります。

あなたの質問はある意味で少し見当違いだと思います。深さ優先検索について現実世界ではないものは何ですか? 深さ優先検索でできることはたくさんあります。

たとえば、私が考えたもう 1 つの例は、再帰降下コンパイルです。多くの実世界のコンパイラで使用されてきた実世界の問題としては十分です。しかし、それは DFS であると主張することもできます。これは基本的に、有効な解析ツリーの深さ優先検索です。

score 1 · Accepted Answer

コンパイラに関するコメントも同様です。抽象構文木ノードは、自然に再帰に役立ちます。すべての再帰的なデータ構造 (リンクされたリスト、ツリー、グラフなど) も、再帰を使用するとより簡単に処理できます。私たちのほとんどは、現実世界の問題の種類のために、学校を卒業すると再帰をあまり使用しないと思いますが、オプションとしてそれを認識することは良いことです.

score 1 · Accepted Answer

再帰なしで書くのははるかに困難だったであろう XML パーサーを一度書きました。

いつでもスタックと反復を使用できると思いますが、再帰が非常にエレガントな場合もあります。

score 1 · Accepted Answer

自然数の乗算は、再帰の実際の例です。

To multiply x by y
  if x is 0
    the answer is 0
  if x is 1
    the answer is y
  otherwise
    multiply x - 1 by y, and add x

score 1 · Accepted Answer

電話会社やケーブル会社は、実際には大規模なネットワークまたはグラフである配線トポロジのモデルを維持しています。再帰は、すべての親要素またはすべての子要素を検索する場合に、このモデルをトラバースする 1 つの方法です。

再帰は処理とメモリの観点からコストがかかるため、この手順は通常、トポロジが変更され、結果が変更された事前順序付きリスト形式で格納される場合にのみ実行されます。

score 1 · Accepted Answer

ツリーまたはグラフのデータ構造を持つプログラムには、何らかの再帰が含まれる可能性があります。

score 1 · Accepted Answer

スタックオーバーフローを引き起こすという実際的な制限がない場合は、反復を使用するすべてが再帰でより自然に行われます;-)

しかし、真剣に再帰と反復は非常に互換性があり、再帰を使用してすべてのアルゴリズムを書き換えて反復を使用したり、その逆を行ったりできます。数学者は再帰が好きで、プログラマーは反復が好きです。それがおそらく、あなたが言及したこれらの不自然な例をすべて目にする理由でもあります。数学者が再帰を好む理由には、数学的帰納法と呼ばれる数学的証明の方法が関係していると思います。 http://en.wikipedia.org/wiki/Mathematical_induction

score 1 · Accepted Answer

12345.67 のような数値を「12,345 ドル 67 セント」に変換する関数を作成します。

score 0 · Accepted Answer

これは本当に言語に依存すると思います。一部の言語、たとえばLispでは、再帰は問題に対する自然な応答であることがよくあります（多くの場合、これが当てはまる言語では、コンパイラは再帰を処理するように最適化されています）。

リストの最初の要素に対して操作を実行し、次に値または新しいリストを蓄積するためにリストの残りの部分で関数を呼び出すというLispの一般的なパターンは、非常にエレガントで、多くのことを行う最も自然な方法です。その言語のもの。Javaでは、それほど多くはありません。

score 0 · Accepted Answer

DataContractSerializer を使用してクラスをシリアル化する必要があるかどうかを判断する再帰関数を作成しました。大きな問題は、データコントラクトのシリアル化が必要な他のタイプをクラスに含めることができるテンプレート/ジェネリックにありました...そのため、各タイプを通過します。

score 0 · Accepted Answer

それらを使用して、SQL パス検索を行います。

また、デバッグは骨の折れる作業であり、貧弱なプログラマーがそれを台無しにするのは非常に簡単です。

score 0 · Accepted Answer

0

プラグイン: http://picogen.deviantart.com/gallery/

ここに画像の説明を入力

于 2011-09-13T20:03:00.640 に答える

score 0 · Accepted Answer

大学貯蓄計画: A(n) = n か月後の大学の貯蓄額 A(0) = 500 ドル毎月 50 ドルが年利 5% の口座に入金されます。

それでA(n) = A(n-1) + 50 + 0.05*(1/12)* A(N-1)

score 0 · Accepted Answer

再帰は非常に基本的なプログラミング手法であり、非常に多くの問題に役立つため、それらをリストすることは、何らかの加算を使用して解決できるすべての問題をリストするようなものです。Project Euler の Lisp ソリューションを調べてみたところ、次のことがわかりました: クロス合計関数、数字マッチング関数、スペースを検索するためのいくつかの関数、最小限のテキストパーサー、数値を 10 進数のリストに分割する関数、関数グラフの構築、および入力ファイルをトラバースする関数。

問題は、今日のほとんどの主流のプログラミング言語ではないにしても、多くの言語が末尾呼び出しの最適化を備えていないため、深い再帰が実行できないことです。この不十分さは、ほとんどのプログラマーがこの自然な考え方を放棄せざるを得ず、代わりに、間違いなく洗練されていない他のループ構造に依存することを余儀なくされていることを意味します。

score 0 · Accepted Answer

subsonic を使用してデータベーステーブルからツリー構造のメニューを生成する方法。

public MenuElement(BHSSiteMap node, string role)
    {
        if (CheckRole(node, role))
        {
            ParentNode = node;

            // get site map collection order by sequence
            BHSSiteMapCollection children = new BHSSiteMapCollection();

            Query q = BHSSiteMap.CreateQuery()
                    .WHERE(BHSSiteMap.Columns.Parent, Comparison.Equals, ParentNode.Id)
                    .ORDER_BY(BHSSiteMap.Columns.Sequence, "ASC");

            children.LoadAndCloseReader(q.ExecuteReader());

            if (children.Count > 0)
            {
                ChildNodes = new List<MenuElement>();

                foreach (BHSSiteMap child in children)
                {
                    MenuElement childME = new MenuElement(child, role);
                    ChildNodes.Add(childME);
                }
            }
        }
    }

score 0 · Accepted Answer

C# でツリーを作成して、デフォルトケースの 6 セグメントキーを持つテーブルのルックアップを処理しました (key[0] が存在しない場合は、デフォルトケースを使用して続行します)。検索は再帰的に行われました。辞書の辞書の辞書（など）を試してみましたが、すぐに複雑になりすぎました。

また、ツリーに格納された方程式を評価して正しい評価順序を取得する数式エバリュエーターを C# で作成しました。確かに、これは問題に対して不適切な言語を選択した可能性が高いですが、興味深い演習でした。

人々が行ったことの例はあまり見ませんでしたが、むしろ彼らが使用したライブラリを見ました。うまくいけば、これがあなたに考える何かを与えるでしょう.

score 0 · Accepted Answer

0

円の端を見つけるなど、GIS または地図作成のための幾何学的計算。

于 2008-09-19T22:15:05.707 に答える

score 0 · Accepted Answer

平方根を求める方法は再帰的です。現実世界で距離を計算するのに便利です。

score 0 · Accepted Answer

素数を見つける方法は再帰的です。大きな数の因数を使用するさまざまな暗号化方式のハッシュキーの生成に役立ちます。

score 0 · Accepted Answer

建物があります。建物には20の部屋があります。法的には、各部屋に一定の人数しか入れることができません。あなたの仕事は、人を部屋に自動的に割り当てることです。部屋がいっぱいになったら、空いている部屋を探す必要があります。特定の部屋だけが特定の人を収容できることを考えると、どの部屋にも注意する必要があります。

例えば：

部屋1、2、3は互いにロールインできます。この部屋は自力で歩けない子供のためのものなので、注意散漫やその他の病気を避けるために、他のすべてのものから遠ざける必要があります (高齢者には問題ありませんが、6 か月になると非常に悪化する可能性があります. 3つすべてが満員の場合、その人は入場を拒否されなければなりません。

部屋4、5、6は互いに転がり込むことができます。この部屋はピーナッツにアレルギーのある人のためのものです。したがって、他の部屋には入ることができません（ピーナッツが入っている可能性があります）。3つすべてが満杯になった場合は、アレルギーレベルを尋ねる警告を提供し、アクセスを許可することができます.

部屋はいつでも変更できます。そのため、部屋 7 ～ 14 をピーナッツのない部屋にすることができます。チェックする部屋の数がわかりません。

または、年齢に基づいて分けたいと思うかもしれません。学年、性別など。これらは私が見つけたほんの一例です。

score 0 · Accepted Answer

私が持っている最後の実世界の例はかなり軽薄ですが、再帰が「ちょうど合う」場合があることを示しています。

私は Chain of Responsibility パターンを使用していたので、Handler オブジェクトはリクエスト自体を処理するか、リクエストをチェーンに委譲します。チェーンの構築をログに記録すると便利です。

public String getChainString() {
    cs = this.getClass().toString();
    if(this.delegate != null) {
        cs += "->" + delegate.getChainString();
    }
    return cs;
}

メソッドは「それ自体」を呼び出しますが、呼び出されるたびに異なるインスタンスにあるため、これは最も純粋な再帰ではないと主張できます。

score 0 · Accepted Answer

作成された画像がサイズ制限されたボックス内で機能するかどうかを確認します。

function check_size($font_size, $font, $text, $width, $height) {
        if (!is_string($text)) {
            throw new Exception('Invalid type for $text');
        }   
        $box = imagettfbbox($font_size, 0, $font, $text);
        $box['width'] = abs($box[2] - $box[0]);
        if ($box[0] < -1) {
            $box['width'] = abs($box[2]) + abs($box[0]) - 1;
        }   
        $box['height'] = abs($box[7]) - abs($box[1]);
        if ($box[3] > 0) {
            $box['height'] = abs($box[7] - abs($box[1])) - 1;
        }   
        return ($box['height'] < $height && $box['width'] < $width) ? array($font_size, $box['width'], $height) : $this->check_size($font_size - 1, $font, $text, $width, $height);
    }

score 0 · Accepted Answer

あなたはコンピューターサイエンスや数学の例が好きではないようなので、別の例としてワイヤーパズルを紹介します。

多くのワイヤーパズルでは、ワイヤーリングに出し入れして、ワイヤーの長い閉じたループを取り除きます。これらのパズルは再帰的です。その一つが「アローダイナミクス」と呼ばれるものです。「arrow dynamics wire puzzle」でググると出てくると思います

これらのパズルは、ハノイの塔によく似ています。

score 0 · Accepted Answer

2 つの異なるが類似したシーケンスがあり、各シーケンスのコンポーネントを一致させて、最初に大きな連続したチャンクが優先され、次に同じシーケンス順序が優先されるようにしたい場合は、それらのシーケンスを再帰的に分析してツリーを形成し、そのツリーを再帰的に処理して平坦化できます。それ。

参考： 再帰とメモ化のサンプルコード

score -3 · Accepted Answer

間接再帰の実際の例は、クリスマスにそのビデオゲームを持っていいかどうか両親に尋ねることです。お父さん：「お母さんに聞いて」… お母さん：「お父さんに聞いて」[要するに、「いいえ、しかし、あなたがかんしゃくを起こさないように、私たちはあなたに言いたくありません。」]

score -3 · Accepted Answer

ハノイの塔

対話できるものは次のとおりです: http://www.mazeworks.com/hanoi/

再帰関係を使用して、このソリューションに必要な移動の正確な数は次のように計算できます。 − 1 + 1。参照: http://en.wikipedia.org/wiki/Towers_of_hanoi#Recursive_solution

recursion - 再帰の実例

55 に答える 55

再帰の実例

SICPの有名な評価/適用サイクル

Related

Reference