1
00:00:00,000 --> 00:00:05,860
>> [เล่นเพลง]

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: คุณอาจจะคิดว่า
รหัสถูกนำมาใช้เพียงเพื่อให้งานสำเร็จ

3
00:00:09,530 --> 00:00:10,450
คุณเขียนมันออกมา

4
00:00:10,450 --> 00:00:11,664
มันจะมีอะไรบางอย่าง

5
00:00:11,664 --> 00:00:12,580
นั่นคือมันสวยมาก

6
00:00:12,580 --> 00:00:13,160
>> คุณรวบรวมไว้

7
00:00:13,160 --> 00:00:13,993
คุณเรียกใช้โปรแกรม

8
00:00:13,993 --> 00:00:15,370
คุณจะดีไป

9
00:00:15,370 --> 00:00:17,520
>> แต่เชื่อหรือไม่ถ้า
รหัสที่คุณมาเป็นเวลานาน

10
00:00:17,520 --> 00:00:20,550
คุณจริงอาจจะมาดู
รหัสเป็นสิ่งที่สวยงาม

11
00:00:20,550 --> 00:00:23,275
มันแก้ปัญหาที่เกิดขึ้นใน
เป็นวิธีที่น่าสนใจมาก

12
00:00:23,275 --> 00:00:26,510
หรือมีอะไรบางอย่างเพียงจริงๆ
ระเบียบเกี่ยวกับวิธีที่มันมีลักษณะ

13
00:00:26,510 --> 00:00:28,750
คุณอาจจะหัวเราะ
ที่ฉัน แต่มันเป็นความจริง

14
00:00:28,750 --> 00:00:31,530
และการเรียกซ้ำเป็นวิธีหนึ่ง
ที่จะได้รับการจัดเรียงของความคิดนี้

15
00:00:31,530 --> 00:00:34,090
ที่สวยงามของรหัสที่สง่างามที่มองหา

16
00:00:34,090 --> 00:00:37,740
จะแก้ปัญหาด้วยวิธีการที่
เป็นที่น่าสนใจและง่ายต่อการเห็นภาพ

17
00:00:37,740 --> 00:00:39,810
และระยะสั้นที่น่าแปลกใจ

18
00:00:39,810 --> 00:00:43,190
>> ผลงานวิธีการเรียกซ้ำ
คือฟังก์ชั่นแบบทั่วถึง

19
00:00:43,190 --> 00:00:49,291
ถูกกำหนดให้เป็นฟังก์ชั่นที่เรียก
ตัวเองเป็นส่วนหนึ่งของการดำเนินการ

20
00:00:49,291 --> 00:00:51,790
ที่อาจดูเหมือนเล็กน้อยแปลก
และเราจะเห็นนิด ๆ หน่อย ๆ

21
00:00:51,790 --> 00:00:53,750
เกี่ยวกับวิธีการทำงานในช่วงเวลาที่

22
00:00:53,750 --> 00:00:55,560
แต่อีกครั้งเหล่านี้
ขั้นตอนการเรียกซ้ำเป็น

23
00:00:55,560 --> 00:00:57,730
จะเป็นเพื่อให้สง่างาม
เพราะพวกเขากำลังจะ

24
00:00:57,730 --> 00:01:00,410
เพื่อแก้ปัญหานี้ได้โดยไม่ต้อง
ทั้งหมดเหล่านี้มีฟังก์ชั่นอื่น ๆ

25
00:01:00,410 --> 00:01:02,710
หรือเหล่านี้ลูปยาว

26
00:01:02,710 --> 00:01:06,310
คุณจะเห็นว่า recursive เหล่านี้
ขั้นตอนจะไปดูสั้น

27
00:01:06,310 --> 00:01:10,610
และพวกเขาจริงๆจะทำ
รหัสของคุณดูเป็นจำนวนมากที่สวยงามมากขึ้น

28
00:01:10,610 --> 00:01:12,560
>> ฉันจะให้คุณตัวอย่างเช่น
นี้เพื่อดูว่า

29
00:01:12,560 --> 00:01:14,880
ขั้นตอนการเรียกซ้ำอาจจะมีการกำหนดไว้

30
00:01:14,880 --> 00:01:18,202
ดังนั้นถ้าคุณคุ้นเคยกับเรื่องนี้
จากชั้นเรียนคณิตศาสตร์หลายปีที่ผ่านมา

31
00:01:18,202 --> 00:01:20,910
บางสิ่งบางอย่างที่นั่นเรียกว่า
ฟังก์ชั่นปัจจัยซึ่งมักจะ

32
00:01:20,910 --> 00:01:25,340
แสดงเป็นเครื่องหมายอัศเจรีย์ซึ่ง
ที่กำหนดไว้ในช่วงจำนวนเต็มบวกทั้งหมด

33
00:01:25,340 --> 00:01:28,850
และวิธีการที่เอ็น
ปัจจัยที่มีการคำนวณ

34
00:01:28,850 --> 00:01:31,050
คือคุณคูณทั้งหมดของ
ตัวเลขที่น้อยกว่า

35
00:01:31,050 --> 00:01:33,750
หรือเท่ากับ n together--
จำนวนเต็มทั้งหมดที่น้อยกว่า

