1
00:00:00,000 --> 00:00:05,860
>> [MUSIC CHƠI]

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Bạn có thể nghĩ rằng
mã chỉ được sử dụng để thực hiện một nhiệm vụ.

3
00:00:09,530 --> 00:00:10,450
Bạn viết nó ra.

4
00:00:10,450 --> 00:00:11,664
Nó làm điều gì đó.

5
00:00:11,664 --> 00:00:12,580
Đó là khá nhiều đó.

6
00:00:12,580 --> 00:00:13,160
>> Bạn biên dịch nó.

7
00:00:13,160 --> 00:00:13,993
Bạn chạy chương trình.

8
00:00:13,993 --> 00:00:15,370
Bạn tốt để đi.

9
00:00:15,370 --> 00:00:17,520
>> Nhưng tin hay không, nếu
bạn mã trong một thời gian dài,

10
00:00:17,520 --> 00:00:20,550
bạn thực sự có thể đến để xem
mã như một cái gì đó là đẹp.

11
00:00:20,550 --> 00:00:23,275
Nó giải quyết một vấn đề trong
một cách rất thú vị,

12
00:00:23,275 --> 00:00:26,510
hay đó chỉ là một cái gì đó thực sự
gọn về hình thức của nó.

13
00:00:26,510 --> 00:00:28,750
Bạn có thể cười
vào tôi, nhưng đó là sự thật.

14
00:00:28,750 --> 00:00:31,530
Và đệ quy là một trong những cách
để loại có được ý tưởng này

15
00:00:31,530 --> 00:00:34,090
xinh đẹp, thanh lịch, tìm kiếm mã.

16
00:00:34,090 --> 00:00:37,740
Nó giải quyết vấn đề theo cách mà
là thú vị, dễ dàng để hình dung,

17
00:00:37,740 --> 00:00:39,810
và đáng ngạc nhiên ngắn.

18
00:00:39,810 --> 00:00:43,190
>> Các tác phẩm theo cách đệ quy
là một hàm đệ quy

19
00:00:43,190 --> 00:00:49,291
được định nghĩa như là một chức năng mà các cuộc gọi
nó như một phần thực thi của nó.

20
00:00:49,291 --> 00:00:51,790
Điều đó có vẻ hơi lạ,
và chúng ta sẽ thấy một chút

21
00:00:51,790 --> 00:00:53,750
về cách làm việc này trong một thời điểm.

22
00:00:53,750 --> 00:00:55,560
Nhưng một lần nữa, các
thủ tục đệ quy là

23
00:00:55,560 --> 00:00:57,730
sẽ rất thanh lịch
bởi vì họ đang đi

24
00:00:57,730 --> 00:01:00,410
để giải quyết vấn đề này mà không có
có tất cả các chức năng khác

25
00:01:00,410 --> 00:01:02,710
hoặc những vòng dài.

26
00:01:02,710 --> 00:01:06,310
Bạn sẽ thấy rằng những đệ quy
thủ tục sẽ xem xét quá ngắn.

27
00:01:06,310 --> 00:01:10,610
Và họ thực sự sẽ làm cho
mã của bạn trông rất xinh đẹp hơn.

28
00:01:10,610 --> 00:01:12,560
>> Tôi sẽ cung cấp cho bạn một ví dụ
điều này để xem như thế nào

29
00:01:12,560 --> 00:01:14,880
một thủ tục đệ quy có thể được xác định.

30
00:01:14,880 --> 00:01:18,202
Vì vậy, nếu bạn đã quen thuộc với điều này
từ lớp toán nhiều năm trước đây,

31
00:01:18,202 --> 00:01:20,910
có của một cái gì đó gọi là
chức năng thừa, mà thường là

32
00:01:20,910 --> 00:01:25,340
ký hiệu là một dấu chấm than, mà
được xác định trên tất cả các số nguyên dương.

33
00:01:25,340 --> 00:01:28,850
Và cách mà n
thừa được tính

34
00:01:28,850 --> 00:01:31,050
là bạn nhân tất cả
các con số nhỏ hơn

35
00:01:31,050 --> 00:01:33,750
hoặc bằng n together--
tất cả các số nguyên ít hơn

36
00:01:33,750 --> 00:01:34,880
hoặc bằng n với nhau.

37
00:01:34,880 --> 00:01:39,850
>> Vì vậy, 5 giai thừa là 5 lần
4 lần 3 lần 2 lần 1.

