1
00:00:00,000 --> 00:00:07,800

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA：理解するために
再帰は、以下を行う必要があり

3
00:00:10,190 --> 00:00:13,820
最初の再帰を理解しています。

4
00:00:13,820 --> 00:00:17,280
プログラム設計手段に再帰を持つ
あなたは自己参照を持っていることを

5
00:00:17,280 --> 00:00:18,570
定義。

6
00:00:18,570 --> 00:00:21,520
再帰的なデータ構造、例えば、
データ構造は、その

7
00:00:21,520 --> 00:00:23,990
で自分自身を含める
その定義。

8
00:00:23,990 --> 00:00:27,160
しかし、今日、我々は集中するつもりだ
再帰関数に。

9
00:00:27,160 --> 00:00:31,160
>> 関数が入力を取ることを思い出して、
引数、およびそのように値を返す

10
00:00:31,160 --> 00:00:34,480
に代表される出力
ここでこの図。

11
00:00:34,480 --> 00:00:38,060
私たちは、体のように箱を考えるよ
のセットを含む関数、

12
00:00:38,060 --> 00:00:42,340
解釈の指示
入力及び出力を提供する。

13
00:00:42,340 --> 00:00:45,660
体の内部を詳しく見てとる
この関数はへの呼び出しを明らかにしなかった

14
00:00:45,660 --> 00:00:47,430
他の機能にも。

15
00:00:47,430 --> 00:00:51,300
この単純な関数を取る、fooという、その
入力として1つの文字列を受け取り、

16
00:00:51,300 --> 00:00:54,630
版画何の手紙
その文字列があります。

17
00:00:54,630 --> 00:00:58,490
文字列の長さの関数はstrlen、、
その出力である、と呼ばれている

18
00:00:58,490 --> 00:01:01,890
printfのへの呼び出しのために必要。

19
00:01:01,890 --> 00:01:05,770
>> 今、何が再帰関数を作る
特別な、それが自分自身を呼び出すことです。

20
00:01:05,770 --> 00:01:09,610
私たちは、この再帰を表すことができます
このオレンジ色の矢印でコール

21
00:01:09,610 --> 00:01:11,360
バック自体にループする。

22
00:01:11,360 --> 00:01:15,630
しかし、再び自分自身を実行することだけでしょう
別の再帰呼び出しを行い、

23
00:01:15,630 --> 00:01:17,150
別の、もう。

24
00:01:17,150 --> 00:01:19,100
しかし、再帰関数
無限にすることはできません。

25
00:01:19,100 --> 00:01:23,490
彼らは何とか終わらなければならない、あるいは、あなたの
プログラムは永遠に実行されます。

26
00:01:23,490 --> 00:01:27,680
>> だから我々は破る方法を見つける必要がある
再帰呼び出しが不足しています。

27
00:01:27,680 --> 00:01:29,900
私たちは、基本ケース、これを呼び出します。

28
00:01:29,900 --> 00:01:33,570
ベースケース条件が満たされたときに、
この関数はせずに返します

29
00:01:33,570 --> 00:01:34,950
別の再帰呼び出し。

30
00:01:34,950 --> 00:01:39,610
HI、void関数をこの関数を取る
すなわち、入力としてint型のnを取ります。

31
00:01:39,610 --> 00:01:41,260
ベースケースは最初に来る。

32
00:01:41,260 --> 00:01:46,220
nが0未満である場合、印刷してバイバイ
その他の場合のお返し、

33
00:01:46,220 --> 00:01:49,400
この関数はハイテク印刷して実行されます
再帰呼び出し。

34
00:01:49,400 --> 00:01:53,600
を持つ関数こんにちはへの別の呼び出し
デクリメント入力値。

35
00:01:53,600 --> 00:01:56,790
>> 今、我々はハイ印刷にもかかわらず、
この関数は、私たちまで終了しません

36
00:01:56,790 --> 00:02:00,370
その戻り値の型を返す、
この場合のボイド中。

37
00:02:00,370 --> 00:02:04,830
したがって、すべてのNベースケース以外では、
この関数こんにちはこんにちは戻ります

38
00:02:04,830 --> 00:02:06,890
Nのマイナス1。

39
00:02:06,890 --> 00:02:10,050
この関数は、しかし無効となりますので、
ここで明示的に戻り値の型はありません。

40
00:02:10,050 --> 00:02:12,000
我々だけで機能を実行します。

41
00:02:12,000 --> 00:02:16,960
だから、（3）のHiが出力されますこんにちは呼び出し、
ハイ（2）、（1）1ハイを実行する実行

42
00:02:16,960 --> 00:02:20,560
ハイを実行する（0）ここで、
ベースケース条件が満たされている。