36
00:01:33,750 --> 00:01:34,880
หรือเท่ากับ n ร่วมกัน

37
00:01:34,880 --> 00:01:39,850
>> ดังนั้นปัจจัยที่ 5 คือ 5 ครั้ง
4 ครั้งครั้งที่ 3 ครั้งที่ 2 1

38
00:01:39,850 --> 00:01:43,020
และ 4 ปัจจัยคือ 4 ครั้ง
3 ครั้ง 2 ครั้งที่ 1 และอื่น ๆ

39
00:01:43,020 --> 00:01:44,800
คุณจะได้รับความคิด

40
00:01:44,800 --> 00:01:47,060
>> ในฐานะที่เป็นโปรแกรมเมอร์ที่เราทำไม่ได้
ใช้ n, เครื่องหมายอัศเจรีย์

41
00:01:47,060 --> 00:01:51,840
ดังนั้นเราจะกำหนดแฟกทอ
ฟังก์ชั่นความเป็นจริงของ n

42
00:01:51,840 --> 00:01:56,897
และเราจะใช้ปัจจัยในการสร้าง
วิธีการแก้ปัญหาที่จะเวียนเกิดปัญหา

43
00:01:56,897 --> 00:01:59,230
และฉันคิดว่าคุณอาจพบว่า
ว่ามันเป็นมากขึ้นสายตา

44
00:01:59,230 --> 00:02:02,380
ที่น่าสนใจกว่าซ้ำ
รุ่นนี้ซึ่ง

45
00:02:02,380 --> 00:02:05,010
เราจะดูที่ในช่วงเวลาที่

46
00:02:05,010 --> 00:02:08,310
>> ดังนั้นนี่คือคู่ของ
ปุน facts-- intended--

47
00:02:08,310 --> 00:02:10,169
เกี่ยวกับ factorial--
ฟังก์ชั่นปัจจัย

48
00:02:10,169 --> 00:02:13,090
ปัจจัย 1 ที่ผมกล่าวว่าเป็น 1

49
00:02:13,090 --> 00:02:15,690
ปัจจัยของ 2 เป็นครั้งที่ 2 1

50
00:02:15,690 --> 00:02:18,470
ปัจจัย 3 คือ 3
ครั้งที่ 2 ครั้งที่ 1, และอื่น ๆ

51
00:02:18,470 --> 00:02:20,810
เราได้พูดคุยเกี่ยวกับ 4 และ 5 แล้ว

52
00:02:20,810 --> 00:02:23,940
>> แต่กำลังมองหาที่นี้ไม่ได้เป็นนี้จริงหรือไม่?

53
00:02:23,940 --> 00:02:28,220
ไม่ได้เป็นปัจจัย 2 เพียง
ปัจจัย 2 ครั้งที่ 1?

54
00:02:28,220 --> 00:02:31,130
ผมหมายถึงปัจจัยที่ 1 คือ 1

55
00:02:31,130 --> 00:02:34,940
ดังนั้นทำไมเราไม่สามารถเพียงแค่บอกว่า
เนื่องจากปัจจัย 2 เป็น 2 ครั้งที่ 1

56
00:02:34,940 --> 00:02:38,520
มันจริงๆเพียงแค่ 2 ครั้ง
ปัจจัยที่ 1?

57
00:02:38,520 --> 00:02:40,900
>> และจากนั้นก็ขยายความคิดที่ว่า
ไม่ได้เป็นปัจจัยของ 3

58
00:02:40,900 --> 00:02:44,080
เพียงแค่ 3 ครั้งปัจจัยของ 2?

59
00:02:44,080 --> 00:02:50,350
และปัจจัย 4 คือ 4 ครั้ง
ปัจจัย 3 และอื่น ๆ หรือไม่

60
00:02:50,350 --> 00:02:52,530
ในความเป็นจริงแฟกทอ
จำนวนใด ๆ ก็สามารถ

61
00:02:52,530 --> 00:02:54,660
จะแสดงถ้าเราชนิด
การดำเนินการนี​​้ตลอดไป

62
00:02:54,660 --> 00:02:56,870
เราสามารถพูดคุยชนิดของ
ปัญหาปัจจัย

63
00:02:56,870 --> 00:02:59,910
ในขณะที่มันเป็นครั้งที่ n
ปัจจัยของ n ลบ 1

64
00:02:59,910 --> 00:03:04,840
มันเป็นช่วงเวลาที่สินค้าของ n
ตัวเลขทั้งหมดน้อยกว่าผม

65
00:03:04,840 --> 00:03:08,890
>> ความคิดนี้นี้
ลักษณะทั่วไปของปัญหา

66
00:03:08,890 --> 00:03:13,410
ช่วยให้เราสามารถซ้ำ
กำหนดฟังก์ชั่นปัจจัย

67
00:03:13,410 --> 00:03:15,440
เมื่อคุณกำหนดฟังก์ชั่น
ซ้ำมี

68
00:03:15,440 --> 00:03:17,470
สองสิ่งที่ต้องเป็นส่วนหนึ่งของมัน

69
00:03:17,470 --> 00:03:20,990
คุณจำเป็นต้องมีสิ่งที่เรียกว่า
กรณีฐานซึ่งเมื่อคุณเรียกมัน