38
00:01:39,850 --> 00:01:43,020
Và 4 giai thừa là 4 lần
3 lần 2 lần 1 và như vậy.

39
00:01:43,020 --> 00:01:44,800
Bạn nhận được các ý tưởng.

40
00:01:44,800 --> 00:01:47,060
>> Khi lập trình, chúng tôi không
sử dụng n, dấu chấm than.

41
00:01:47,060 --> 00:01:51,840
Vì vậy, chúng tôi sẽ xác định các nhân tố
chức năng là thực tế của n.

42
00:01:51,840 --> 00:01:56,897
Và chúng ta sẽ sử dụng để tạo ra giai thừa
một giải pháp đệ quy cho một vấn đề.

43
00:01:56,897 --> 00:01:59,230
Và tôi nghĩ rằng bạn có thể tìm thấy
rằng nó rất nhiều trực quan hơn

44
00:01:59,230 --> 00:02:02,380
hấp dẫn hơn so với lặp đi lặp lại
phiên bản này, mà

45
00:02:02,380 --> 00:02:05,010
chúng tôi cũng sẽ có một cái nhìn tại trong một thời điểm.

46
00:02:05,010 --> 00:02:08,310
>> Vì vậy, đây là một vài
pun facts-- intended--

47
00:02:08,310 --> 00:02:10,169
về các factorial--
chức năng thừa.

48
00:02:10,169 --> 00:02:13,090
Giai thừa của 1, như tôi đã nói, là 1.

49
00:02:13,090 --> 00:02:15,690
Giai thừa của 2 là 2 lần 1.

50
00:02:15,690 --> 00:02:18,470
Giai thừa của 3 là 3
lần 2 lần 1, và như vậy.

51
00:02:18,470 --> 00:02:20,810
Chúng tôi nói chuyện về 4 và 5 đã.

52
00:02:20,810 --> 00:02:23,940
>> Nhưng nhìn vào điều này, không phải là điều này có đúng?

53
00:02:23,940 --> 00:02:28,220
Không factorial của 2 chỉ
2 lần giai thừa của 1?

54
00:02:28,220 --> 00:02:31,130
Ý tôi là, giai thừa của 1 là 1.

55
00:02:31,130 --> 00:02:34,940
Vậy tại sao chúng ta không thể nói rằng,
kể từ khi thừa của 2 là 2 lần 1,

56
00:02:34,940 --> 00:02:38,520
nó thực sự chỉ là 2 lần
giai thừa của 1?

57
00:02:38,520 --> 00:02:40,900
>> Và sau đó mở rộng ý tưởng đó,
không phải là giai thừa của 3

58
00:02:40,900 --> 00:02:44,080
chỉ 3 lần giai thừa của 2?

59
00:02:44,080 --> 00:02:50,350
Và giai thừa của 4 là 4 lần
giai thừa của 3, và như vậy?

60
00:02:50,350 --> 00:02:52,530
Trong thực tế, giai thừa
của bất kỳ số có thể chỉ

61
00:02:52,530 --> 00:02:54,660
được thể hiện nếu chúng ta loại
của tiến hành việc này mãi mãi.

62
00:02:54,660 --> 00:02:56,870
Chúng ta có thể loại khái quát
vấn đề thừa

63
00:02:56,870 --> 00:02:59,910
vì nó là n lần
thừa của n trừ đi 1.

64
00:02:59,910 --> 00:03:04,840
Đó là n lần sản phẩm của
tất cả các con số nhỏ hơn tôi.

65
00:03:04,840 --> 00:03:08,890
>> Ý tưởng này, điều này
khái quát của vấn đề,

66
00:03:08,890 --> 00:03:13,410
cho phép chúng tôi để đệ quy
xác định các chức năng thừa.

67
00:03:13,410 --> 00:03:15,440
Khi bạn định nghĩa một hàm
đệ quy, có

68
00:03:15,440 --> 00:03:17,470
hai điều đó cần phải là một phần của nó.

69
00:03:17,470 --> 00:03:20,990
Bạn cần phải có một cái gì đó gọi là một
trường hợp cơ sở, trong đó, khi bạn kích hoạt nó,

70
00:03:20,990 --> 00:03:22,480
sẽ ngăn chặn quá trình đệ quy.

71
00:03:22,480 --> 00:03:25,300
>> Nếu không, một chức năng mà các cuộc gọi
itself-- như bạn có thể imagine--

