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

2
00:00:05,587 --> 00:00:07,670
DOUG LLOYD: Nếu bạn đã nhìn thấy
video về đệ quy,

3
00:00:07,670 --> 00:00:10,170
toàn bộ quá trình có thể có
dường như một chút huyền diệu.

4
00:00:10,170 --> 00:00:10,930
Làm thế nào nó hoạt động?

5
00:00:10,930 --> 00:00:15,010
Làm thế nào để các chức năng biết rằng họ
cần phải chờ đợi cho giá trị khác

6
00:00:15,010 --> 00:00:19,150
để trở về từ một chức năng khác nhau
gọi để có được kết quả chúng tôi muốn?

7
00:00:19,150 --> 00:00:22,550
>> Vâng, lý do công trình này là vì
của cái gì được gọi là các cuộc gọi stack.

8
00:00:22,550 --> 00:00:26,360
Khi bạn gọi một hàm,
hệ thống dành riêng không gian trong bộ nhớ

9
00:00:26,360 --> 00:00:28,120
cho chức năng đó để làm công việc của mình.

10
00:00:28,120 --> 00:00:31,720
Và chúng ta gọi là các khối của bộ nhớ
đang được dành cho mỗi chức năng

11
00:00:31,720 --> 00:00:35,670
gọi một stack frame hay một khung chức năng.

12
00:00:35,670 --> 00:00:38,290
Và như bạn mong đợi,
các khung stack

13
00:00:38,290 --> 00:00:41,000
sống trên một phần của ngăn xếp bộ nhớ.

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

15
00:00:43,960 --> 00:00:47,540
>> Nhiều hơn một chức năng stack frame
có thể tồn tại trong bộ nhớ tại một thời gian nhất định.

16
00:00:47,540 --> 00:00:51,240
Nếu chính gọi là di chuyển chức năng,
và di chuyển hướng cuộc gọi,

17
00:00:51,240 --> 00:00:54,460
cả ba chức năng có khung mở.

18
00:00:54,460 --> 00:00:57,350
Nhưng họ không phải tất cả có khung hoạt động.

19
00:00:57,350 --> 00:00:59,410
Các khung hình này được bố trí trong một chồng.

20
00:00:59,410 --> 00:01:01,820
Và khung từ
Gần đây nhất được gọi là

21
00:01:01,820 --> 00:01:04,390
hàm luôn luôn là trên đỉnh của ngăn xếp.

22
00:01:04,390 --> 00:01:07,150
Và đó luôn là khung hoạt động.

23
00:01:07,150 --> 00:01:10,420
Chỉ có thực sự bao giờ một
chức năng mà hoạt động tại một thời gian.

24
00:01:10,420 --> 00:01:12,420
Đó là một trong những ngày đầu của stack.

25
00:01:12,420 --> 00:01:17,620
>> Khi một cuộc gọi chức năng khác
chức năng, nó loại nhấn pause.

26
00:01:17,620 --> 00:01:20,590
Nó loại là giữ lại, chờ đợi.

27
00:01:20,590 --> 00:01:24,050
Và một stack frame được đẩy
vào ngăn xếp trên đầu trang của nó.

28
00:01:24,050 --> 00:01:26,150
Và đó trở thành khung hoạt động.

29
00:01:26,150 --> 00:01:28,600
Và khung ngay lập tức
bên dưới nó cần phải chờ đợi

30
00:01:28,600 --> 00:01:33,560
cho đến khi nó là một lần nữa khung hoạt động
trước khi nó có thể tiếp tục công việc của mình.

31
00:01:33,560 --> 00:01:35,870
Khi một chức năng là
hoàn thành và hoàn thành công việc,

32
00:01:35,870 --> 00:01:37,720
khung của nó được popped ra khỏi stack.

33
00:01:37,720 --> 00:01:38,950
Đó là thuật ngữ.

34
00:01:38,950 --> 00:01:41,110
Và khung ngay lập tức
dưới nó, như tôi vừa nói,

35
00:01:41,110 --> 00:01:42,880
trở thành các khung hoạt động mới.

