ZAMYLA：理解するために 再帰は、以下を行う必要があり 最初の再帰を理解しています。 プログラム設計手段に再帰を持つ あなたは自己参照を持っていることを 定義。 再帰的なデータ構造、例えば、 データ構造は、その で自分自身を含める その定義。 しかし、今日、我々は集中するつもりだ 再帰関数に。 

関数が入力を取ることを思い出して、 引数、およびそのように値を返す に代表される出力 ここでこの図。 私たちは、体のように箱を考えるよ のセットを含む関数、 解釈の指示 入力及び出力を提供する。 体の内部を詳しく見てとる この関数はへの呼び出しを明らかにしなかった 他の機能にも。 この単純な関数を取る、fooという、その 入力として1つの文字列を受け取り、 版画何の手紙 その文字列があります。 文字列の長さの関数はstrlen、、 その出力である、と呼ばれている printfのへの呼び出しのために必要。 

今、何が再帰関数を作る 特別な、それが自分自身を呼び出すことです。 私たちは、この再帰を表すことができます このオレンジ色の矢印でコール バック自体にループする。 しかし、再び自分自身を実行することだけでしょう 別の再帰呼び出しを行い、 別の、もう。 しかし、再帰関数 無限にすることはできません。 彼らは何とか終わらなければならない、あるいは、あなたの プログラムは永遠に実行されます。 

だから我々は破る方法を見つける必要がある 再帰呼び出しが不足しています。 私たちは、基本ケース、これを呼び出します。 ベースケース条件が満たされたときに、 この関数はせずに返します 別の再帰呼び出し。 HI、void関数をこの関数を取る すなわち、入力としてint型のnを取ります。 ベースケースは最初に来る。 nが0未満である場合、印刷してバイバイ その他の場合のお返し、 この関数はハイテク印刷して実行されます 再帰呼び出し。 を持つ関数こんにちはへの別の呼び出し デクリメント入力値。 

今、我々はハイ印刷にもかかわらず、 この関数は、私たちまで終了しません その戻り値の型を返す、 この場合のボイド中。 したがって、すべてのNベースケース以外では、 この関数こんにちはこんにちは戻ります Nのマイナス1。 この関数は、しかし無効となりますので、 ここで明示的に戻り値の型はありません。 我々だけで機能を実行します。 だから、（3）のHiが出力されますこんにちは呼び出し、 ハイ（2）、（1）1ハイを実行する実行 ハイを実行する（0）ここで、 ベースケース条件が満たされている。 だから、ハワイ（0）BYE出力し、リターン。 

[OK]をクリックします。 だから今我々は基本を理解していること 彼らが必要とする再帰関数、 少なくとも1つのベースケースだけでなく、 再帰呼び出し、のはに移りましょう より意味のある例。 ただ返さない一 何に関係なく無効になる。 

の階乗を見てみましょう 最も一般的に使用される操作 確率の計算。 nの階乗は、すべての製品である 未満の正の整数 そしてnに等しい。 そう階乗5は5倍4倍である 3回2回1 120を得た。 四階乗は4回3回です 2回1 24を得た。 同じルールが適用されます 任意の正の整数に。 

では、どのように再帰的に書くかもしれません 階乗を計算する関数 数の？ まあ、我々は両方を識別する必要があります ベースケースと再帰呼び出し。 再帰呼び出しは同じになります ベースを除くすべてのケースについて 我々はする必要がありますことを意味した場合、 私たちに与えるパターンを見つける私たちの 望ましい結果。 

この例では、どのように5の階乗を参照してください。 1によって2で3で4を乗じ関与 そして、それは非常に同じ乗算 、ここで発見された 4の階乗の定義。 だから我々は5の階乗であることがわかり ただ5回4階乗。 今、このパターンが適用されません 階乗4にも同様に？ はい。 私たちは、4の階乗が含まれていることを参照してください。 乗算3回2回1、 3階乗として非常に同じ定義。 そう4階乗は4倍に等しい3 階乗などなど我々の パターンは、1階乗までこだわった 定義により1に等しい。 

他の正はありません 整数は残しました。 だから我々はのためのパターンを持っている 私たちの再帰呼び出し。 nの階乗をn倍に等しい nの階乗マイナス1。 そして、我々のベースケース？ それはちょうど我々の定義になるでしょう 1階乗の。 

だから今、私たちは、書面に進むことができます 関数のコード。 基本ケースのために、我々は持っているだろう 条件nが1に等しいと、等しい 我々は1が返されます。 そして、再帰呼び出しに移動し、 我々は、n回戻ります nの階乗マイナス1。 

