>> 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」とリターン。