72
00:03:25,300 --> 00:03:26,870
thể đi mãi mãi.

73
00:03:26,870 --> 00:03:29,047
Chức năng gọi hàm
kêu gọi các cuộc gọi chức năng

74
00:03:29,047 --> 00:03:30,380
chức năng cuộc gọi chức năng.

75
00:03:30,380 --> 00:03:32,380
Nếu bạn không có một cách
để ngăn chặn nó, chương trình của bạn

76
00:03:32,380 --> 00:03:34,760
sẽ bị mắc kẹt một cách hiệu quả
tại một vòng lặp vô hạn.

77
00:03:34,760 --> 00:03:37,176
Nó sẽ sụp đổ cuối cùng,
bởi vì nó sẽ chạy ra khỏi bộ nhớ.

78
00:03:37,176 --> 00:03:38,990
Nhưng đó là bên cạnh điểm.

79
00:03:38,990 --> 00:03:42,210
>> Chúng tôi cần phải có một số cách khác để ngăn chặn
thứ bên cạnh chương trình rơi của chúng tôi,

80
00:03:42,210 --> 00:03:46,010
vì một chương trình mà treo là
có lẽ không đẹp hoặc thanh lịch.

81
00:03:46,010 --> 00:03:47,690
Và vì vậy chúng tôi gọi đây là trường hợp cơ sở.

82
00:03:47,690 --> 00:03:50,610
Đây là một giải pháp đơn giản
cho một vấn đề mà dừng lại

83
00:03:50,610 --> 00:03:52,770
quá trình đệ quy từ xảy ra.

84
00:03:52,770 --> 00:03:55,220
Vì vậy, đó là một phần của
một hàm đệ quy.

85
00:03:55,220 --> 00:03:56,820
>> Phần thứ hai là trường hợp đệ quy.

86
00:03:56,820 --> 00:03:59,195
Và đây là nơi mà các đệ quy
sẽ thực sự diễn ra.

87
00:03:59,195 --> 00:04:02,200
Đây là nơi mà các
chức năng sẽ gọi chính nó.

88
00:04:02,200 --> 00:04:05,940
>> Nó sẽ không gọi chính nó trong một cách chính xác
giống như cách nó đã được gọi.

89
00:04:05,940 --> 00:04:08,880
Nó sẽ là một biến thể nhẹ
mà làm cho các vấn đề đó

90
00:04:08,880 --> 00:04:11,497
cố gắng để giải quyết một chút teeny nhỏ hơn.

91
00:04:11,497 --> 00:04:14,330
Nhưng nó thường đi buck
giải quyết phần lớn các giải pháp

92
00:04:14,330 --> 00:04:17,450
một cuộc gọi khác nhau xuống dòng.

93
00:04:17,450 --> 00:04:20,290
>> Mà của những vẻ
giống như trường hợp cơ sở ở đây?

94
00:04:20,290 --> 00:04:25,384
Mà một trong những vẻ như
Giải pháp đơn giản nhất để một vấn đề?

95
00:04:25,384 --> 00:04:27,550
Chúng tôi có một loạt các giai thừa,
và chúng tôi có thể tiếp tục

96
00:04:27,550 --> 00:04:30,470
đi on-- 6, 7, 8, 9, 10, và như vậy.

97
00:04:30,470 --> 00:04:34,130
>> Nhưng một trong những trông giống như một
trường hợp tốt để được các trường hợp cơ sở.

98
00:04:34,130 --> 00:04:35,310
Đó là một giải pháp rất đơn giản.

99
00:04:35,310 --> 00:04:37,810
Chúng tôi không cần phải làm bất cứ điều gì đặc biệt.

100
00:04:37,810 --> 00:04:40,560
>> Giai thừa của 1 chỉ 1 là.

101
00:04:40,560 --> 00:04:42,790
Chúng tôi không phải làm bất kỳ
nhân ở tất cả.

102
00:04:42,790 --> 00:04:45,248
Nó có vẻ như nếu chúng ta đang đi
để thử và giải quyết vấn đề này,

103
00:04:45,248 --> 00:04:47,600
và chúng ta cần phải ngăn chặn
đệ quy một nơi nào đó,

104
00:04:47,600 --> 00:04:50,610
có lẽ chúng ta muốn dừng lại
nó khi chúng tôi nhận được 1.

105
00:04:50,610 --> 00:04:54,580
Chúng tôi không muốn dừng lại trước đó.