36
00:01:42,880 --> 00:01:45,960
>> Và nếu nó gọi hàm khác,
nó sẽ tạm dừng lại.

37
00:01:45,960 --> 00:01:49,290
Stack frame mà chức năng mới của sẽ
được đẩy lên đỉnh của ngăn xếp.

38
00:01:49,290 --> 00:01:50,650
Nó sẽ làm công việc của mình.

39
00:01:50,650 --> 00:01:52,100
Nó có thể bật lại tắt.

40
00:01:52,100 --> 00:01:55,630
Và các chức năng khác
dưới nó có thể tiếp tục một lần nữa.

41
00:01:55,630 --> 00:02:00,080
>> Vì vậy, hãy đi qua này một lần nữa, tìm
lúc ý tưởng của các chức năng thừa

42
00:02:00,080 --> 00:02:03,070
mà chúng tôi xác định trong
đệ quy video để xem

43
00:02:03,070 --> 00:02:07,770
chính xác cách thức kỳ diệu đằng sau này
quá trình đệ quy được diễn ra.

44
00:02:07,770 --> 00:02:09,870
Vì vậy, đây là toàn bộ tập tin của chúng tôi, phải không?

45
00:02:09,870 --> 00:02:14,000
Chúng tôi định nghĩa hai
functions-- chính và thực tế.

46
00:02:14,000 --> 00:02:15,980
Và như chúng ta có thể mong đợi,
bất kỳ chương trình C sẽ

47
00:02:15,980 --> 00:02:18,470
để bắt đầu ở dòng đầu tiên của chính.

48
00:02:18,470 --> 00:02:21,660
>> Vì vậy, chúng ta tạo một stack frame mới cho chính.

49
00:02:21,660 --> 00:02:23,320
Và nó sẽ bắt đầu chạy.

50
00:02:23,320 --> 00:02:25,270
Cuộc gọi chính printf.

51
00:02:25,270 --> 00:02:29,390
Và printf sẽ
in ra thừa của 5.

52
00:02:29,390 --> 00:02:31,440
Vâng, nó không biết
những gì thừa của 5,

53
00:02:31,440 --> 00:02:35,620
và do đó, điều này gọi là đã
tùy thuộc vào một cuộc gọi chức năng.

54
00:02:35,620 --> 00:02:37,270
Vì vậy, chính là sẽ tạm dừng ngay tại đó.

55
00:02:37,270 --> 00:02:39,103
Tôi sẽ rời khỏi nó
mũi tên bên phải ở đó, màu sắc

56
00:02:39,103 --> 00:02:41,360
nó cùng một màu sắc như là
ngăn xếp khung bên phải,

57
00:02:41,360 --> 00:02:47,720
để chỉ ra rằng chính sẽ đóng băng
ở đây trong khi thừa của 5 được gọi.

58
00:02:47,720 --> 00:02:49,300
>> Vì vậy, giai thừa của 5 được gọi.

59
00:02:49,300 --> 00:02:53,160
Và nó sẽ bắt đầu ở rất
bắt đầu của các chức năng thừa.

60
00:02:53,160 --> 00:02:55,440
Nó nhắc đi nhắc lại câu hỏi tôi bằng 1?

61
00:02:55,440 --> 00:02:56,810
5 bằng 1?

62
00:02:56,810 --> 00:02:57,410
Ồ không.

63
00:02:57,410 --> 00:03:01,110
Vì vậy, nó sẽ đi xuống
phần else return n lần

64
00:03:01,110 --> 00:03:02,990
thừa của n trừ đi 1.

65
00:03:02,990 --> 00:03:03,490
Tốt.

66
00:03:03,490 --> 00:03:07,070
>> Vì vậy, bây giờ, giai thừa của 5
tùy thuộc vào một cuộc gọi khác

67
00:03:07,070 --> 00:03:09,740
để factorial, đi qua
trong 4 như các tham số.

68
00:03:09,740 --> 00:03:14,210
Và do đó, giai thừa của
5 khung hình, mà khung màu đỏ,

