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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Để hiểu
đệ quy, bạn phải

3
00:00:10,190 --> 00:00:13,820
đầu tiên hiểu đệ quy.

4
00:00:13,820 --> 00:00:17,280
Có đệ quy trong chương trình thiết kế phương tiện
rằng bạn có tự tham chiếu

5
00:00:17,280 --> 00:00:18,570
định nghĩa.

6
00:00:18,570 --> 00:00:21,520
Cấu trúc dữ liệu đệ quy, ví dụ,
là những cấu trúc dữ liệu

7
00:00:21,520 --> 00:00:23,990
bao gồm bản thân trong
định nghĩa.

8
00:00:23,990 --> 00:00:27,160
Nhưng ngày hôm nay, chúng ta sẽ tập trung
về chức năng đệ quy.

9
00:00:27,160 --> 00:00:31,160
>> Nhớ lại rằng chức năng có đầu vào,
đối số, và trả về một giá trị như họ

10
00:00:31,160 --> 00:00:34,480
đầu ra đại diện
sơ đồ này ở đây.

11
00:00:34,480 --> 00:00:38,060
Chúng tôi sẽ nghĩ về hộp như cơ thể của
chức năng, có chứa các bộ

12
00:00:38,060 --> 00:00:42,340
hướng dẫn giải thích
đầu vào và cung cấp một đầu ra.

13
00:00:42,340 --> 00:00:45,660
Tham gia một cái nhìn gần hơn bên trong cơ thể của
chức năng có thể tiết lộ các cuộc gọi đến

14
00:00:45,660 --> 00:00:47,430
chức năng khác.

15
00:00:47,430 --> 00:00:51,300
Có chức năng này đơn giản, foo, mà
có một chuỗi duy nhất là đầu vào và

16
00:00:51,300 --> 00:00:54,630
in bao nhiêu chữ cái
chuỗi có.

17
00:00:54,630 --> 00:00:58,490
Chức năng strlen, cho chiều dài chuỗi,
được gọi là, có đầu ra là

18
00:00:58,490 --> 00:01:01,890
cần thiết cho các cuộc gọi đến printf.

19
00:01:01,890 --> 00:01:05,770
>> Bây giờ, những gì làm cho một hàm đệ quy
đặc biệt là nó gọi chính nó.

20
00:01:05,770 --> 00:01:09,610
Chúng ta có thể đại diện cho đệ quy
gọi với mũi tên màu cam này

21
00:01:09,610 --> 00:01:11,360
lặp lại cho chính nó.

22
00:01:11,360 --> 00:01:15,630
Nhưng thực hiện nó một lần nữa chỉ sẽ
thực hiện một cuộc gọi đệ quy, và

23
00:01:15,630 --> 00:01:17,150
khác và khác.

24
00:01:17,150 --> 00:01:19,100
Nhưng chức năng đệ quy
không thể là vô hạn.

25
00:01:19,100 --> 00:01:23,490
Họ phải kết thúc bằng cách nào đó, hoặc của bạn
chương trình sẽ chạy mãi mãi.

26
00:01:23,490 --> 00:01:27,680
>> Vì vậy chúng tôi cần phải tìm một cách để phá vỡ
ra khỏi các cuộc gọi đệ quy.

27
00:01:27,680 --> 00:01:29,900
Chúng tôi gọi đây là trường hợp cơ sở.

28
00:01:29,900 --> 00:01:33,570
Khi điều kiện trường hợp cơ sở được đáp ứng,
hàm trả về mà không làm

29
00:01:33,570 --> 00:01:34,950
một cuộc gọi đệ quy.

30
00:01:34,950 --> 00:01:39,610
Có chức năng này, hi, một hàm void
mà phải mất một int n như đầu vào.

31
00:01:39,610 --> 00:01:41,260
Trường hợp cơ sở đến trước.

32
00:01:41,260 --> 00:01:46,220
Nếu n là nhỏ hơn không, in tạm biệt và
trở lại Đối với tất cả các trường hợp khác, các

33
00:01:46,220 --> 00:01:49,400
chức năng sẽ in hi và thực hiện
cuộc gọi đệ quy.

34
00:01:49,400 --> 00:01:53,600
Một cuộc gọi đến các chức năng hi với
một giá trị đầu vào giảm đi.

35
00:01:53,600 --> 00:01:56,790
>> Bây giờ, mặc dù chúng tôi in hi, các
chức năng sẽ không chấm dứt cho đến khi chúng tôi