106
00:04:54,580 --> 00:04:56,660
>> Vì vậy, nếu chúng ta đang xác định
chức năng thừa của chúng tôi,

107
00:04:56,660 --> 00:04:58,690
đây là một bộ xương cho
làm thế nào chúng ta có thể làm điều đó.

108
00:04:58,690 --> 00:05:03,110
Chúng tôi cần phải cắm vào hai things--
trường hợp cơ sở và các trường hợp đệ quy.

109
00:05:03,110 --> 00:05:04,990
Trường hợp cơ sở là gì?

110
00:05:04,990 --> 00:05:10,150
Nếu n là bằng 1, trở 1-- đó
một vấn đề thực sự đơn giản để giải quyết.

111
00:05:10,150 --> 00:05:11,890
>> Giai thừa của 1 là 1.

112
00:05:11,890 --> 00:05:13,860
Nó không phải 1 lần bất cứ điều gì.

113
00:05:13,860 --> 00:05:15,020
Nó chỉ là 1.

114
00:05:15,020 --> 00:05:17,170
Đó là một thực tế rất dễ dàng.

115
00:05:17,170 --> 00:05:19,620
Và đó có thể là trường hợp cơ sở của chúng tôi.

116
00:05:19,620 --> 00:05:24,730
Nếu chúng ta có được thông qua 1 thành này
chức năng, chúng tôi sẽ chỉ trả lại 1.

117
00:05:24,730 --> 00:05:27,320
>> Các đệ quy là gì
trường hợp có thể trông như thế nào?

118
00:05:27,320 --> 00:05:32,445
Đối với tất cả các số khác
bên cạnh 1, mô hình là những gì?

119
00:05:32,445 --> 00:05:35,780
Vâng, nếu chúng ta đang dùng
giai thừa của n,

120
00:05:35,780 --> 00:05:38,160
đó là lần n giai thừa của n trừ đi 1.

121
00:05:38,160 --> 00:05:42,130
>> Nếu chúng ta lấy thừa của 3,
đó là 3 lần giai thừa của 3 trừ đi 1,

122
00:05:42,130 --> 00:05:43,070
hoặc 2.

123
00:05:43,070 --> 00:05:47,330
Và do đó, nếu chúng ta không
nhìn vào 1, nếu không

124
00:05:47,330 --> 00:05:51,710
return n lần
thừa của n trừ đi 1.

125
00:05:51,710 --> 00:05:53,210
Nó khá dễ hiểu.

126
00:05:53,210 --> 00:05:57,360
>> Và vì lợi ích của việc có một chút
sạch và mã thanh lịch hơn,

127
00:05:57,360 --> 00:06:01,440
biết rằng nếu chúng ta có vòng single-line
hoặc đơn dòng nhánh có điều kiện,

128
00:06:01,440 --> 00:06:04,490
chúng ta có thể thoát khỏi tất cả các
dấu ngoặc nhọn xung quanh họ.

129
00:06:04,490 --> 00:06:06,850
Vì vậy, chúng ta có thể hợp nhất này để này.

130
00:06:06,850 --> 00:06:09,640
Điều này có chính xác như nhau
chức năng như thế này.

131
00:06:09,640 --> 00:06:13,850
>> Tôi chỉ lấy đi những xoăn
niềng răng, bởi vì chỉ có một dòng

132
00:06:13,850 --> 00:06:18,500
bên trong của những nhánh có điều kiện.

133
00:06:18,500 --> 00:06:21,160
Vì vậy, những cư xử hệt.

134
00:06:21,160 --> 00:06:23,800
Nếu n là bằng 1, trở về 1.

135
00:06:23,800 --> 00:06:28,351
Nếu không trả lại n lần
giai thừa của n trừ đi 1.

136
00:06:28,351 --> 00:06:29,850
Vì vậy, chúng tôi đang làm cho vấn đề nhỏ hơn.

137
00:06:29,850 --> 00:06:33,850
Nếu n bắt đầu ra như là 5, chúng ta sẽ
trả lại 5 lần thừa của 4.

138
00:06:33,850 --> 00:06:37,100
Và chúng ta sẽ thấy trong một phút khi chúng tôi nói chuyện
về stack-- cuộc gọi trong một video khác

139
00:06:37,100 --> 00:06:39,390
nơi chúng ta nói về
gọi stack-- chúng ta sẽ tìm hiểu

