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

2
00:00:05,587 --> 00:00:07,670
道格·勞埃德：如果你看過
視頻上的遞歸，

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
這裡只有真正過1
功能處於活動狀態的時間。

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
因此，它會下去
else部分，返回n倍

64
00:03:01,110 --> 00:03:02,990
階乘ñ減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
這將下井else分支。

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
>> 所以它需要調用的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個CAN
說回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的階乘離開本層，並
4階乘是現在的活動框架。

112
00:05:09,410 --> 00:05:13,510
>> 4說，OK，我要回到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