36
00:01:56,790 --> 00:02:00,370
trở lại kiểu trả về của nó,
trong trường hợp này có hiệu lực.

37
00:02:00,370 --> 00:02:04,830
Vì vậy, đối với mỗi n khác hơn so với trường hợp cơ sở,
chức năng này sẽ trở lại hi hi

38
00:02:04,830 --> 00:02:06,890
n trừ đi 1.

39
00:02:06,890 --> 00:02:10,050
Vì chức năng này không có hiệu lực, mặc dù chúng tôi
sẽ không đánh một cách rõ ràng trở lại đây.

40
00:02:10,050 --> 00:02:12,000
Chúng ta sẽ thực hiện các chức năng.

41
00:02:12,000 --> 00:02:16,960
Vì vậy, gọi hi (3) sẽ in và hi
thực hi (2) thực hiện các hi (1) một

42
00:02:16,960 --> 00:02:20,560
thực hiện các hi (0), nơi
điều kiện trường hợp cơ sở được đáp ứng.

43
00:02:20,560 --> 00:02:24,100
Vì vậy, hi (0) in tạm biệt và trả về.

44
00:02:24,100 --> 00:02:24,990
>> OK.

45
00:02:24,990 --> 00:02:28,690
Vì vậy, bây giờ chúng ta hiểu những điều cơ bản của
chức năng đệ quy, mà họ cần

46
00:02:28,690 --> 00:02:32,730
ít nhất một trường hợp cơ sở cũng như một
gọi đệ quy, chúng ta hãy chuyển sang một

47
00:02:32,730 --> 00:02:34,120
Ví dụ có ý nghĩa hơn.

48
00:02:34,120 --> 00:02:37,830
Một trong đó không chỉ trả lại
làm mất hiệu lực không có vấn đề gì.

49
00:02:37,830 --> 00:02:41,340
>> Chúng ta hãy nhìn vào các nhân tố
hoạt động sử dụng phổ biến nhất trong

50
00:02:41,340 --> 00:02:43,660
tính toán xác suất.

51
00:02:43,660 --> 00:02:48,120
Thừa của n là sản phẩm của mỗi
số nguyên dương nhỏ hơn

52
00:02:48,120 --> 00:02:49,400
và bằng n.

53
00:02:49,400 --> 00:02:56,731
Vì vậy, năm thừa là 5 lần 4 lần
3 lần 2 lần 1 để cung cấp cho 120.

54
00:02:56,731 --> 00:03:01,400
Bốn thừa là 4 lần 3 lần
2 lần 1 để cung cấp cho 24.

55
00:03:01,400 --> 00:03:04,910
Và cùng một quy tắc áp dụng
với bất kỳ số nguyên dương.

56
00:03:04,910 --> 00:03:08,670
>> Vậy làm thế nào chúng ta có thể viết đệ quy
chức năng cho phép tính giai thừa

57
00:03:08,670 --> 00:03:09,960
của một số?

58
00:03:09,960 --> 00:03:14,700
Vâng, chúng tôi sẽ cần phải xác định cả hai
trường hợp cơ sở và các cuộc gọi đệ quy.

59
00:03:14,700 --> 00:03:18,250
Cuộc gọi đệ quy sẽ giống nhau
cho tất cả các trường hợp ngoại trừ cho các cơ sở

60
00:03:18,250 --> 00:03:21,420
trường hợp, có nghĩa là chúng tôi sẽ phải
tìm thấy một mô hình mà sẽ cho chúng ta của chúng tôi

61
00:03:21,420 --> 00:03:23,350
kết quả mong muốn.

62
00:03:23,350 --> 00:03:30,270
>> Trong ví dụ này, xem như thế nào 5 thừa
liên quan đến nhân 4 3 2 1

63
00:03:30,270 --> 00:03:33,010
Và rất giống nhân
được tìm thấy ở đây,

64
00:03:33,010 --> 00:03:35,430
định nghĩa của 4 thừa.

65
00:03:35,430 --> 00:03:39,810
Vì vậy, chúng ta thấy rằng 5 là thừa
chỉ 5 lần 4 thừa.

66
00:03:39,810 --> 00:03:43,360
Bây giờ không áp dụng mô hình này
4 factorial không?

67
00:03:43,360 --> 00:03:44,280
Vâng.