69
00:03:14,210 --> 00:03:17,160
sẽ đóng băng ngay tại đó
tại dòng mà tôi đã chỉ ra

70
00:03:17,160 --> 00:03:21,914
và chờ cho thừa của 4 để kết thúc
những gì nó cần phải làm như vậy mà sau đó nó

71
00:03:21,914 --> 00:03:23,330
có thể trở thành các khung hoạt động trở lại.

72
00:03:23,330 --> 00:03:26,890
>> Vì vậy factorial của 4 bắt đầu tại
đầu thừa.

73
00:03:26,890 --> 00:03:28,556
Là 4 bằng 1?

74
00:03:28,556 --> 00:03:30,180
Không, vì vậy nó sẽ làm điều tương tự.

75
00:03:30,180 --> 00:03:31,590
Nó sẽ đi xuống các chi nhánh khác.

76
00:03:31,590 --> 00:03:33,240
Nó sẽ nhận được để mà dòng mã.

77
00:03:33,240 --> 00:03:35,710
OK, tôi sẽ trở lại bốn lần.

78
00:03:35,710 --> 00:03:41,270
Oh, thừa của 3-- vậy factorial của
4 phụ thuộc vào giai thừa của 3 hoàn thiện.

79
00:03:41,270 --> 00:03:43,055
>> Và do đó, nó cần gọi thừa của 3.

80
00:03:43,055 --> 00:03:45,180
Và điều đó sẽ đi qua
cùng một quá trình một lần nữa.

81
00:03:45,180 --> 00:03:48,200
Nó bắt đầu thông qua, được ở đây.

82
00:03:48,200 --> 00:03:50,980
Thừa của 3 phụ thuộc
về thừa của 1.

83
00:03:50,980 --> 00:03:53,750
Vì vậy, thừa của 2 bắt đầu, được ở đây.

84
00:03:53,750 --> 00:03:56,310
Nó phụ thuộc vào giai thừa của 1.

85
00:03:56,310 --> 00:03:57,430
Thừa của 1 bắt đầu.

86
00:03:57,430 --> 00:03:57,650
>> ĐƯỢC.

87
00:03:57,650 --> 00:03:59,775
Vì vậy, bây giờ, chúng tôi đang nhận
một nơi nào đó thú vị, phải không?

88
00:03:59,775 --> 00:04:02,190
Vì vậy, bây giờ, 1 bằng 1.

89
00:04:02,190 --> 00:04:05,130
Và vì vậy chúng tôi trở về 1.

90
00:04:05,130 --> 00:04:06,770
Tại thời điểm này, chúng tôi đang quay trở lại.

91
00:04:06,770 --> 00:04:07,880
Các chức năng được thực hiện.

92
00:04:07,880 --> 00:04:11,140
Đó là thái độ is-- có
không có gì khác cho nó để làm,

93
00:04:11,140 --> 00:04:17,006
và do đó, các khung stack cho
thừa của 1 bật tắt.

94
00:04:17,006 --> 00:04:17,589
Mọi chuyện đã kết thúc rồi.

95
00:04:17,589 --> 00:04:19,480
Nó trở lại 1.

96
00:04:19,480 --> 00:04:23,370
Và bây giờ, thừa của 2,
là khung ngay bên dưới nó

97
00:04:23,370 --> 00:04:26,160
trong ngăn xếp, trở thành khung hoạt động.

98
00:04:26,160 --> 00:04:29,030
>> Và nó có thể nhận
chính xác nơi nó lại tắt.

99
00:04:29,030 --> 00:04:32,240
Nó được chờ đợi cho một giai thừa
của 1 để kết thúc công việc của mình.

100
00:04:32,240 --> 00:04:33,610
Nó bây giờ đã hoàn thành.

101
00:04:33,610 --> 00:04:35,510
Và như vậy chúng ta ở đây.

102
00:04:35,510 --> 00:04:38,080
>> Thừa của 1 trả lại một giá trị là 1.

103
00:04:38,080 --> 00:04:42,430
Vì vậy, thừa của 2 lon
nói trả lại 2 lần 1.