70
00:03:20,990 --> 00:03:22,480
จะหยุดกระบวนการ recursive

71
00:03:22,480 --> 00:03:25,300
>> มิฉะนั้นฟังก์ชั่นที่เรียกร้อง
itself-- ที่คุณอาจ imagine--

72
00:03:25,300 --> 00:03:26,870
ได้ตลอดไป

73
00:03:26,870 --> 00:03:29,047
ฟังก์ชั่นการเรียกฟังก์ชั่น
เรียกฟังก์ชั่นการโทร

74
00:03:29,047 --> 00:03:30,380
ฟังก์ชั่นเรียกฟังก์ชั่น

75
00:03:30,380 --> 00:03:32,380
หากคุณไม่ได้มีวิธีการที่
ที่จะหยุดมันโปรแกรมของคุณ

76
00:03:32,380 --> 00:03:34,760
จะติดได้อย่างมีประสิทธิภาพ
ในวง จำกัด

77
00:03:34,760 --> 00:03:37,176
มันจะผิดพลาดที่สุด
เพราะมันจะวิ่งออกจากหน่วยความจำ

78
00:03:37,176 --> 00:03:38,990
แต่ที่ข้างจุด

79
00:03:38,990 --> 00:03:42,210
>> เราจำเป็นต้องมีวิธีการอื่น ๆ ที่จะหยุด
สิ่งที่นอกเหนือจากสุดยอดโปรแกรมของเรา

80
00:03:42,210 --> 00:03:46,010
เนื่องจากโปรแกรมที่เกิดปัญหาคือ
อาจจะไม่สวยงามหรือหรูหรา

81
00:03:46,010 --> 00:03:47,690
และเพื่อให้เราเรียกสิ่งนี้ว่ากรณีฐาน

82
00:03:47,690 --> 00:03:50,610
นี้เป็นวิธีที่ง่าย
ในการแก้ไขปัญหาที่หยุด

83
00:03:50,610 --> 00:03:52,770
กระบวนการ recursive เกิดขึ้น

84
00:03:52,770 --> 00:03:55,220
เพื่อให้เป็นส่วนหนึ่งของ
ฟังก์ชั่นแบบทั่วถึง

85
00:03:55,220 --> 00:03:56,820
>> ส่วนที่สองเป็นกรณี recursive

86
00:03:56,820 --> 00:03:59,195
และนี่คือที่เรียกซ้ำตัวเอง
จริงที่จะเกิดขึ้น

87
00:03:59,195 --> 00:04:02,200
นี่คือที่
ฟังก์ชั่นจะเรียกตัวเอง

88
00:04:02,200 --> 00:04:05,940
>> มันจะไม่เรียกตัวเองในตรง
แบบเดียวกับที่มันถูกเรียกว่า

89
00:04:05,940 --> 00:04:08,880
มันจะเปลี่ยนแปลงเล็กน้อย
ที่ทำให้ปัญหามัน

90
00:04:08,880 --> 00:04:11,497
พยายามที่จะแก้นิดเล็กที่มีขนาดเล็ก

91
00:04:11,497 --> 00:04:14,330
แต่โดยทั่วไปผ่านเจ้าชู้
ของการแก้จำนวนมากของการแก้ปัญหา

92
00:04:14,330 --> 00:04:17,450
ที่จะมีการเรียกที่แตกต่างกันลงเส้น

93
00:04:17,450 --> 00:04:20,290
>> ซึ่งเหล่านี้ของรูปลักษณ์
เช่นเดียวกับกรณีฐานที่นี่?

94
00:04:20,290 --> 00:04:25,384
ซึ่งหนึ่งในลักษณะเช่นเหล่านี้
ทางออกที่ง่ายที่สุดในการแก้ไขปัญหาหรือไม่?

95
00:04:25,384 --> 00:04:27,550
เรามีพวงของ factorials ที่
และเราสามารถดำเนินการต่อ

96
00:04:27,550 --> 00:04:30,470
จะ on-- 6, 7, 8, 9, 10, และอื่น ๆ

97
00:04:30,470 --> 00:04:34,130
>> แต่หนึ่งในลักษณะเช่นเหล่านี้
กรณีที่ดีจะเป็นกรณีฐาน

98
00:04:34,130 --> 00:04:35,310
จะเป็นทางออกที่ง่ายมาก

99
00:04:35,310 --> 00:04:37,810
เราไม่ต้องทำอะไรเป็นพิเศษ

100
00:04:37,810 --> 00:04:40,560
>> ปัจจัยที่ 1 เพียง 1

101
00:04:40,560 --> 00:04:42,790
เราไม่ได้มีการดำเนินการใด ๆ
คูณเลย

102
00:04:42,790 --> 00:04:45,248
ดูเหมือนว่าถ้าเรากำลังจะ
และพยายามแก้ปัญหานี้

103
00:04:45,248 --> 00:04:47,600
และเราจำเป็นต้องหยุด
recursion ที่ไหนสักแห่ง

104
00:04:47,600 --> 00:04:50,610
เราอาจต้องการที่จะหยุด
เมื่อเราได้รับ 1

