1
00:00:00,000 --> 00:00:05,587

2
00:00:05,587 --> 00:00:07,670
DOUG LLOYD: ถ้าคุณเคยเห็น
วิดีโอเกี่ยวกับการเรียกซ้ำ

3
00:00:07,670 --> 00:00:10,170
กระบวนการทั้งหมดอาจจะมี
ดูเหมือนนิด ๆ หน่อย ๆ ที่มีมนต์ขลัง

4
00:00:10,170 --> 00:00:10,930
มันทำงานยังไง?

5
00:00:10,930 --> 00:00:15,010
วิธีการทำงานจะรู้ว่าพวกเขา
จำเป็นต้องรอและรอค่าอื่น

6
00:00:15,010 --> 00:00:19,150
จะกลับมาจากที่แตกต่างกันฟังก์ชั่น
โทรในการสั่งซื้อเพื่อให้ได้ผลที่เราต้องการหรือไม่

7
00:00:19,150 --> 00:00:22,550
>> ดีเหตุผลที่งานนี้เป็นเพราะ
บางสิ่งบางอย่างที่รู้จักกันเป็นกองสาย

8
00:00:22,550 --> 00:00:26,360
เมื่อคุณเรียกฟังก์ชั่นที่
ระบบชุดกันพื้นที่ในหน่วยความจำ

9
00:00:26,360 --> 00:00:28,120
สำหรับฟังก์ชั่นการทำงานที่

10
00:00:28,120 --> 00:00:31,720
และที่เราเรียกว่าชิ้นนี้ของหน่วยความจำที่
มีการตั้งสำรองสำหรับแต่ละฟังก์ชัน

11
00:00:31,720 --> 00:00:35,670
เรียกกองกรอบหรือกรอบการทำงาน

12
00:00:35,670 --> 00:00:38,290
และในขณะที่คุณอาจคาดหวัง
เหล่านี้เฟรมสแต็ค

13
00:00:38,290 --> 00:00:41,000
อาศัยอยู่ในส่วนของสแต็คของหน่วยความจำ

14
00:00:41,000 --> 00:00:43,960

15
00:00:43,960 --> 00:00:47,540
>> มากกว่าหนึ่งกองกรอบการทำงาน
สามารถอยู่ในความทรงจำในเวลาที่กำหนด

16
00:00:47,540 --> 00:00:51,240
ถ้าสายหลักย้ายฟังก์ชั่น
และเรียกร้องให้ย้ายทิศทาง

17
00:00:51,240 --> 00:00:54,460
ทั้งสามฟังก์ชั่นที่มีกรอบการเปิด

18
00:00:54,460 --> 00:00:57,350
แต่พวกเขาไม่ได้ทุกคนมีกรอบการใช้งาน

19
00:00:57,350 --> 00:00:59,410
ภาพเหล่านี้จะถูกจัดให้อยู่ในกอง

20
00:00:59,410 --> 00:01:01,820
และกรอบจากที่
มากที่สุดเมื่อเร็ว ๆ นี้ที่เรียกว่า

21
00:01:01,820 --> 00:01:04,390
ฟังก์ชั่นอยู่เสมอด้านบนของสแต็ค

22
00:01:04,390 --> 00:01:07,150
และที่อยู่เสมอกรอบการใช้งาน

23
00:01:07,150 --> 00:01:10,420
มีเพียงหนึ่งจริงๆเคย
ฟังก์ชั่นที่ใช้งานได้ตลอดเวลา

24
00:01:10,420 --> 00:01:12,420
มันเป็นหนึ่งในด้านบนของสแต็ค

25
00:01:12,420 --> 00:01:17,620
>> เมื่อมีการเรียกฟังก์ชั่นอื่น
ฟังก์ชั่นการจัดเรียงของมันกดหยุดชั่วคราว

26
00:01:17,620 --> 00:01:20,590
มันคือการจัดเรียงของที่ถือรอ

27
00:01:20,590 --> 00:01:24,050
และกองกรอบอื่นจะถูกผลัก
บนสแต็คที่ด้านบนของมัน

28
00:01:24,050 --> 00:01:26,150
และนั่นกลายเป็นกรอบที่ใช้งานอยู่

29
00:01:26,150 --> 00:01:28,600
และกรอบทันที
ด้านล่างจะต้องรอ

30
00:01:28,600 --> 00:01:33,560
จนกว่าจะมีกรอบอีกครั้งที่ใช้งาน
ก่อนที่จะสามารถดำเนินการต่อการทำงานของมัน

31
00:01:33,560 --> 00:01:35,870
เมื่อฟังก์ชั่นเป็น
ที่สมบูรณ์และมันทำ

32
00:01:35,870 --> 00:01:37,720
กรอบของมันจะโผล่ออกกอง