43
00:02:20,560 --> 00:02:24,100
だから、ハワイ（0）BYE出力し、リターン。

44
00:02:24,100 --> 00:02:24,990
>> [OK]をクリックします。

45
00:02:24,990 --> 00:02:28,690
だから今我々は基本を理解していること
彼らが必要とする再帰関数、

46
00:02:28,690 --> 00:02:32,730
少なくとも1つのベースケースだけでなく、
再帰呼び出し、のはに移りましょう

47
00:02:32,730 --> 00:02:34,120
より意味のある例。

48
00:02:34,120 --> 00:02:37,830
ただ返さない一
何に関係なく無効になる。

49
00:02:37,830 --> 00:02:41,340
>> の階乗を見てみましょう
最も一般的に使用される操作

50
00:02:41,340 --> 00:02:43,660
確率の計算。

51
00:02:43,660 --> 00:02:48,120
nの階乗は、すべての製品である
未満の正の整数

52
00:02:48,120 --> 00:02:49,400
そしてnに等しい。

53
00:02:49,400 --> 00:02:56,731
そう階乗5は5倍4倍である
3回2回1 120を得た。

54
00:02:56,731 --> 00:03:01,400
四階乗は4回3回です
2回1 24を得た。

55
00:03:01,400 --> 00:03:04,910
同じルールが適用されます
任意の正の整数に。

56
00:03:04,910 --> 00:03:08,670
>> では、どのように再帰的に書くかもしれません
階乗を計算する関数

57
00:03:08,670 --> 00:03:09,960
数の？

58
00:03:09,960 --> 00:03:14,700
まあ、我々は両方を識別する必要があります
ベースケースと再帰呼び出し。

59
00:03:14,700 --> 00:03:18,250
再帰呼び出しは同じになります
ベースを除くすべてのケースについて

60
00:03:18,250 --> 00:03:21,420
我々はする必要がありますことを意味した場合、
私たちに与えるパターンを見つける私たちの

61
00:03:21,420 --> 00:03:23,350
望ましい結果。

62
00:03:23,350 --> 00:03:30,270
>> この例では、どのように5の階乗を参照してください。
1によって2で3で4を乗じ関与

63
00:03:30,270 --> 00:03:33,010
そして、それは非常に同じ乗算
、ここで発見された

64
00:03:33,010 --> 00:03:35,430
4の階乗の定義。

65
00:03:35,430 --> 00:03:39,810
だから我々は5の階乗であることがわかり
ただ5回4階乗。

66
00:03:39,810 --> 00:03:43,360
今、このパターンが適用されません
階乗4にも同様に？

67
00:03:43,360 --> 00:03:44,280
はい。

68
00:03:44,280 --> 00:03:49,120
私たちは、4の階乗が含まれていることを参照してください。
乗算3回2回1、

69
00:03:49,120 --> 00:03:51,590
3階乗として非常に同じ定義。

70
00:03:51,590 --> 00:03:56,950
そう4階乗は4倍に等しい3
階乗などなど我々の

71
00:03:56,950 --> 00:04:02,170
パターンは、1階乗までこだわった
定義により1に等しい。

72
00:04:02,170 --> 00:04:04,950
>> 他の正はありません
整数は残しました。

73
00:04:04,950 --> 00:04:07,870
だから我々はのためのパターンを持っている
私たちの再帰呼び出し。

74
00:04:07,870 --> 00:04:13,260
nの階乗をn倍に等しい
nの階乗マイナス1。

75
00:04:13,260 --> 00:04:14,370
そして、我々のベースケース？

76
00:04:14,370 --> 00:04:17,370
それはちょうど我々の定義になるでしょう
1階乗の。

77
00:04:17,370 --> 00:04:19,995
>> だから今、私たちは、書面に進むことができます
関数のコード。

78
00:04:19,995 --> 00:04:24,110
基本ケースのために、我々は持っているだろう
条件nが1に等しいと、等しい

79
00:04:24,110 --> 00:04:25,780
我々は1が返されます。

80
00:04:25,780 --> 00:04:29,280
そして、再帰呼び出しに移動し、
我々は、n回戻ります

81
00:04:29,280 --> 00:04:32,180
nの階乗マイナス1。

82
00:04:32,180 --> 00:04:33,590
>> それでは、私たちのこれをテストしてみましょう。

83
00:04:33,590 --> 00:04:35,900
それでは階乗4を試してみましょう。

84
00:04:35,900 --> 00:04:39,420
私達の機能ごとにそれは等しいです
4回階乗（3）。

85
00:04:39,420 --> 00:04:43,040
階乗は（3）に等しい
3回の階乗（2）。