105
00:04:50,610 --> 00:04:54,580
เราไม่ต้องการที่จะหยุดก่อนหน้านั้น

106
00:04:54,580 --> 00:04:56,660
>> ดังนั้นถ้าเรากำหนด
ฟังก์ชั่นปัจจัยของเรา

107
00:04:56,660 --> 00:04:58,690
นี่เป็นโครงกระดูกสำหรับ
วิธีการที่เราจะทำอย่างนั้น

108
00:04:58,690 --> 00:05:03,110
เราจำเป็นต้องเสียบทั้งสอง things--
กรณีฐานและกรณี recursive

109
00:05:03,110 --> 00:05:04,990
กรณีฐานคืออะไร?

110
00:05:04,990 --> 00:05:10,150
ถ้า n มีค่าเท่ากับ 1 กลับ 1- ที่
ปัญหาที่ง่ายมากที่จะแก้ปัญหา

111
00:05:10,150 --> 00:05:11,890
>> ปัจจัยที่ 1 คือ 1

112
00:05:11,890 --> 00:05:13,860
มันไม่ได้ 1 ครั้งอะไร

113
00:05:13,860 --> 00:05:15,020
มันเป็นเพียง 1

114
00:05:15,020 --> 00:05:17,170
มันเป็นความจริงที่ง่ายมาก

115
00:05:17,170 --> 00:05:19,620
และอื่น ๆ ที่สามารถเป็นกรณีฐานของเรา

116
00:05:19,620 --> 00:05:24,730
ถ้าเราได้รับผ่าน 1 ในนี้
ฟังก์ชั่นเราก็จะกลับมา 1

117
00:05:24,730 --> 00:05:27,320
>> อะไรแบบทั่วถึง
กรณีที่อาจจะมีลักษณะอย่างไร

118
00:05:27,320 --> 00:05:32,445
ทุกหมายเลขอื่น
นอกเหนือจาก 1 สิ่งที่รูปแบบหรือไม่

119
00:05:32,445 --> 00:05:35,780
ดีถ้าเรากำลังการ
ปัจจัยของ n,

120
00:05:35,780 --> 00:05:38,160
มันเป็นครั้งที่ n ของปัจจัยลบ 1 n

121
00:05:38,160 --> 00:05:42,130
>> ถ้าเราจะเอาปัจจัยของ 3
มันเป็นครั้งที่ 3 ปัจจัยของ 3 ลบ 1,

122
00:05:42,130 --> 00:05:43,070
หรือ 2

123
00:05:43,070 --> 00:05:47,330
ดังนั้นถ้าเราไม่
กำลังมองหาที่ 1 มิฉะนั้น

124
00:05:47,330 --> 00:05:51,710
การกลับมาครั้งที่ n
ปัจจัยของ n ลบ 1

125
00:05:51,710 --> 00:05:53,210
มันตรงไปตรงสวย

126
00:05:53,210 --> 00:05:57,360
>> และเพื่อประโยชน์ของการมีเล็กน้อย
ทำความสะอาดและรหัสหรูหรามากขึ้น

127
00:05:57,360 --> 00:06:01,440
รู้ว่าถ้าเรามีลูปบรรทัดเดียว
หรือสายเดี่ยวสาขาเงื่อนไข

128
00:06:01,440 --> 00:06:04,490
เราสามารถกำจัดทั้งหมดของ
วงเล็บปีกการอบตัวพวกเขา

129
00:06:04,490 --> 00:06:06,850
ดังนั้นเราจึงสามารถรวมนี้นี้

130
00:06:06,850 --> 00:06:09,640
นี้มีเหมือนกัน
การทำงานเช่นนี้

131
00:06:09,640 --> 00:06:13,850
>> ฉันแค่การออกไปหยิก
วงเล็บเพราะมีเพียงหนึ่งบรรทัด

132
00:06:13,850 --> 00:06:18,500
ภายในของสาขาเงื่อนไขเหล่านั้น

133
00:06:18,500 --> 00:06:21,160
ดังนั้นมีพฤติกรรมเหล่านี้เหมือนกัน

134
00:06:21,160 --> 00:06:23,800
ถ้า n มีค่าเท่ากับ 1 กลับ 1

135
00:06:23,800 --> 00:06:28,351
มิฉะนั้นกลับมาครั้ง n
ปัจจัยของ n ลบ 1

136
00:06:28,351 --> 00:06:29,850
ดังนั้นเราจึงกำลังทำให้ปัญหาที่มีขนาดเล็ก

137
00:06:29,850 --> 00:06:33,850
ถ้า n เริ่มออกเป็น 5 เรากำลังจะไป
กลับ 5 ครั้งปัจจัย 4

138
00:06:33,850 --> 00:06:37,100
และเราจะเห็นในนาทีเมื่อเราพูด
เกี่ยวกับการโทรใน stack-- วิดีโออื่น

139
00:06:37,100 --> 00:06:39,390
ที่เราพูดคุยเกี่ยวกับ
เรียก stack-- เราจะได้เรียนรู้

140
00:06:39,390 --> 00:06:41,630
เกี่ยวกับเหตุผลที่ว่ากระบวนการทำงานนี้

