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，即
採用單個字符串作為輸入，並

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
藉此功能，喜，一個void函數
接受一個int n作為輸入。

31
00:01:39,610 --> 00:01:41,260
基本情況是第一位的。

32
00:01:41,260 --> 00:01:46,220
如果n小於零，打印和再見
返回對於所有其他情況下，

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）將打印和喜
執行喜（2）執行喜（1）1

42
00:02:16,960 --> 00:02:20,560
它執行喜（0），其中所述
基本情況的條件得到滿足。

43
00:02:20,560 --> 00:02:24,100
因此喜（0）打印再見和回報。

44
00:02:24,100 --> 00:02:24,990
>> 確定。

45
00:02:24,990 --> 00:02:28,690
所以，現在我們了解的基本知識
遞歸函數，它們需要

46
00:02:28,690 --> 00:02:32,730
至少一種鹼的情況下，以及一個
遞歸調用，讓我們進入到一個

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倍，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的階乘
涉及乘以4×3×2×1

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，
寫一個函數sum

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
一個值，兩個節點的指針。

124
00:06:53,820 --> 00:06:57,270
通常，這是由表示
有一條線指向父節點

125
00:06:57,270 --> 00:07:01,870
給左子節點和一個
右邊的子節點。

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
>> 正如你所看到的，你不局限於
到只有一個遞歸調用。

150
00:08:15,390 --> 00:08:17,930
正如許多如將完成這項工作。

151
00:08:17,930 --> 00:08:21,200
如果你有一棵樹，每個
節點有三個孩子，

152
00:08:21,200 --> 00:08:23,100
左，中，右？

153
00:08:23,100 --> 00:08:24,886
你會如何編輯富？

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
嘗試在表達一種特定的情況下，
其他情況下，還是在子集。

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
>> 藉此功能，喜，一
空函數，它接受

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時，打印
“再見”和回報。

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