それでは、私たちのこれをテストしてみましょう。 それでは階乗4を試してみましょう。 私達の機能ごとにそれは等しいです 4回階乗（3）。 階乗は（3）に等しい 3回の階乗（2）。 階乗は（2）2倍に等しい 1を返し階乗（1）、。 階乗は（2）現在、2回1、2を返します。 階乗は（3）今戻ることができます 3回2、6。 そして最後に、階乗（4） 4回6、24を返します。 

あなたはどんな困難に遭遇している場合 再帰呼び出しで、それをふり この関数は、すでに動作します。 私はこれで意味することは、あなたがしなければならないということです 復帰への再帰呼び出しを信頼 正しい値。 例えば、私が知っている場合、その 階乗（5）は、5倍に等しい 階乗（4）、私はそれを信頼するつもりだ 階乗は（4）私に24を与える。 もしあれば、変数として考えて 、あるかのようにすでに定義されます 階乗（4）。 したがって、すべての階乗（N）のために、それはだ Nとの積 前の階乗。 そして、この前の階乗 呼び出すことによって得られる nの階乗マイナス1。 

あなたが実装できるかどうか、今、参照してください。 再帰的な自分を機能します。 ご使用の端末をロード、またはrun.cs50.net、 と関数の合計を送る すなわち整数nを受け取り、返し すべての連続した​​正の合計 nは1の整数。 私はいくつかの合計を書いた 私たちのお手伝いをする値。 まず、把握 ベースケース条件。 次に、（5）の和を見てください。 あなたは用語でそれを表現することができます 別の合計の？ 今、何を（4）の和はどうでしょうか？ どのようにして和を表現することができます（4） 別の合計の面で？ 

あなたは合計を取得したら（5）と和（4） 他の和で表さ参照 あなたが特定できる場合 和するためのパターン（N）。 そうでない場合は、他のいくつかの数字を試してみてください とその合計エクスプレス 別の数値に換算。 離散的なパターンを識別することにより、 数字は、あなたがにあなたの方法にもしている 任意のnのパターンを識別する。 

再帰は本当に強力なツールですが、 これは勿論、これらに限定されないです 数学関数。 再帰は非常に効果的に使用することができる 例えば木を扱うとき。 のために木に短いをチェックしてください より徹底した見直しが、今の で、その二分探索木をリコール 特に、各ノードで構成されている 値と2ノードポインタと。 通常、これは次式で表される。 一行のポインティングを有する親ノード 左の子ノードと1に 右の子ノードへ。 バイナリサーチの構造 ツリーがよく適しています 再帰検索する。 再帰呼び出しのいずれかを渡し 左右どちらかのノードが、より多くの ツリー要するにそれの。 

あなたが上で操作を実行したいとし バイナリツリー内のすべての単一のノード。 どのようにそのことについてに行くのでしょうか？ さて、あなたは再帰を書くことができます 演算を実行する関数 親ノード上と再帰を作る 同じ関数を呼び出して、 左に通過させ、 右の子ノード。 たとえば、この機能、fooという、その 指定されたノードの値を変更し、 1にそのすべての子。 ヌルノード原因のベースケース 返す関数、を示す 任意のノードが存在しないことを そのサブツリーに残しました。 

のは、それを見てみましょう。 最初の親は13です。 我々は、値を1に変更して、呼び出し 私たちの左の機能だけでなく、 右のように。 関数fooが、左側に呼び出された 最初の部分木なので、左ノード 1とfooに再割り当てされます そのノードの子で呼び出される、 最初の左と右、 などなど。 そして枝が持っていないことを伝える 同じプロセスので、任意のより多くの子供 右の子供たちのために継続します ツリー全体のノードがあるまで、 1に再割り当て。 

ご覧のように、あなたが制限されず、 ちょうど1再帰呼び出し。 仕事を得るでしょうと同じくらい多くの。 あなたはそれぞれのツリーを持っていた場合はどう ノードには3人の子供がいた、 左、中央、右の？ どのようにfooという編集のでしょうか？ さて、簡単な。 ちょうど別の再帰呼び出しを追加し、 中央のノードポインタを渡す。 

再帰はに非常に強力ではありません エレガントな言及が、それはすることができます 最初は難しい概念、​​そうである 患者とあなたの時間がかかる。 基本ケースで始まる。 これは通常、特定するのが最も簡単です、 そして、あなたは働くことができる 後方そこから。 あなたは、あなたのに到達する必要が知っている ベースケースなので、そのマイト あなたにいくつかのヒントを与える。 中1の特定の場合を表現しよう 他のケースの面、またはサブセットで。 

この短いを見てくれてありがとう。 少なくとも、今することができます このようなジョークを理解しています。 私の名前はZamylaであり、これはCS50である。 

こんにちは、この関数を取る、A かかる無効機能 int型、N、入力として。 ベースケースは最初に来る。 nは0、印刷​​未満である場合 「BYE」とリターン。