140
00:06:39,390 --> 00:06:41,630
về lý do tại sao chính xác quá trình này hoạt động.

141
00:06:41,630 --> 00:06:46,970
>> Nhưng trong khi thừa của 5 nói
trả lại 5 lần thừa của 4 và 4

142
00:06:46,970 --> 00:06:49,710
là sẽ nói, OK, tốt, trở lại
4 lần thừa của 3.

143
00:06:49,710 --> 00:06:51,737
Và như bạn thấy, chúng tôi
loại đến gần 1.

144
00:06:51,737 --> 00:06:53,820
Chúng tôi đang nhận được gần hơn và
gần với trường hợp cơ sở.

145
00:06:53,820 --> 00:06:58,180
>> Và một khi chúng ta nhấn hợp cơ sở,
tất cả các chức năng trước đó

146
00:06:58,180 --> 00:07:00,540
có câu trả lời mà họ đang tìm kiếm.

147
00:07:00,540 --> 00:07:03,900
Thừa của 2 đang nói trở lại
2 lần giai thừa của 1.

148
00:07:03,900 --> 00:07:06,760
Vâng, thừa của 1 trả về 1.

149
00:07:06,760 --> 00:07:10,090
Vì vậy, các cuộc gọi cho thừa
2 có thể trở lại 2 lần 1,

150
00:07:10,090 --> 00:07:13,980
và cho rằng trở lại thừa của
3, được chờ đợi kết quả đó.

151
00:07:13,980 --> 00:07:17,110
>> Và sau đó nó có thể tính toán
kết quả của nó, 3 lần 2 là 6,

152
00:07:17,110 --> 00:07:18,907
và đưa nó trở lại thừa của 4.

153
00:07:18,907 --> 00:07:20,740
Và một lần nữa, chúng ta có một
video trên các cuộc gọi stack

154
00:07:20,740 --> 00:07:23,810
nơi này được minh họa một chút
nhiều hơn những gì tôi đang nói ngay bây giờ.

155
00:07:23,810 --> 00:07:25,300
Nhưng điều này là nó.

156
00:07:25,300 --> 00:07:29,300
Chỉ riêng điều này là giải pháp cho
tính giai thừa của một số.

157
00:07:29,300 --> 00:07:31,527
>> Nó chỉ có bốn dòng mã.

158
00:07:31,527 --> 00:07:32,610
Đó là khá mát mẻ, phải không?

159
00:07:32,610 --> 00:07:35,480
Đó là loại sexy.

160
00:07:35,480 --> 00:07:38,580
>> Vì vậy, nói chung, nhưng không
luôn luôn, một hàm đệ quy

161
00:07:38,580 --> 00:07:41,190
có thể thay thế một vòng lặp trong một
hàm không đệ quy.

162
00:07:41,190 --> 00:07:46,100
Vì vậy, ở đây, bên cạnh, là lặp đi lặp lại
phiên bản của các chức năng thừa.

163
00:07:46,100 --> 00:07:49,650
Cả hai tính toán
chính xác những điều tương tự.

164
00:07:49,650 --> 00:07:52,170
>> Cả hai tính giai thừa của n.

165
00:07:52,170 --> 00:07:54,990
Các phiên bản bên trái
sử dụng đệ quy để làm điều đó.

166
00:07:54,990 --> 00:07:58,320
Các phiên bản bên phải
sử dụng lặp đi lặp lại để làm điều đó.

167
00:07:58,320 --> 00:08:02,050
>> Và thông báo, chúng ta phải khai báo
một biến một sản phẩm số nguyên.

168
00:08:02,050 --> 00:08:02,940
Và sau đó chúng ta lặp.

169
00:08:02,940 --> 00:08:06,790
Vì vậy, miễn là n là lớn hơn 0, chúng tôi
giữ nhân mà sản phẩm của n

170
00:08:06,790 --> 00:08:09,890
và giảm các n cho đến khi
chúng tôi tính toán sản phẩm.

171
00:08:09,890 --> 00:08:14,600
Vì vậy, hai chức năng này, một lần nữa,
làm chính xác những điều tương tự.

172
00:08:14,600 --> 00:08:19,980
Nhưng họ không làm điều đó trong
chính xác theo cùng một cách.

173
00:08:19,980 --> 00:08:22,430
>> Bây giờ, nó có thể
có nhiều hơn một cơ sở