141
00:06:41,630 --> 00:06:46,970
>> แต่ในขณะที่ปัจจัย 5 กล่าวว่า
กลับ 5 ครั้งปัจจัย 4 และ 4

142
00:06:46,970 --> 00:06:49,710
จะไปพูดตกลงกันกลับ
ปัจจัย 4 ครั้งของ 3

143
00:06:49,710 --> 00:06:51,737
และในขณะที่คุณสามารถดูเรา
การเรียงลำดับของการแสวงหา 1

144
00:06:51,737 --> 00:06:53,820
เราได้รับใกล้ชิดและ
ใกล้ชิดกับกรณีฐานที่

145
00:06:53,820 --> 00:06:58,180
>> และเมื่อเราตีกรณีฐาน
ทุกฟังก์ชั่ก่อนหน้านี้

146
00:06:58,180 --> 00:07:00,540
มีคำตอบที่พวกเขากำลังมองหา

147
00:07:00,540 --> 00:07:03,900
ปัจจัยของ 2 กลับมาบอกว่า
2 ครั้งปัจจัย 1

148
00:07:03,900 --> 00:07:06,760
ดีปัจจัย 1 ผลตอบแทนที่ 1

149
00:07:06,760 --> 00:07:10,090
ดังนั้นการเรียกร้องให้ปัจจัย
2 สามารถกลับ 2 ครั้งที่ 1

150
00:07:10,090 --> 00:07:13,980
และให้กลับไปปัจจัยที่
3 ซึ่งกำลังรอผลว่า

151
00:07:13,980 --> 00:07:17,110
>> และจากนั้นก็สามารถคำนวณ
ผลที่ 3 ครั้งที่ 2 เป็น 6

152
00:07:17,110 --> 00:07:18,907
และให้มันกลับไปที่ปัจจัย 4

153
00:07:18,907 --> 00:07:20,740
และอีกครั้งที่เรามี
วิดีโอบนสแต็คโทร

154
00:07:20,740 --> 00:07:23,810
ที่นี้คือตัวอย่างเล็ก ๆ น้อย ๆ
มากกว่าสิ่งที่ฉันพูดในขณะนี้

155
00:07:23,810 --> 00:07:25,300
แต่ตอนนี้มันเป็น

156
00:07:25,300 --> 00:07:29,300
นี้เพียงอย่างเดียวเป็นวิธีการแก้
คำนวณปัจจัยของตัวเลข

157
00:07:29,300 --> 00:07:31,527
>> มันเป็นเพียงสี่บรรทัดของรหัส

158
00:07:31,527 --> 00:07:32,610
นั่นเป็นเย็นสวยใช่มั้ย?

159
00:07:32,610 --> 00:07:35,480
เป็นชนิดของเซ็กซี่

160
00:07:35,480 --> 00:07:38,580
>> ดังนั้นโดยทั่วไป แต่ไม่ได้
เคยฟังก์ชั่นแบบทั่วถึง

161
00:07:38,580 --> 00:07:41,190
สามารถเปลี่ยนวงในได้
ฟังก์ชั่นที่ไม่ recursive

162
00:07:41,190 --> 00:07:46,100
ดังนั้นที่นี่เคียงข้างเป็นซ้ำ
รุ่นของฟังก์ชั่นปัจจัย

163
00:07:46,100 --> 00:07:49,650
ทั้งสองคำนวณเหล่านี้
สิ่งเดียวกัน

164
00:07:49,650 --> 00:07:52,170
>> พวกเขาทั้งสองปัจจัยการคำนวณของ n

165
00:07:52,170 --> 00:07:54,990
รุ่นด้านซ้าย
ใช้เรียกซ้ำที่จะทำมัน

166
00:07:54,990 --> 00:07:58,320
รุ่นทางด้านขวา
ใช้ซ้ำที่จะทำมัน

167
00:07:58,320 --> 00:08:02,050
>> และแจ้งให้ทราบว่าเราจะต้องประกาศ
ตัวแปรผลิตภัณฑ์จำนวนเต็ม

168
00:08:02,050 --> 00:08:02,940
และจากนั้นเราห่วง

169
00:08:02,940 --> 00:08:06,790
ตราบเท่าที่ n มากกว่า 0 เรา
ให้คูณโดยผลิตภัณฑ์ที่ n

170
00:08:06,790 --> 00:08:09,890
และ decrementing n จนกว่า
เราคำนวณผลิตภัณฑ์

171
00:08:09,890 --> 00:08:14,600
ดังนั้นทั้งสองฟังก์ชั่นอีกครั้ง
ทำสิ่งเดียวกัน

172
00:08:14,600 --> 00:08:19,980
แต่พวกเขาไม่ได้ทำมันใน
ตรงทางเดียวกัน

173
00:08:19,980 --> 00:08:22,430
>> ตอนนี้ก็เป็นไปได้ที่จะ
มีมากกว่าหนึ่งฐาน

174
00:08:22,430 --> 00:08:25,770
กรณีหรือมากกว่าหนึ่ง
กรณีเวียนเกิดขึ้นอยู่

175
00:08:25,770 --> 00:08:27,670
ในสิ่งที่ฟังก์ชั่นของคุณพยายามที่จะทำ

