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
ใช้ฟังก์ชันนี้ hi ฟังก์ชั่นเป็นโมฆะ
ที่ใช้เวลา 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
ฟังก์ชั่นจะพิมพ์ hi และดำเนินการ
โทรซ้ำ

34
00:01:49,400 --> 00:01:53,600
สายอื่นที่จะทำงาน hi ด้วย
ค่าเข้า decremented

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 อื่น ๆ กว่ากรณีฐาน
ฟังก์ชั่นนี้จะกลับ hi hi

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
ดังนั้นการเรียก hi (3) จะพิมพ์ hi และ
hi ดำเนินการ (2) ที่รัน hi (1) อย่างใดอย่างหนึ่ง

42
00:02:16,960 --> 00:02:20,560
ที่รัน hi (0), ที่
เงื่อนไขกรณีฐานจะพบ

43
00:02:20,560 --> 00:02:24,100
ดังนั้น hi (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
สิ่งที่ผมหมายถึงนี้คือการที่คุณควร
ไว้วางใจเรียก recursive ของคุณเพื่อกลับ

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
ที่ใช้เวลาจำนวนเต็มและส่งกลับ
ผลรวมของติดต่อกันทั้งหมดบวก

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
ว่าไม่มีโหนดใด
ทิ้งไว้ในที่ sub ต้นไม้

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 จะเรียกว่าด้านซ้าย
sub ต้นไม้แรกดังนั้นโหนดซ้าย

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
วิธีที่คุณจะแก้ไข 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
พยายามที่จะแสดงกรณีที่เฉพาะเจาะจงอย่างใดอย่างหนึ่งใน
แง่ของกรณีอื่น ๆ หรือในชุดย่อย

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