174
00:08:22,430 --> 00:08:25,770
trường hợp hoặc nhiều hơn một
trường hợp đệ quy, tùy thuộc

175
00:08:25,770 --> 00:08:27,670
về những gì chức năng của bạn đang cố gắng để làm.

176
00:08:27,670 --> 00:08:31,650
Bạn không nhất thiết chỉ giới hạn
một trường hợp cơ sở duy nhất hoặc một đệ quy đơn

177
00:08:31,650 --> 00:08:32,370
trường hợp.

178
00:08:32,370 --> 00:08:35,320
Vì vậy, một ví dụ có
với nhiều trường hợp cơ sở

179
00:08:35,320 --> 00:08:37,830
có thể là các this--
Dãy số Fibonacci.

180
00:08:37,830 --> 00:08:41,549
>> Bạn có thể nhớ lại từ
còn học tiểu học

181
00:08:41,549 --> 00:08:45,740
rằng dãy Fibonacci được định nghĩa
như this-- phần tử đầu tiên là 0.

182
00:08:45,740 --> 00:08:46,890
Yếu tố thứ hai là 1.

183
00:08:46,890 --> 00:08:49,230
Cả hai của những người chỉ là theo định nghĩa.

184
00:08:49,230 --> 00:08:55,920
>> Sau đó mọi phần tử khác được định nghĩa
là tổng của n trừ đi 1 và n trừ đi 2.

185
00:08:55,920 --> 00:09:00,330
Vì vậy, yếu tố thứ ba
sẽ là 0 + 1 là 1.

186
00:09:00,330 --> 00:09:03,280
Và sau đó yếu tố thứ tư
sẽ là yếu tố thứ hai, 1,

187
00:09:03,280 --> 00:09:06,550
cộng với các yếu tố thứ ba, 1.

188
00:09:06,550 --> 00:09:08,507
Và đó sẽ là 2.

189
00:09:08,507 --> 00:09:09,340
Và như vậy và như vậy.

190
00:09:09,340 --> 00:09:11,680
>> Vì vậy, trong trường hợp này, chúng ta có hai trường hợp cơ sở.

191
00:09:11,680 --> 00:09:14,850
Nếu n là bằng 1, trở về 0.

192
00:09:14,850 --> 00:09:18,560
Nếu n là bằng 2, trở về 1.

193
00:09:18,560 --> 00:09:25,930
Nếu không, trở về Fibonacci của n
trừ 1 cộng với Fibonacci của n trừ đi 2.

194
00:09:25,930 --> 00:09:27,180
>> Vì vậy, đó là nhiều trường hợp cơ sở.

195
00:09:27,180 --> 00:09:29,271
Còn nhiều trường hợp đệ quy?

196
00:09:29,271 --> 00:09:31,520
Vâng, có điều gì đó
gọi là phỏng đoán Collatz.

197
00:09:31,520 --> 00:09:34,630
Tôi sẽ không nói,
bạn biết đó là gì,

198
00:09:34,630 --> 00:09:38,170
bởi vì nó thực sự thức của chúng tôi
vấn đề cho video đặc biệt này.

199
00:09:38,170 --> 00:09:43,220
Và đó là tập thể dục của chúng tôi
để làm việc trên cùng.

200
00:09:43,220 --> 00:09:46,760
>> Vì vậy, đây là những gì
Collatz phỏng đoán is--

201
00:09:46,760 --> 00:09:48,820
nó áp dụng cho tất cả các số nguyên dương.

202
00:09:48,820 --> 00:09:51,500
Và nó đoán rằng nó
luôn luôn có thể quay trở lại

203
00:09:51,500 --> 00:09:55,060
1 nếu bạn làm theo các bước sau.

204
00:09:55,060 --> 00:09:57,560
Nếu n là 1, dừng lại.

205
00:09:57,560 --> 00:10:00,070
Chúng tôi đã trở lại với 1 nếu n là 1.

206
00:10:00,070 --> 00:10:05,670
>> Nếu không, đi qua này
quá trình một lần nữa trên n chia cho 2.

207
00:10:05,670 --> 00:10:08,200
Và xem nếu bạn có thể lấy lại cho 1.

208
00:10:08,200 --> 00:10:13,260
Nếu không, nếu n là số lẻ, đi qua
quá trình này một lần nữa trên 3n cộng với 1,

209
00:10:13,260 --> 00:10:15,552
hoặc 3 lần n + 1.