68
00:03:44,280 --> 00:03:49,120
Chúng ta thấy rằng 4 nhân tố có chứa các
nhân 3 lần 2 lần 1,

69
00:03:49,120 --> 00:03:51,590
rất giống như định nghĩa 3 thừa.

70
00:03:51,590 --> 00:03:56,950
Vì vậy, 4 thừa bằng 4 lần 3
thừa, vv và vv của chúng tôi

71
00:03:56,950 --> 00:04:02,170
mô hình gậy cho đến khi 1 nhân tố, trong đó
theo định nghĩa là bằng 1.

72
00:04:02,170 --> 00:04:04,950
>> Không có tích cực khác
số nguyên trái.

73
00:04:04,950 --> 00:04:07,870
Vì vậy, chúng ta có mô hình cho
gọi đệ quy của chúng tôi.

74
00:04:07,870 --> 00:04:13,260
n thừa bằng n lần
giai thừa của n trừ đi 1.

75
00:04:13,260 --> 00:04:14,370
Và trường hợp cơ sở của chúng tôi?

76
00:04:14,370 --> 00:04:17,370
Điều đó sẽ chỉ được định nghĩa của chúng tôi
1 thừa.

77
00:04:17,370 --> 00:04:19,995
>> Vì vậy, bây giờ chúng tôi có thể chuyển sang viết
mã cho chức năng.

78
00:04:19,995 --> 00:04:24,110
Đối với trường hợp cơ sở, chúng tôi sẽ có
điều kiện n bằng bình đẳng 1, nơi

79
00:04:24,110 --> 00:04:25,780
chúng tôi sẽ trả lại 1.

80
00:04:25,780 --> 00:04:29,280
Sau đó chuyển sang cuộc gọi đệ quy,
chúng tôi sẽ trở lại n lần

81
00:04:29,280 --> 00:04:32,180
thừa của n trừ đi 1.

82
00:04:32,180 --> 00:04:33,590
>> Bây giờ hãy kiểm tra của chúng tôi này.

83
00:04:33,590 --> 00:04:35,900
Chúng ta hãy cố gắng thừa 4.

84
00:04:35,900 --> 00:04:39,420
Mỗi chức năng của chúng tôi nó bằng
đến 4 lần thừa (3).

85
00:04:39,420 --> 00:04:43,040
Thừa (3) bằng
3 lần thừa (2).

86
00:04:43,040 --> 00:04:48,700
Thừa (2) tương đương với 2 lần
thừa (1), trả về 1.

87
00:04:48,700 --> 00:04:52,490
Thừa (2) bây giờ trả về 2 lần 1, 2.

88
00:04:52,490 --> 00:04:55,960
Thừa (3) bây giờ có thể quay trở lại
3 lần 2, 6.

89
00:04:55,960 --> 00:05:02,490
Và cuối cùng, thừa (4)
trả 4 lần 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Nếu bạn đang gặp phải bất kỳ khó khăn
với các cuộc gọi đệ quy, giả vờ rằng

91
00:05:06,780 --> 00:05:09,660
chức năng công trình đã.

92
00:05:09,660 --> 00:05:13,450
Những gì tôi có ý nghĩa của việc này là bạn nên
tin tưởng các cuộc gọi đệ quy của bạn trở lại

93
00:05:13,450 --> 00:05:15,100
các giá trị đúng.

94
00:05:15,100 --> 00:05:18,960
Ví dụ, nếu tôi biết rằng
thừa (5) bằng 5 lần

95
00:05:18,960 --> 00:05:24,870
thừa (4), tôi sẽ tin tưởng rằng
thừa (4) sẽ cho tôi 24.

96
00:05:24,870 --> 00:05:28,510
Nghĩ về nó như là một biến, nếu bạn
sẽ, như thể bạn đã được xác định

97
00:05:28,510 --> 00:05:30,070
thừa (4).

98
00:05:30,070 --> 00:05:33,850
Vì vậy, đối với bất kỳ thừa (n), nó
sản phẩm của n và

99
00:05:33,850 --> 00:05:35,360
giai thừa trước đó.

100
00:05:35,360 --> 00:05:38,130
Và thừa trước đây
thu được bằng cách gọi

101
00:05:38,130 --> 00:05:41,330
thừa của n trừ đi 1.

102
00:05:41,330 --> 00:05:45,130
>> Bây giờ, xem bạn có thể thực hiện một
đệ quy hoạt động cho mình.