86
00:04:43,040 --> 00:04:48,700
階乗は（2）2倍に等しい
1を返し階乗（1）、。

87
00:04:48,700 --> 00:04:52,490
階乗は（2）現在、2回1、2を返します。

88
00:04:52,490 --> 00:04:55,960
階乗は（3）今戻ることができます
3回2、6。

89
00:04:55,960 --> 00:05:02,490
そして最後に、階乗（4）
4回6、24を返します。

90
00:05:02,490 --> 00:05:06,780
>> あなたはどんな困難に遭遇している場合
再帰呼び出しで、それをふり

91
00:05:06,780 --> 00:05:09,660
この関数は、すでに動作します。

92
00:05:09,660 --> 00:05:13,450
私はこれで意味することは、あなたがしなければならないということです
復帰への再帰呼び出しを信頼

93
00:05:13,450 --> 00:05:15,100
正しい値。

94
00:05:15,100 --> 00:05:18,960
例えば、私が知っている場合、その
階乗（5）は、5倍に等しい

95
00:05:18,960 --> 00:05:24,870
階乗（4）、私はそれを信頼するつもりだ
階乗は（4）私に24を与える。

96
00:05:24,870 --> 00:05:28,510
もしあれば、変数として考えて
、あるかのようにすでに定義されます

97
00:05:28,510 --> 00:05:30,070
階乗（4）。

98
00:05:30,070 --> 00:05:33,850
したがって、すべての階乗（N）のために、それはだ
Nとの積

99
00:05:33,850 --> 00:05:35,360
前の階乗。

100
00:05:35,360 --> 00:05:38,130
そして、この前の階乗
呼び出すことによって得られる

101
00:05:38,130 --> 00:05:41,330
nの階乗マイナス1。

102
00:05:41,330 --> 00:05:45,130
>> あなたが実装できるかどうか、今、参照してください。
再帰的な自分を機能します。

103
00:05:45,130 --> 00:05:50,490
ご使用の端末をロード、またはrun.cs50.net、
と関数の合計を送る

104
00:05:50,490 --> 00:05:54,770
すなわち整数nを受け取り、返し
すべての連続した​​正の合計

105
00:05:54,770 --> 00:05:57,490
nは1の整数。

106
00:05:57,490 --> 00:06:01,000
私はいくつかの合計を書いた
私たちのお手伝いをする値。

107
00:06:01,000 --> 00:06:04,030
まず、把握
ベースケース条件。

108
00:06:04,030 --> 00:06:06,170
次に、（5）の和を見てください。

109
00:06:06,170 --> 00:06:09,270
あなたは用語でそれを表現することができます
別の合計の？

110
00:06:09,270 --> 00:06:11,290
今、何を（4）の和はどうでしょうか？

111
00:06:11,290 --> 00:06:15,630
どのようにして和を表現することができます（4）
別の合計の面で？

112
00:06:15,630 --> 00:06:19,655
>> あなたは合計を取得したら（5）と和（4）
他の和で表さ参照

113
00:06:19,655 --> 00:06:22,970
あなたが特定できる場合
和するためのパターン（N）。

114
00:06:22,970 --> 00:06:26,190
そうでない場合は、他のいくつかの数字を試してみてください
とその合計エクスプレス

115
00:06:26,190 --> 00:06:28,410
別の数値に換算。

116
00:06:28,410 --> 00:06:31,930
離散的なパターンを識別することにより、
数字は、あなたがにあなたの方法にもしている

117
00:06:31,930 --> 00:06:34,320
任意のnのパターンを識別する。

118
00:06:34,320 --> 00:06:38,040
>> 再帰は本当に強力なツールですが、
これは勿論、これらに限定されないです

119
00:06:38,040 --> 00:06:39,820
数学関数。

120
00:06:39,820 --> 00:06:44,040
再帰は非常に効果的に使用することができる
例えば木を扱うとき。

121
00:06:44,040 --> 00:06:47,210
のために木に短いをチェックしてください
より徹底した見直しが、今の

122
00:06:47,210 --> 00:06:51,140
で、その二分探索木をリコール
特に、各ノードで構成されている

123
00:06:51,140 --> 00:06:53,820
値と2ノードポインタと。

124
00:06:53,820 --> 00:06:57,270
通常、これは次式で表される。
一行のポインティングを有する親ノード

125
00:06:57,270 --> 00:07:01,870
左の子ノードと1に
右の子ノードへ。

126
00:07:01,870 --> 00:07:04,510
バイナリサーチの構造
ツリーがよく適しています

127
00:07:04,510 --> 00:07:05,940
再帰検索する。

128
00:07:05,940 --> 00:07:09,730
再帰呼び出しのいずれかを渡し
左右どちらかのノードが、より多くの