33
00:01:37,720 --> 00:01:38,950
นั่นเป็นคำศัพท์

34
00:01:38,950 --> 00:01:41,110
และกรอบทันที
ด้านล่างเป็นฉันเพียงแค่กล่าวว่า

35
00:01:41,110 --> 00:01:42,880
กลายเป็นกรอบใหม่ที่ใช้งาน

36
00:01:42,880 --> 00:01:45,960
>> และถ้ามันเรียกฟังก์ชั่นอื่น
ก็จะหยุดการทำงานชั่วคราวอีกครั้ง

37
00:01:45,960 --> 00:01:49,290
กรอบสแต็คที่ฟังก์ชั่นใหม่จะ
จะผลักดันไปยังด้านบนของสแต็ค

38
00:01:49,290 --> 00:01:50,650
มันจะทำงานของมัน

39
00:01:50,650 --> 00:01:52,100
มันอาจปรากฏกลับออก

40
00:01:52,100 --> 00:01:55,630
และฟังก์ชั่นอื่น ๆ
ด้านล่างจะสามารถกลับมาทำงานอีกครั้ง

41
00:01:55,630 --> 00:02:00,080
>> ถ้าอย่างนั้นเราไปถึงนี้อีกครั้งมอง
ที่ความคิดของฟังก์ชั่นแฟกทอ

42
00:02:00,080 --> 00:02:03,070
ที่เรากำหนดไว้ใน
วิดีโอเรียกซ้ำเพื่อดู

43
00:02:03,070 --> 00:02:07,770
ว่าวิธีการที่อยู่เบื้องหลังความมหัศจรรย์นี้
ขั้นตอนการเรียกซ้ำที่เกิดขึ้น

44
00:02:07,770 --> 00:02:09,870
ดังนั้นนี่คือไฟล์ทั้งหมดของเราใช่มั้ย?

45
00:02:09,870 --> 00:02:14,000
เรากำหนดสอง
functions-- หลักและความเป็นจริง

46
00:02:14,000 --> 00:02:15,980
และในขณะที่เราอาจคาดหวัง
โปรแกรม C ใด ๆ ที่เกิดขึ้น

47
00:02:15,980 --> 00:02:18,470
จะเริ่มต้นที่บรรทัดแรกของหลัก

48
00:02:18,470 --> 00:02:21,660
>> ดังนั้นเราจึงสร้างกองกรอบใหม่สำหรับหลัก

49
00:02:21,660 --> 00:02:23,320
และมันก็จะเริ่มทำงาน

50
00:02:23,320 --> 00:02:25,270
สายหลัก printf

51
00:02:25,270 --> 00:02:29,390
และ printf เป็นไป
พิมพ์ออกมาจาก 5 ปัจจัย

52
00:02:29,390 --> 00:02:31,440
ดีก็ไม่ทราบ
สิ่งที่ปัจจัย 5 คือ

53
00:02:31,440 --> 00:02:35,620
และเพื่อให้การเรียกร้องนี้มีอยู่แล้ว
ขึ้นอยู่กับการเรียกใช้ฟังก์ชันอื่น

54
00:02:35,620 --> 00:02:37,270
หลักดังนั้นจะไปหยุดอยู่ที่นั่น

55
00:02:37,270 --> 00:02:39,103
ผมจะปล่อยให้มัน
ลูกศรขวามีสี

56
00:02:39,103 --> 00:02:41,360
มันมีสีเดียวกันเป็น
สแต็คกรอบด้านขวา

57
00:02:41,360 --> 00:02:47,720
เพื่อแสดงให้เห็นว่าหลักเป็นไปแช่แข็ง
ที่นี่ในขณะปัจจัย 5 ที่เรียกว่า

58
00:02:47,720 --> 00:02:49,300
>> ดังนั้นปัจจัย 5 ที่เรียกว่า

59
00:02:49,300 --> 00:02:53,160
และมันจะเริ่มต้นที่มาก
เริ่มต้นการทำงานของปัจจัย

60
00:02:53,160 --> 00:02:55,440
มันถามคำถามที่ฉันกำลังเท่ากับ 1

61
00:02:55,440 --> 00:02:56,810
คือ 5 เท่ากับ 1?

62
00:02:56,810 --> 00:02:57,410
ดีไม่มี

63
00:02:57,410 --> 00:03:01,110
ดังนั้นมันจะลงไป
ส่วนอื่นกลับ n ครั้ง

64
00:03:01,110 --> 00:03:02,990
ปัจจัยของ n ลบ 1

65
00:03:02,990 --> 00:03:03,490
ดีตกลง

66
00:03:03,490 --> 00:03:07,070
>> ดังนั้นตอนนี้ปัจจัย 5 คือ
ขึ้นอยู่กับสายอื่น