176
00:08:27,670 --> 00:08:31,650
คุณไม่จำเป็นต้อง จำกัด เพียงการ
กรณีฐานเดียวหรือ recursive เดียว

177
00:08:31,650 --> 00:08:32,370
กรณี

178
00:08:32,370 --> 00:08:35,320
ดังนั้นตัวอย่างของบางสิ่งบางอย่าง
กับกรณีฐานหลาย

179
00:08:35,320 --> 00:08:37,830
อาจจะ this--
ลำดับฟีโบนักชีจำนวน

180
00:08:37,830 --> 00:08:41,549
>> คุณอาจจะจำได้จาก
วันที่โรงเรียนประถมศึกษา

181
00:08:41,549 --> 00:08:45,740
ว่าลำดับฟีโบนักชีมีการกำหนด
เช่น this-- องค์ประกอบแรกเป็น 0

182
00:08:45,740 --> 00:08:46,890
องค์ประกอบที่สองคือ 1

183
00:08:46,890 --> 00:08:49,230
ทั้งสองของผู้ที่มีเพียงโดยความหมาย

184
00:08:49,230 --> 00:08:55,920
>> จากนั้นทุกองค์ประกอบอื่น ๆ ที่กำหนดไว้
เป็นผลรวมของ n ลบ 1 และ n ลบ 2

185
00:08:55,920 --> 00:09:00,330
ดังนั้นองค์ประกอบที่สาม
จะบวก 1 0 1

186
00:09:00,330 --> 00:09:03,280
แล้วองค์ประกอบที่สี่
จะเป็นองค์ประกอบที่สอง, 1,

187
00:09:03,280 --> 00:09:06,550
รวมทั้งองค์ประกอบที่สาม 1

188
00:09:06,550 --> 00:09:08,507
และนั่นจะเป็น 2

189
00:09:08,507 --> 00:09:09,340
และอื่น ๆ และอื่น ๆ

190
00:09:09,340 --> 00:09:11,680
>> ดังนั้นในกรณีนี้เรามีสองกรณีฐาน

191
00:09:11,680 --> 00:09:14,850
ถ้า n มีค่าเท่ากับ 1 กลับ 0

192
00:09:14,850 --> 00:09:18,560
ถ้า n มีค่าเท่ากับ 2 กลับ 1

193
00:09:18,560 --> 00:09:25,930
มิฉะนั้นผลตอบแทนของ Fibonacci n
บวกลบ 1 ของ Fibonacci n ลบ 2

194
00:09:25,930 --> 00:09:27,180
>> เพื่อให้เป็นกรณีฐานหลาย

195
00:09:27,180 --> 00:09:29,271
สิ่งที่เกี่ยวกับกรณี recursive หลาย

196
00:09:29,271 --> 00:09:31,520
ดีมีบางสิ่งบางอย่าง
ที่เรียกว่าการคาดเดา Collat​​z

197
00:09:31,520 --> 00:09:34,630
ฉันฉันจะไม่พูดว่า
คุณรู้ว่าสิ่งที่เป็น

198
00:09:34,630 --> 00:09:38,170
เพราะมันเป็นเรื่องจริงสุดท้ายของเรา
ปัญหาที่เกิดขึ้นสำหรับวิดีโอนี้โดยเฉพาะ

199
00:09:38,170 --> 00:09:43,220
และก็ออกกำลังกายของเรา
ในการทำงานร่วมกัน

200
00:09:43,220 --> 00:09:46,760
>> ดังนั้นนี่คือสิ่งที่เป็น
Collat​​z คาดเดา is--

201
00:09:46,760 --> 00:09:48,820
มันใช้กับทุกจำนวนเต็มบวก

202
00:09:48,820 --> 00:09:51,500
และมันก็ไม่มีผลตอบแทนว่ามันเป็น
เสมอไปได้ที่จะได้รับกลับ

203
00:09:51,500 --> 00:09:55,060
1 ถ้าคุณทำตามขั้นตอนเหล่านี้

204
00:09:55,060 --> 00:09:57,560
ถ้า n เป็น 1 หยุด

205
00:09:57,560 --> 00:10:00,070
เราเคยได้กลับไป 1 ถ้า n เป็น 1

206
00:10:00,070 --> 00:10:05,670
>> มิฉะนั้นไปผ่านทางนี้
กระบวนการอีกครั้งใน n หารด้วย 2

207
00:10:05,670 --> 00:10:08,200
และดูว่าคุณจะได้รับกลับไปที่ 1

208
00:10:08,200 --> 00:10:13,260
มิฉะนั้นถ้า n เป็นเลขคี่ไปผ่าน
กระบวนการนี​​้อีกครั้งใน 3n บวก 1,

209
00:10:13,260 --> 00:10:15,552
หรือ 3 ครั้ง n บวก 1

210
00:10:15,552 --> 00:10:17,010
ดังนั้นที่นี่เรามีกรณีฐานเดียว

211
00:10:17,010 --> 00:10:18,430
ถ้า n มีค่าเท่ากับ 1 หยุด

212
00:10:18,430 --> 00:10:20,230
เราไม่ได้ดำเนินการใด ๆ เรียกซ้ำมากขึ้น