104
00:04:42,430 --> 00:04:43,680
Công việc của nó bây giờ được thực hiện.

105
00:04:43,680 --> 00:04:49,110
Nó thấy 2 để factorial
3, được chờ đợi nó.

106
00:04:49,110 --> 00:04:53,370
Thừa của 3 tại là khung trên,
khung hoạt động trong stack.

107
00:04:53,370 --> 00:04:58,617
Và do đó, nó nói, OK, tốt, tôi sẽ
để trở lại 3 lần 2, mà là 6.

108
00:04:58,617 --> 00:05:00,700
Và tôi sẽ cung cấp cho rằng
đánh giá lại để thừa

109
00:05:00,700 --> 00:05:03,430
4, đã được chờ đợi tôi.

110
00:05:03,430 --> 00:05:04,500
Tôi đa xong.

111
00:05:04,500 --> 00:05:09,410
Thừa của 3 bật ra khỏi ngăn xếp, và
thừa của 4 doanh nghiệp là khung hoạt động.

112
00:05:09,410 --> 00:05:13,510
>> 4 nói, OK, tôi sẽ trả lại 4 lần
giai thừa của 3, đó là sáu.

113
00:05:13,510 --> 00:05:15,980
Đó là giá trị mà
thừa của 3 trở lại.

114
00:05:15,980 --> 00:05:19,010
Và như vậy 4 lần 6 là 24.

115
00:05:19,010 --> 00:05:20,990
Và tôi sẽ vượt qua
trở lại đó để factorial

116
00:05:20,990 --> 00:05:23,160
5, đã được chờ đợi tôi.

117
00:05:23,160 --> 00:05:25,270
Thừa của 5 tại là khung hoạt động.

118
00:05:25,270 --> 00:05:30,700
Nó sẽ trả lại 5 lần
thừa của 4-- 5 lần 24, hoặc 120--

119
00:05:30,700 --> 00:05:32,722
và đưa ra giá trị đó
trở lại chính, trong đó có

120
00:05:32,722 --> 00:05:35,680
được chờ đợi rất kiên nhẫn cho một
thời gian dài ở dưới cùng của ngăn xếp.

121
00:05:35,680 --> 00:05:36,640
>> Đó là nơi mà nó bắt đầu.

122
00:05:36,640 --> 00:05:37,670
Nó làm cho cuộc gọi này.

123
00:05:37,670 --> 00:05:39,400
Một số khung đã qua ở đầu trang.

124
00:05:39,400 --> 00:05:41,890
Nó bây giờ đã trở lại trên đầu của stack.

125
00:05:41,890 --> 00:05:43,450
Đó là khung hoạt động.

126
00:05:43,450 --> 00:05:47,810
Vì vậy, chính có giá trị 120
trở lại từ giai thừa của 5.

127
00:05:47,810 --> 00:05:50,750
Nó được chờ đợi để
in ra giá trị đó.

128
00:05:50,750 --> 00:05:51,657
Và sau đó nó được thực hiện.

129
00:05:51,657 --> 00:05:53,240
Không có nhiều dòng mã trong chính.

130
00:05:53,240 --> 00:05:56,800
Vì vậy, khung chính của bật tắt
ngăn xếp, và chúng tôi đang thực hiện.

131
00:05:56,800 --> 00:05:58,992
>> Và đó là cách đệ quy trình.

132
00:05:58,992 --> 00:06:00,200
Đó là cách các khung stack làm việc.

133
00:06:00,200 --> 00:06:03,120
Những cuộc gọi chức năng
đã xảy ra trước đó

134
00:06:03,120 --> 00:06:06,620
chỉ là về tạm dừng, chờ đợi
cho các cuộc gọi tiếp theo

135
00:06:06,620 --> 00:06:12,050
để kết thúc để họ có thể trở thành hoạt động
khung và hoàn thành những gì họ cần làm.

136
00:06:12,050 --> 00:06:13,060
>> Tôi Doug Lloyd.

137
00:06:13,060 --> 00:06:14,880
Đây là CS50.

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