67
00:03:07,070 --> 00:03:09,740
ปัจจัยที่จะผ่าน
4 เป็นพารามิเตอร์

68
00:03:09,740 --> 00:03:14,210
ดังนั้นปัจจัยของ
5 กรอบที่กรอบสีแดง

69
00:03:14,210 --> 00:03:17,160
จะไปหยุดอยู่ที่นั่น
ที่บรรทัดที่ฉันได้แสดงให้เห็น

70
00:03:17,160 --> 00:03:21,914
และรอปัจจัย 4 ที่จะเสร็จสิ้น
สิ่งที่ต้องทำเพื่อที่แล้วมัน

71
00:03:21,914 --> 00:03:23,330
จะกลายเป็นกรอบที่ใช้งานอีกครั้ง

72
00:03:23,330 --> 00:03:26,890
>> ดังนั้นปัจจัย 4 เริ่มต้นที่
จุดเริ่มต้นของปัจจัย

73
00:03:26,890 --> 00:03:28,556
4 เท่ากับ 1?

74
00:03:28,556 --> 00:03:30,180
ไม่เช่นนั้นก็จะทำสิ่งเดียวกัน

75
00:03:30,180 --> 00:03:31,590
มันจะลงไปสาขาอื่น

76
00:03:31,590 --> 00:03:33,240
ก็จะได้รับไปยังบรรทัดของรหัสที่

77
00:03:33,240 --> 00:03:35,710
ตกลงฉันจะกลับมาสี่ครั้ง

78
00:03:35,710 --> 00:03:41,270
โอ้ปัจจัยของ 3-- ดังนั้นปัจจัยของ
4 ขึ้นอยู่กับปัจจัย 3 ตกแต่ง

79
00:03:41,270 --> 00:03:43,055
>> และดังนั้นจึงต้องมีการเรียก factorial 3

80
00:03:43,055 --> 00:03:45,180
และที่จะไปผ่าน
กระบวนการเดียวกันอีกครั้ง

81
00:03:45,180 --> 00:03:48,200
มันเริ่มต้นผ่านได้ที่นี่

82
00:03:48,200 --> 00:03:50,980
ปัจจัย 3 ขึ้น
ในปัจจัยที่ 1

83
00:03:50,980 --> 00:03:53,750
ดังนั้นปัจจัย 2 เริ่มต้นที่นี่ได้รับ

84
00:03:53,750 --> 00:03:56,310
มันขึ้นอยู่กับปัจจัยที่ 1

85
00:03:56,310 --> 00:03:57,430
ปัจจัยที่ 1 เริ่มต้น

86
00:03:57,430 --> 00:03:57,650
>> ตกลง.

87
00:03:57,650 --> 00:03:59,775
ดังนั้นตอนนี้เราได้รับ
ที่ไหนสักแห่งที่น่าสนใจใช่มั้ย?

88
00:03:59,775 --> 00:04:02,190
ดังนั้นตอนนี้ 1 มีค่าเท่ากับ 1

89
00:04:02,190 --> 00:04:05,130
และเพื่อให้เรากลับ 1

90
00:04:05,130 --> 00:04:06,770
ณ จุดนี้เราจะกลับมา

91
00:04:06,770 --> 00:04:07,880
ของทำฟังก์ชั่น

92
00:04:07,880 --> 00:04:11,140
มันเป็นพฤติกรรม is-- มี
ไม่มีอะไรมันจะทำ

93
00:04:11,140 --> 00:04:17,006
และเพื่อให้กองกรอบสำหรับ
ปัจจัยที่ 1 ปรากฏออก

94
00:04:17,006 --> 00:04:17,589
มันเสร็จ

95
00:04:17,589 --> 00:04:19,480
มันกลับมา 1

96
00:04:19,480 --> 00:04:23,370
และตอนนี้ปัจจัยของ 2 ซึ่ง
เป็นกรอบด้านล่างทันที

97
00:04:23,370 --> 00:04:26,160
ในกองกลายเป็นกรอบที่ใช้งานอยู่

98
00:04:26,160 --> 00:04:29,030
>> และมันสามารถรับ
ตรงที่มันทิ้งไป

99
00:04:29,030 --> 00:04:32,240
มันได้รับการรอปัจจัย
1 ที่จะเสร็จสิ้นการทำงานของมัน

100
00:04:32,240 --> 00:04:33,610
จะได้ดำเนินการเสร็จสิ้นในขณะนี้

101
00:04:33,610 --> 00:04:35,510
และอื่น ๆ ที่นี่เรามี

102
00:04:35,510 --> 00:04:38,080
>> ปัจจัยที่ 1 กลับค่าเป็น 1

103
00:04:38,080 --> 00:04:42,430
ดังนั้นปัจจัย 2 กระป๋อง
กล่าวว่าการกลับมาครั้งที่ 2 1