213
00:10:20,230 --> 00:10:23,730
>> แต่เรามีสองกรณี recursive

214
00:10:23,730 --> 00:10:28,750
ถ้า n คือแม้เราจะทำอย่างใดอย่างหนึ่งเรียกซ้ำ
กรณีโทรแบ่ง n 2

215
00:10:28,750 --> 00:10:33,950
ถ้า n เป็นเลขคี่เราทำที่แตกต่างกัน
กรณีเวียนเกิดเมื่อวันที่ 3 ครั้ง n บวก 1

216
00:10:33,950 --> 00:10:39,120
>> และเพื่อให้เป้าหมายสำหรับวิดีโอนี้
ที่จะใช้สองหยุดวิดีโอ

217
00:10:39,120 --> 00:10:42,440
และพยายามเขียนนี้
ฟังก์ชันเวียน Collat​​z

218
00:10:42,440 --> 00:10:47,640
ที่คุณส่งผ่านค่า n และ
จะคำนวณวิธีการหลายขั้นตอนมัน

219
00:10:47,640 --> 00:10:52,430
ที่จะได้รับ 1 ถ้าคุณเริ่มต้นจาก n
และคุณทำตามขั้นตอนเหล่านั้นขึ้นไปข้างบน

220
00:10:52,430 --> 00:10:56,660
ถ้า n เป็น 1 ก็จะใช้เวลา 0 ขั้นตอน

221
00:10:56,660 --> 00:11:00,190
มิฉะนั้นก็จะ
ใช้ขั้นตอนหนึ่งบวกอย่างไรก็ตาม

222
00:11:00,190 --> 00:11:06,200
หลายขั้นตอนจะใช้เวลาในการอย่างใดอย่างหนึ่ง n
โดยแบ่งออกเป็น 2 ถ้า n คือแม้หรือ 3n บวก 1

223
00:11:06,200 --> 00:11:08,100
ถ้า n เป็นเลขคี่

224
00:11:08,100 --> 00:11:11,190
>> ตอนนี้ผมได้นำขึ้นบนหน้าจอที่นี่
คู่ของสิ่งที่ทดสอบสำหรับคุณ

225
00:11:11,190 --> 00:11:15,690
คู่ของกรณีการทดสอบสำหรับคุณที่จะเห็น
ว่าตัวเลข Collat​​z ต่างๆเหล่านี้

226
00:11:15,690 --> 00:11:17,440
และยังมีภาพประกอบ
ขั้นตอนที่

227
00:11:17,440 --> 00:11:20,390
จะต้องมีการผ่านไปแล้วเพื่อให้คุณสามารถ
การเรียงลำดับของดูขั้นตอนในการดำเนินการนี​​้

228
00:11:20,390 --> 00:11:24,222
ดังนั้นถ้า n มีค่าเท่ากับ
1, Collat​​z ของ n คือ 0

229
00:11:24,222 --> 00:11:26,180
คุณไม่จำเป็นต้องที่จะทำ
สิ่งที่จะได้รับกลับไป 1

230
00:11:26,180 --> 00:11:27,600
คุณมีอยู่แล้ว

231
00:11:27,600 --> 00:11:30,550
>> ถ้า n เป็น 2 ก็จะใช้เวลา
ขั้นตอนหนึ่งที่จะได้รับ 1

232
00:11:30,550 --> 00:11:31,810
คุณเริ่มต้นด้วย 2

233
00:11:31,810 --> 00:11:33,100
ดี 2 ไม่เท่ากับ 1

234
00:11:33,100 --> 00:11:36,580
ดังนั้นจึงเป็นไปได้ในขั้นตอนเดียว
บวก แต่มันหลายขั้นตอน

235
00:11:36,580 --> 00:11:38,015
จะใช้เวลาใน n หารด้วย 2

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

237
00:11:41,280 --> 00:11:42,910
>> โดยแบ่งออกเป็น 2 2 1

238
00:11:42,910 --> 00:11:47,200
ดังนั้นจึงต้องใช้ขั้นตอนที่หนึ่งบวกอย่างไรก็ตาม
หลายขั้นตอนจะใช้เวลา 1

239
00:11:47,200 --> 00:11:49,720
1 ขั้นตอนจะใช้เวลาเป็นศูนย์

240
00:11:49,720 --> 00:11:52,370
>> สำหรับ 3 ที่คุณสามารถดูมี
ค่อนข้างไม่กี่ขั้นตอนที่เกี่ยวข้องกับการ

241
00:11:52,370 --> 00:11:53,590
คุณไปจาก 3

242
00:11:53,590 --> 00:11:56,710
แล้วคุณไป
10, 5, 16, 8, 4, 2, 1

243
00:11:56,710 --> 00:11:58,804
มันต้องใช้เวลาเจ็ดขั้นตอนที่จะได้รับกลับไปที่ 1

244
00:11:58,804 --> 00:12:01,220
และในขณะที่คุณสามารถดูมี
สองสามกรณีทดสอบอื่น ๆ ที่นี่

245
00:12:01,220 --> 00:12:02,470
การทดสอบโปรแกรมของคุณ

246
00:12:02,470 --> 00:12:03,970
ดังนั้นอีกครั้งหยุดวิดีโอ