103
00:05:45,130 --> 00:05:50,490
Tải lên thiết bị đầu cuối của bạn, hoặc run.cs50.net,
và viết một số tiền chức năng

104
00:05:50,490 --> 00:05:54,770
mà phải mất một số nguyên n và trả về
tổng của tất cả liên tiếp tích cực

105
00:05:54,770 --> 00:05:57,490
số nguyên từ n đến 1.

106
00:05:57,490 --> 00:06:01,000
Tôi đã viết ra số tiền của một số
giá trị để giúp bạn của chúng tôi.

107
00:06:01,000 --> 00:06:04,030
Đầu tiên, tìm ra các
trường hợp cơ sở điều kiện.

108
00:06:04,030 --> 00:06:06,170
Sau đó, nhìn vào tổng hợp (5).

109
00:06:06,170 --> 00:06:09,270
Bạn có thể thể hiện nó trong điều kiện
của tổng khác?

110
00:06:09,270 --> 00:06:11,290
Bây giờ, những gì về tổng hợp (4)?

111
00:06:11,290 --> 00:06:15,630
Làm thế nào bạn có thể thể hiện tổng hợp (4)
về số tiền khác?

112
00:06:15,630 --> 00:06:19,655
>> Một khi bạn đã tổng hợp (5) và tổng hợp (4)
thể hiện trong điều khoản của các khoản tiền khác, xem

113
00:06:19,655 --> 00:06:22,970
nếu bạn có thể xác định một
mô hình để tổng hợp (n).

114
00:06:22,970 --> 00:06:26,190
Nếu không, hãy thử một vài số điện thoại khác
và thể hiện số tiền của họ trong

115
00:06:26,190 --> 00:06:28,410
về số lượng khác.

116
00:06:28,410 --> 00:06:31,930
Bằng cách xác định mô hình rời rạc
số, bạn cũng trên đường đến

117
00:06:31,930 --> 00:06:34,320
xác định mô hình cho bất kỳ n.

118
00:06:34,320 --> 00:06:38,040
>> Đệ quy là một công cụ thực sự mạnh mẽ,
nên dĩ nhiên nó không giới hạn

119
00:06:38,040 --> 00:06:39,820
chức năng toán học.

120
00:06:39,820 --> 00:06:44,040
Đệ quy có thể được sử dụng rất hiệu quả
khi giao dịch với cây chẳng hạn.

121
00:06:44,040 --> 00:06:47,210
Kiểm tra ngắn trên cây cho một
xem xét kỹ lưỡng hơn, nhưng bây giờ

122
00:06:47,210 --> 00:06:51,140
nhớ lại rằng cây tìm kiếm nhị phân, trong
Đặc biệt, được tạo thành từ các nút, mỗi

123
00:06:51,140 --> 00:06:53,820
với một giá trị và hai con trỏ nút.

124
00:06:53,820 --> 00:06:57,270
Thông thường, điều này được thể hiện bằng
nút cha có một dòng trỏ

125
00:06:57,270 --> 00:07:01,870
đến nút con trái và một
đến nút con phải.

126
00:07:01,870 --> 00:07:04,510
Cấu trúc của một tìm kiếm nhị phân
cây vay cũng chính nó

127
00:07:04,510 --> 00:07:05,940
để tìm kiếm đệ quy.

128
00:07:05,940 --> 00:07:09,730
Cuộc gọi đệ quy hoặc đi qua các
trái hoặc nút phải, nhưng hơn

129
00:07:09,730 --> 00:07:10,950
đó trong ngắn cây.

130
00:07:10,950 --> 00:07:15,690
>> Nói rằng bạn muốn thực hiện một thao tác trên
mỗi nút duy nhất trong một cây nhị phân.

131
00:07:15,690 --> 00:07:17,410
Làm thế nào bạn có thể đi về điều đó?

132
00:07:17,410 --> 00:07:20,600
Vâng, bạn có thể viết một đệ quy
chức năng thực hiện các hoạt động

133
00:07:20,600 --> 00:07:24,450
trên nút cha và làm cho một đệ quy
gọi để cùng chức năng,

134
00:07:24,450 --> 00:07:27,630
đi qua trong bên trái và
các nút con phải.

135
00:07:27,630 --> 00:07:31,650
Ví dụ, chức năng này, foo, mà
thay đổi giá trị của một nút cho trước và