210
00:10:15,552 --> 00:10:17,010
Vì vậy, ở đây chúng tôi có một trường hợp cơ sở duy nhất.

211
00:10:17,010 --> 00:10:18,430
Nếu n là bằng 1, dừng lại.

212
00:10:18,430 --> 00:10:20,230
Chúng tôi sẽ không làm bất cứ đệ quy nhiều hơn.

213
00:10:20,230 --> 00:10:23,730
>> Nhưng chúng ta có hai trường hợp đệ quy.

214
00:10:23,730 --> 00:10:28,750
Nếu n là chẵn, chúng tôi làm một đệ quy
trường hợp, gọi điện thoại n chia cho 2.

215
00:10:28,750 --> 00:10:33,950
Nếu n là số lẻ, chúng tôi làm một khác nhau
trường hợp đệ quy trên 3 lần n + 1.

216
00:10:33,950 --> 00:10:39,120
>> Và vì vậy mục tiêu cho video này
để mất một giây, tạm dừng các video,

217
00:10:39,120 --> 00:10:42,440
và thử viết này
hàm đệ quy Collatz

218
00:10:42,440 --> 00:10:47,640
nơi bạn vượt qua trong một giá trị n, và
nó tính toán có bao nhiêu bước nó

219
00:10:47,640 --> 00:10:52,430
cần để có được 1 nếu bạn bắt đầu từ n
và bạn làm theo những bước lên trên.

220
00:10:52,430 --> 00:10:56,660
Nếu n là 1, phải mất 0 bước.

221
00:10:56,660 --> 00:11:00,190
Nếu không, nó sẽ
một bước cộng tuy nhiên

222
00:11:00,190 --> 00:11:06,200
nhiều bước cần phải mất hai n
chia cho 2 nếu n là chẵn, hoặc 3n cộng 1

223
00:11:06,200 --> 00:11:08,100
nếu n là số lẻ.

224
00:11:08,100 --> 00:11:11,190
>> Bây giờ, tôi đã đặt lên trên màn hình ở đây
một vài điều thử nghiệm cho bạn,

225
00:11:11,190 --> 00:11:15,690
một vài thử nghiệm các trường hợp cho bạn, để xem
những gì các con số khác nhau là Collatz,

226
00:11:15,690 --> 00:11:17,440
và cũng là một minh họa
các bước mà

227
00:11:17,440 --> 00:11:20,390
cần phải được đi qua, do đó bạn có thể
loại nhìn thấy quá trình này trong hành động.

228
00:11:20,390 --> 00:11:24,222
Vì vậy, nếu n bằng
1, Collatz của n là 0.

229
00:11:24,222 --> 00:11:26,180
Bạn không cần phải làm
bất cứ điều gì để có được trở lại 1.

230
00:11:26,180 --> 00:11:27,600
Bạn đã có.

231
00:11:27,600 --> 00:11:30,550
>> Nếu n là 2, phải mất
một bước để có được 1.

232
00:11:30,550 --> 00:11:31,810
Bạn bắt đầu với 2.

233
00:11:31,810 --> 00:11:33,100
Vâng, 2 là không bằng 1.

234
00:11:33,100 --> 00:11:36,580
Vì vậy, nó sẽ là một bước
Tuy nhiên cộng với nhiều bước nó

235
00:11:36,580 --> 00:11:38,015
mất trên n chia cho 2.

236
00:11:38,015 --> 00:11:41,280

237
00:11:41,280 --> 00:11:42,910
>> 2 chia cho 2 là 1.

238
00:11:42,910 --> 00:11:47,200
Vì vậy, phải mất một bước cộng tuy nhiên
nhiều bước cần cho 1.

239
00:11:47,200 --> 00:11:49,720
1 mất zero bước.

240
00:11:49,720 --> 00:11:52,370
>> Đối với 3, bạn có thể thấy, có
khá một vài bước có liên quan.

241
00:11:52,370 --> 00:11:53,590
Bạn đi từ 3.

242
00:11:53,590 --> 00:11:56,710
Và sau đó bạn đi đến
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Phải mất bảy bước để có được trở lại 1.

244
00:11:58,804 --> 00:12:01,220
Và như bạn thấy, có một
vài trường hợp thử nghiệm khác ở đây

245
00:12:01,220 --> 00:12:02,470
để kiểm tra chương trình của bạn.

246
00:12:02,470 --> 00:12:03,970
Vì vậy, một lần nữa, tạm dừng video.