129
00:07:09,730 --> 00:07:10,950
ツリー要するにそれの。

130
00:07:10,950 --> 00:07:15,690
>> あなたが上で操作を実行したいとし
バイナリツリー内のすべての単一のノード。

131
00:07:15,690 --> 00:07:17,410
どのようにそのことについてに行くのでしょうか？

132
00:07:17,410 --> 00:07:20,600
さて、あなたは再帰を書くことができます
演算を実行する関数

133
00:07:20,600 --> 00:07:24,450
親ノード上と再帰を作る
同じ関数を呼び出して、

134
00:07:24,450 --> 00:07:27,630
左に通過させ、
右の子ノード。

135
00:07:27,630 --> 00:07:31,650
たとえば、この機能、fooという、その
指定されたノードの値を変更し、

136
00:07:31,650 --> 00:07:33,830
1にそのすべての子。

137
00:07:33,830 --> 00:07:37,400
ヌルノード原因のベースケース
返す関数、を示す

138
00:07:37,400 --> 00:07:41,290
任意のノードが存在しないことを
そのサブツリーに残しました。

139
00:07:41,290 --> 00:07:42,620
>> のは、それを見てみましょう。

140
00:07:42,620 --> 00:07:44,340
最初の親は13です。

141
00:07:44,340 --> 00:07:47,930
我々は、値を1に変更して、呼び出し
私たちの左の機能だけでなく、

142
00:07:47,930 --> 00:07:49,600
右のように。

143
00:07:49,600 --> 00:07:53,910
関数fooが、左側に呼び出された
最初の部分木なので、左ノード

144
00:07:53,910 --> 00:07:57,730
1とfooに再割り当てされます
そのノードの子で呼び出される、

145
00:07:57,730 --> 00:08:01,900
最初の左と右、
などなど。

146
00:08:01,900 --> 00:08:05,630
そして枝が持っていないことを伝える
同じプロセスので、任意のより多くの子供

147
00:08:05,630 --> 00:08:09,700
右の子供たちのために継続します
ツリー全体のノードがあるまで、

148
00:08:09,700 --> 00:08:11,430
1に再割り当て。

149
00:08:11,430 --> 00:08:15,390
>> ご覧のように、あなたが制限されず、
ちょうど1再帰呼び出し。

150
00:08:15,390 --> 00:08:17,930
仕事を得るでしょうと同じくらい多くの。

151
00:08:17,930 --> 00:08:21,200
あなたはそれぞれのツリーを持っていた場合はどう
ノードには3人の子供がいた、

152
00:08:21,200 --> 00:08:23,100
左、中央、右の？

153
00:08:23,100 --> 00:08:24,886
どのようにfooという編集のでしょうか？

154
00:08:24,886 --> 00:08:25,860
さて、簡単な。

155
00:08:25,860 --> 00:08:30,250
ちょうど別の再帰呼び出しを追加し、
中央のノードポインタを渡す。

156
00:08:30,250 --> 00:08:34,549
>> 再帰はに非常に強力ではありません
エレガントな言及が、それはすることができます

157
00:08:34,549 --> 00:08:38,010
最初は難しい概念、​​そうである
患者とあなたの時間がかかる。

158
00:08:38,010 --> 00:08:39,370
基本ケースで始まる。

159
00:08:39,370 --> 00:08:42,650
これは通常、特定するのが最も簡単です、
そして、あなたは働くことができる

160
00:08:42,650 --> 00:08:43,830
後方そこから。

161
00:08:43,830 --> 00:08:46,190
あなたは、あなたのに到達する必要が知っている
ベースケースなので、そのマイト

162
00:08:46,190 --> 00:08:47,760
あなたにいくつかのヒントを与える。

163
00:08:47,760 --> 00:08:53,120
中1の特定の場合を表現しよう
他のケースの面、またはサブセットで。

164
00:08:53,120 --> 00:08:54,700
>> この短いを見てくれてありがとう。

165
00:08:54,700 --> 00:08:58,920
少なくとも、今することができます
このようなジョークを理解しています。

166
00:08:58,920 --> 00:09:01,250
私の名前はZamylaであり、これはCS50である。

167
00:09:01,250 --> 00:09:04,306

168
00:09:04,306 --> 00:09:07,170
>> こんにちは、この関数を取る、A
かかる無効機能

169
00:09:07,170 --> 00:09:09,212
int型、N、入力として。

170
00:09:09,212 --> 00:09:11,020
ベースケースは最初に来る。

171
00:09:11,020 --> 00:09:14,240
nは0、印刷​​未満である場合
「BYE」とリターン。

172
00:09:14,240 --> 00:09:15,490