104
00:04:42,430 --> 00:04:43,680
การทำงานของมันจะทำในขณะนี้

105
00:04:43,680 --> 00:04:49,110
มันกลับ 2 ปัจจัย
3 ซึ่งได้รับการรอให้มัน

106
00:04:49,110 --> 00:04:53,370
ปัจจัย 3 อยู่ในขณะนี้กรอบด้านบน
กรอบการใช้งานในกอง

107
00:04:53,370 --> 00:04:58,617
และดังนั้นจึงกล่าวว่าตกลงกันฉันจะ
ที่จะกลับมา 3 ครั้งที่ 2 ซึ่งเป็น 6

108
00:04:58,617 --> 00:05:00,700
และฉันจะให้ที่
ค่ากลับไปที่ปัจจัย

109
00:05:00,700 --> 00:05:03,430
4 ซึ่งได้รับการรอคอยสำหรับฉัน

110
00:05:03,430 --> 00:05:04,500
ฉันทำ

111
00:05:04,500 --> 00:05:09,410
ปัจจัย 3 ปรากฏออกมาจาก stack และ
ปัจจัย 4 คือตอนนี้กรอบที่ใช้งานอยู่

112
00:05:09,410 --> 00:05:13,510
>> 4 กล่าวว่าตกลงฉันจะกลับมา 4 ครั้ง
ปัจจัยใน 3 ซึ่งเป็นหก

113
00:05:13,510 --> 00:05:15,980
นั่นคือของค่าที่
ปัจจัย 3 กลับ

114
00:05:15,980 --> 00:05:19,010
และอื่น ๆ 4 ครั้งที่ 6 คือ 24

115
00:05:19,010 --> 00:05:20,990
และฉันจะผ่าน
กลับไปที่ปัจจัย

116
00:05:20,990 --> 00:05:23,160
5 ซึ่งได้รับการรอคอยสำหรับฉัน

117
00:05:23,160 --> 00:05:25,270
ปัจจัย 5 อยู่ในขณะนี้กรอบที่ใช้งานอยู่

118
00:05:25,270 --> 00:05:30,700
มันจะกลับมา 5 ครั้ง
ปัจจัยของ 4-- 5 ครั้งที่ 24 หรือ 120--

119
00:05:30,700 --> 00:05:32,722
และให้ค่าที่
กลับไปที่หลักซึ่งมี

120
00:05:32,722 --> 00:05:35,680
รอคอยอย่างอดทนมากสำหรับ
เวลานานที่ด้านล่างของสแต็ค

121
00:05:35,680 --> 00:05:36,640
>> มันเป็นเรื่องที่มันเริ่มต้น

122
00:05:36,640 --> 00:05:37,670
มันทำให้สายนี้

123
00:05:37,670 --> 00:05:39,400
หลายเฟรมเข้ามาที่ด้านบน

124
00:05:39,400 --> 00:05:41,890
คือตอนนี้กลับมาอยู่ด้านบนของสแต็ค

125
00:05:41,890 --> 00:05:43,450
มันเป็นกรอบที่ใช้งานอยู่

126
00:05:43,450 --> 00:05:47,810
ดังนั้นหลักมีค่า 120
กลับมาจากปัจจัย 5

127
00:05:47,810 --> 00:05:50,750
จะได้รับการรอคอยที่จะ
พิมพ์ค่าที่

128
00:05:50,750 --> 00:05:51,657
และจากนั้นก็ทำ

129
00:05:51,657 --> 00:05:53,240
ไม่มีบรรทัดที่มากขึ้นของรหัสในหลักเป็น

130
00:05:53,240 --> 00:05:56,800
ดังนั้นกรอบหลักของปรากฏออก
สแต็คและเรากำลังทำ

131
00:05:56,800 --> 00:05:58,992
>> และนั่นคือวิธีการเรียกซ้ำงาน

132
00:05:58,992 --> 00:06:00,200
นั่นเป็นวิธีที่เฟรมสแต็คทำงาน

133
00:06:00,200 --> 00:06:03,120
ผู้ที่ฟังก์ชั่นการโทร
ก่อนหน้านี้ที่เกิดขึ้น

134
00:06:03,120 --> 00:06:06,620
เป็นเพียงเกี่ยวกับการหยุดรอ
สำหรับการโทรตามมา

135
00:06:06,620 --> 00:06:12,050
จะเสร็จสิ้นเพื่อให้พวกเขาสามารถกลายเป็นที่ใช้งานอยู่
กรอบและเสร็จสิ้นสิ่งที่พวกเขาต้องทำ

136
00:06:12,050 --> 00:06:13,060
>> ฉันลอยด์ดั๊ก

137
00:06:13,060 --> 00:06:14,880
นี่คือ CS50

138
00:06:14,880 --> 00:06:16,580