136
00:07:31,650 --> 00:07:33,830
tất cả các con của nó là 1.

137
00:07:33,830 --> 00:07:37,400
Trường hợp cơ sở của một nguyên nhân nút vô giá trị
chức năng quay trở lại, cho thấy

138
00:07:37,400 --> 00:07:41,290
mà không có bất kỳ nút
còn lại trong đó cây con.

139
00:07:41,290 --> 00:07:42,620
>> Chúng ta hãy đi qua nó.

140
00:07:42,620 --> 00:07:44,340
Phụ huynh đầu tiên là 13.

141
00:07:44,340 --> 00:07:47,930
Chúng tôi thay đổi giá trị 1, và sau đó gọi
chức năng của chúng tôi bên trái cũng

142
00:07:47,930 --> 00:07:49,600
như bên phải.

143
00:07:49,600 --> 00:07:53,910
Chức năng, foo, được gọi là bên trái
cây con đầu tiên, do đó nút bên trái

144
00:07:53,910 --> 00:07:57,730
sẽ được bố trí 1 và foo sẽ
được gọi là con cái của nút đó,

145
00:07:57,730 --> 00:08:01,900
đầu tiên bên trái và sau đó bên phải,
vv và vv.

146
00:08:01,900 --> 00:08:05,630
Và nói với họ rằng các chi nhánh không có
trẻ em nữa vì vậy quá trình tương tự

147
00:08:05,630 --> 00:08:09,700
sẽ tiếp tục cho các em ngay
cho đến khi nút toàn bộ cây của là

148
00:08:09,700 --> 00:08:11,430
bố trí 1.

149
00:08:11,430 --> 00:08:15,390
>> Như bạn thấy, bạn không giới hạn
chỉ cần một cuộc gọi đệ quy.

150
00:08:15,390 --> 00:08:17,930
Cũng giống như nhiều như sẽ có được công việc thực hiện.

151
00:08:17,930 --> 00:08:21,200
Nếu bạn đã có một cây trong đó mỗi
nút có ba người con,

152
00:08:21,200 --> 00:08:23,100
Trái, giữa và phải không?

153
00:08:23,100 --> 00:08:24,886
Làm thế nào bạn sẽ chỉnh sửa foo?

154
00:08:24,886 --> 00:08:25,860
Vâng, đơn giản.

155
00:08:25,860 --> 00:08:30,250
Chỉ cần thêm một cuộc gọi đệ quy và
vượt qua trong con trỏ nút giữa.

156
00:08:30,250 --> 00:08:34,549
>> Đệ quy là rất mạnh mẽ và không để
đề cập đến thanh lịch, nhưng nó có thể là một

157
00:08:34,549 --> 00:08:38,010
khái niệm khó khăn lúc đầu, vì vậy hãy
bệnh nhân và mất thời gian của bạn.

158
00:08:38,010 --> 00:08:39,370
Bắt đầu với trường hợp cơ sở.

159
00:08:39,370 --> 00:08:42,650
Nó thường là đơn giản nhất để xác định,
và sau đó bạn có thể làm việc

160
00:08:42,650 --> 00:08:43,830
ngược từ đó.

161
00:08:43,830 --> 00:08:46,190
Bạn biết bạn cần phải đạt được của bạn
trường hợp cơ sở, vì vậy sức mạnh mà

162
00:08:46,190 --> 00:08:47,760
cung cấp cho bạn một vài gợi ý.

163
00:08:47,760 --> 00:08:53,120
Cố gắng thể hiện một trường hợp cụ thể trong
về các trường hợp khác, hoặc tại các bộ.

164
00:08:53,120 --> 00:08:54,700
>> Cảm ơn cho xem cái này ngắn.

165
00:08:54,700 --> 00:08:58,920
Ít nhất, bây giờ bạn có thể
hiểu câu nói đùa như thế này.

166
00:08:58,920 --> 00:09:01,250
Tên tôi là Zamyla, và đây là CS50.

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

168
00:09:04,306 --> 00:09:07,170
>> Có chức năng này, hi, một
khoảng trống chức năng mà mất

169
00:09:07,170 --> 00:09:09,212
một int, n, như đầu vào.

170
00:09:09,212 --> 00:09:11,020
Trường hợp cơ sở đến trước.

171
00:09:11,020 --> 00:09:14,240
Nếu n là nhỏ hơn 0, in
"Bye" và trở lại.

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