Recursionは、問題（または問題の解決策）を（より単純なバージョンの）それ自体に関して定義するプロセスです。

たとえば、”find your way home”という操作を次のように定義できます。

  1. 家にいる場合は、移動を停止します。

  2. 家に向かって一歩を踏み出してください。

  3. “あなたの家に帰る方法を見つける”。

ここでは、家に帰る方法を見つけるための解決策は二つのステップ（三つのステップ）です。 まず、すでに家にいる場合、私たちは家に帰りません。, 第二に、我々は我々の状況を解決するために簡単になり、非常に簡単なアクションを行います。 最後に、アルゴリズム全体をやり直します。

上記の例は末尾再帰と呼ばれます。 これは、最後の文が再帰アルゴリズムを呼び出している場所です。 末尾再帰は直接ループに変換することができます。

寺の広場を見つけるための再帰的な”アルゴリズム”をどのように書きますか？

再帰のもう一つの例は、数値のリストで最大値を見つけることです。 リスト内の最大値は、最初の数値または残りの数値のうち最大の数値のいずれかです。, アルゴリズムの擬似コードを書く方法は次のとおりです。

再帰アルゴリズムの一部

すべての再帰アルゴリズムには次のものが必要です。

  1. ベースケース（すなわち、いつ停止するか）

  2. ベースケースに向かって作業する

  3. 再帰呼び出し（すなわち、自分自身を呼び出す）

“ベースケースに向かって作業する”は次のとおりです。

“ベースケースに向かって作業する”は次のとおりです。ここで、問題をより簡単にする（例えば、リストを二つの部分に分割し、それぞれ元の部分よりも小さくする）。 再帰呼び出しは、問題のより単純なバージョンを解決するために同じアルゴリズムを使用する場所です。, ベースケースは、”最も単純な”可能な問題の解決策です（たとえば、”リスト内の最大数を見つける”問題のベースケースは、リストが一つの番号しか持っていない場合.. そして、定義によって、一つだけの数がある場合、それは最大です）。

簡単な例：三つの数字を追加します

三つの数字を追加することは、最初の二つの数字を追加し、その後、再びこれら二つの数字を追加すること

(Matlabでは、すべての引数なしで関数を呼び出すことができます。 Nargin関数は、指定された値の数をコンピューターに通知します。, したがって、add_numbers(1)は1のnarginを持ち、add_numbers(1,1)は2のnarginを持ち、add_numbers(1,1,1)は3のnarginを持ちます。)

再帰アルゴリズムの3つの部分を特定します。

すべての再帰アルゴリズムには、次の三つの段階が必要です。

再帰が機能する理由

再帰アルゴリズムでは、コンピュータは問題の以前のすべての状態を”記憶”します。 この情報は、コンピュータが”アクティベーションスタック”（つまり、各機能ワークスペース内）に”保持”されます。

すべての関数には、関数の呼び出しごとに独自のワークスペースがあります。,

迷路の例:

各部屋に北、南、東、西の側面にドアがある場合とない場合があります部屋の長方形のグリッドを考えてみましょう。

どのように迷路から抜け出す方法を見つけるのですか？ 答えを見つけるための一つの可能な”アルゴリズム”があります：

現在の部屋のすべてのドアについて、ドアが出口につながる場合は、そのドアを取

ここでの”トリック”はもちろんですが、ドアが出口につながる部屋につながるかどうかをどのように知っていますか？ 答えは私達ではないですが、私達はコンピュータが私達のためにそれを把握させてもいいです。

上記のアルゴリズムの再帰的な部分は何ですか？, その”ドアは迷路の外につながる”。 ドアが迷路から出てくるかどうかをどのように知るのですか？ 隣の部屋の中（ドアを通って行く）、私たちは同じ質問をするので、私たちは知っています、どのように私たちは迷路から抜け出すのですか？

何が起こるかは、コンピュータがすべての”what ifs”を”記憶”することです。 私が最初のドアを取る場合はどうなりますか、私は第二のドアを取る場合はどうなりますか、私は隣のドアを取る場合など。 そして、あなたが通過することができるすべての可能なドアのために、コンピュータはそれらのものを覚えていますifs、そしてその後のすべてのドア、そ

これは実際のコード実装に近いものです。,

質問：上記の基本ケースは何ですか？

答え：（それはトリックの質問でした）コードには基本ケースはありません。 部屋が出口であるかどうかは、開始時に確認する必要があります。 そうであれば、再帰はありません！ 

  function success = find_way_out( maze, room ) if room is exit → return true room ← mark as visited % rest of code ... end

質問：どのように訪問したように部屋をマークしますか？

答え：さまざまな技術があります。 ルームが構造体（またはオブジェクト）の場合は、visitedフィールドの方向をルームに追加できます。 （例えば、部屋。visited=true;）オブジェクトを使用していない場合は、迷路と同じサイズ/形状のブールフラグの行列を持ち、これらの値を使用することができます。,

質問：上記のアルゴリズムの他の問題はありますか？

答え：それに対する答えは、次の質問について考えることによって見つけることができます：迷路がすべての壁にドアを持つそれぞれが同じサイズの長方形の部屋の巨大なグリッドであった場合はどうなりますか？ 最初のドアを通って北に行き、次に次の部屋のドアを通って東に行き、次にその部屋のドアを通って南に行き、次にその部屋のドアを通って西に行く どこで終わるのですか？ あなたが始めた場所に戻って！ さらに悪いことに、このループを永遠に続ける可能性があります。 勇敢な冒険家はこの問題をどのように解決するのでしょうか？,

それに対する一つの答えは、チョークの部分を使用して、あなたが入るすべての部屋の床に大きなXを置くことです。 従って床のXが付いている部屋に戻って来るとき、入る必要はないことを知っている。 プログラムの場合、booleanフラグ”seen”または”visited”を使用する必要があります。 すべての部屋には旗があります。 すべての部屋は、フラグがfalseに設定されて始まります。 ルームを訪問するときは、フラグをtrueに設定します。, 最後に、”基本ケース”では、次のような行があります。

  function success = find_way_out( maze, room ) % exit chack if room is visited → return false % rest of code ... end

再帰は、コンピュータアルゴリズムにも同様に適用できます。

コンピュータ関連の例には、数のリストを追加する、フィボナッチ数列を計算する、階乗を計算する、数独を計算するなどがあります。

ループと末尾再帰

いくつかの再帰アルゴリズムはループと非常によく似ています。 これらのアルゴリズムは”末尾再帰”と呼ばれます。 末尾再帰アルゴリズムは直接ループに変換できます。