247
00:12:03,970 --> 00:12:09,210
Và tôi sẽ đi nhảy lại ngay bây giờ để
những gì quá trình thực tế là ở đây,

248
00:12:09,210 --> 00:12:11,390
những phỏng đoán này là.

249
00:12:11,390 --> 00:12:14,140
>> Xem nếu bạn có thể tìm ra
làm thế nào để xác định Collatz của n

250
00:12:14,140 --> 00:12:19,967
vì vậy mà nó tính toán có bao nhiêu
các bước cần thiết để có được 1.

251
00:12:19,967 --> 00:12:23,050
Vì vậy, hy vọng, bạn đã tạm dừng video
và bạn không phải chờ đợi tôi

252
00:12:23,050 --> 00:12:25,820
để cung cấp cho bạn câu trả lời ở đây.

253
00:12:25,820 --> 00:12:29,120
Nhưng nếu bạn đang có, cũng,
đây là câu trả lời nào.

254
00:12:29,120 --> 00:12:33,070
>> Vì vậy, đây là một định nghĩa có thể
của hàm Collatz.

255
00:12:33,070 --> 00:12:35,610
Cơ sở của chúng tôi case-- nếu n là
bằng 1, chúng tôi trở về 0.

256
00:12:35,610 --> 00:12:38,250
Nó không mất bất kỳ
bước để có được trở lại 1.

257
00:12:38,250 --> 00:12:42,710
>> Nếu không, chúng ta có hai cases-- đệ quy
một cho số chẵn và một cho lẻ.

258
00:12:42,710 --> 00:12:47,164
Cách tôi kiểm tra số chẵn
là để kiểm tra xem n mod 2 bằng 0.

259
00:12:47,164 --> 00:12:49,080
Điều này về cơ bản là, một lần nữa,
đặt câu hỏi,

260
00:12:49,080 --> 00:12:54,050
nếu bạn nhớ lại những gì mod is-- nếu tôi
chia n 2 là không có còn lại không?

261
00:12:54,050 --> 00:12:55,470
Đó sẽ là một số chẵn.

262
00:12:55,470 --> 00:13:01,370
>> Và vì vậy nếu n mod 2 bằng 0 là
thử nghiệm là đây là một số chẵn.

263
00:13:01,370 --> 00:13:04,250
Nếu vậy, tôi muốn trở về 1,
bởi vì điều này chắc chắn là

264
00:13:04,250 --> 00:13:09,270
thực hiện một bước cộng Collatz của
bất cứ số là một nửa của tôi.

265
00:13:09,270 --> 00:13:13,910
Nếu không, tôi muốn quay trở lại 1
cộng Collatz của 3 lần n + 1.

266
00:13:13,910 --> 00:13:16,060
Đó là khác
bước đệ quy mà chúng ta

267
00:13:16,060 --> 00:13:19,470
có thể áp dụng để tính toán
Collatz-- số bước

268
00:13:19,470 --> 00:13:22,610
nó cần để có được trở lại
đến 1 đưa ra một số.

269
00:13:22,610 --> 00:13:24,610
Vì vậy, hy vọng, ví dụ này
đã cho bạn một chút

270
00:13:24,610 --> 00:13:26,620
của một hương vị của thủ tục đệ quy.

271
00:13:26,620 --> 00:13:30,220
Hy vọng rằng, bạn nghĩ rằng mã là một
ít đẹp hơn nếu được thực hiện

272
00:13:30,220 --> 00:13:32,760
theo một cách đệ quy nhã.

273
00:13:32,760 --> 00:13:35,955
Nhưng thậm chí nếu không, đệ quy là một
công cụ thực sự mạnh mẽ không kém.

274
00:13:35,955 --> 00:13:38,330
Và do đó, nó chắc chắn là điều
để có được đầu của bạn xung quanh,

275
00:13:38,330 --> 00:13:41,360
bởi vì bạn sẽ có thể tạo ra
chương trình khá mát mẻ sử dụng đệ quy

276
00:13:41,360 --> 00:13:45,930
mà nếu không có thể là phức tạp để viết
nếu bạn đang sử dụng các vòng lặp và lặp đi lặp lại.

277
00:13:45,930 --> 00:13:46,980
Tôi Doug Lloyd.

278
00:13:46,980 --> 00:13:48,780
Đây là CS50.

279
00:13:48,780 --> 00:13:50,228