247
00:12:03,970 --> 00:12:09,210
และฉันจะกระโดดกลับไปตอนนี้
สิ่งที่เกิดขึ้นจริงกระบวนการอยู่ที่นี่

248
00:12:09,210 --> 00:12:11,390
สิ่งที่คาดเดานี้

249
00:12:11,390 --> 00:12:14,140
>> ดูว่าคุณสามารถคิดออก
วิธีการกำหนด Collat​​z ของ n

250
00:12:14,140 --> 00:12:19,967
เพื่อที่จะคำนวณว่าหลาย
ขั้นตอนที่จะได้รับ 1

251
00:12:19,967 --> 00:12:23,050
ดังนั้นหวังว่าคุณได้หยุดชั่วคราววิดีโอ
และคุณไม่ได้เพียงแค่รอให้ฉัน

252
00:12:23,050 --> 00:12:25,820
ที่จะให้คำตอบได้ที่นี่

253
00:12:25,820 --> 00:12:29,120
แต่ถ้าคุณเป็นดี
นี่คือคำตอบอยู่แล้ว

254
00:12:29,120 --> 00:12:33,070
>> ดังนั้นนี่คือความหมายที่เป็นไปได้
ฟังก์ชั่น Collat​​z

255
00:12:33,070 --> 00:12:35,610
ฐานของเรา case-- ถ้า n เป็น
เท่ากับ 1 เรากลับ 0

256
00:12:35,610 --> 00:12:38,250
มันไม่ได้ใช้ใด ๆ
ขั้นตอนที่จะได้รับกลับไปที่ 1

257
00:12:38,250 --> 00:12:42,710
>> มิฉะนั้นเรามีสอง cases-- recursive
สำหรับเลขคู่และหนึ่งสำหรับแปลก

258
00:12:42,710 --> 00:12:47,164
วิธีที่ผมทดสอบแม้ตัวเลข
คือการตรวจสอบว่าสมัย n 2 เท่ากับ 0

259
00:12:47,164 --> 00:12:49,080
นี้เป็นพื้นอีกครั้ง
ถามคำถาม

260
00:12:49,080 --> 00:12:54,050
ถ้าคุณจำสิ่งที่ mod is-- ถ้าฉัน
n หารด้วย 2 จะมีที่เหลือหรือไม่?

261
00:12:54,050 --> 00:12:55,470
ที่จะเป็นเลขคู่

262
00:12:55,470 --> 00:13:01,370
>> และดังนั้นถ้าสมัย n 2 เท่ากับ 0
การทดสอบนี้เป็นเลขคู่

263
00:13:01,370 --> 00:13:04,250
ถ้าเป็นเช่นนั้นผมต้องการที่จะกลับ 1,
เพราะนี้เป็นมั่นเหมาะ

264
00:13:04,250 --> 00:13:09,270
การขั้นตอนหนึ่งบวก Collat​​z ของ
จำนวนสิ่งที่เป็นครึ่งหนึ่งของฉัน

265
00:13:09,270 --> 00:13:13,910
มิฉะนั้นผมต้องการที่จะกลับ 1
บวก Collat​​z 3 ครั้ง n บวก 1

266
00:13:13,910 --> 00:13:16,060
นั่นคืออื่น ๆ
ขั้นตอนที่เราเรียกซ้ำ

267
00:13:16,060 --> 00:13:19,470
อาจจะใช้ในการคำนวณ
Collat​​z-- จำนวนขั้นตอน

268
00:13:19,470 --> 00:13:22,610
ที่จะได้รับกลับมา
1 ได้รับจำนวน

269
00:13:22,610 --> 00:13:24,610
ดังนั้นหวังว่าตัวอย่างนี้
ให้คุณนิด ๆ หน่อย ๆ

270
00:13:24,610 --> 00:13:26,620
รสชาติของขั้นตอนการเรียกซ้ำ

271
00:13:26,620 --> 00:13:30,220
หวังว่าคุณคิดรหัสเป็น
เล็ก ๆ น้อย ๆ ที่สวยงามมากขึ้นหากดำเนินการ

272
00:13:30,220 --> 00:13:32,760
ในที่หรูหราวิธีเวียนเกิด

273
00:13:32,760 --> 00:13:35,955
แต่แม้ว่าจะไม่ได้เรียกซ้ำตัวเองเป็น
เครื่องมือที่มีประสิทธิภาพจริงๆกระนั้น

274
00:13:35,955 --> 00:13:38,330
และดังนั้นจึงเป็นสิ่งที่แน่นอน
ที่จะได้รับหัวของคุณไปรอบ ๆ

275
00:13:38,330 --> 00:13:41,360
เพราะคุณจะสามารถที่จะสร้าง
โปรแกรมเย็นสวยใช้เรียกซ้ำ

276
00:13:41,360 --> 00:13:45,930
ที่อาจจะมีความซับซ้อนในการเขียน
ถ้าคุณกำลังใช้ลูปและซ้ำ

277
00:13:45,930 --> 00:13:46,980
ฉันลอยด์ดั๊ก

278
00:13:46,980 --> 00:13:48,780
นี่คือ CS50

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