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

2
00:00:05,587 --> 00:00:07,670
DOUG LLOYD: Jeśli widzieliście
wideo na rekursji,

3
00:00:07,670 --> 00:00:10,170
cały proces może mieć
Wydawało się trochę magiczne.

4
00:00:10,170 --> 00:00:10,930
Jak to działa?

5
00:00:10,930 --> 00:00:15,010
Jak funkcje wiedzieć, że
trzeba czekać i czekać na inną wartość

6
00:00:15,010 --> 00:00:19,150
powrócić z inną funkcją
zadzwonić, aby uzyskać wynik chcemy?

7
00:00:19,150 --> 00:00:22,550
>> Cóż, powód to działa to, ponieważ
czegoś znanego jako stos wywołań.

8
00:00:22,550 --> 00:00:26,360
Kiedy zadzwonić do funkcji,
System rezerwuje miejsca w pamięci

9
00:00:26,360 --> 00:00:28,120
dla tej funkcji, aby wykonać swoją pracę.

10
00:00:28,120 --> 00:00:31,720
A my nazywamy te fragmenty pamięci, które
odłogowania są dla każdej funkcji

11
00:00:31,720 --> 00:00:35,670
wywołać ramkę stosu lub ramkę funkcji.

12
00:00:35,670 --> 00:00:38,290
I jak można się spodziewać,
te ramki stosu

13
00:00:38,290 --> 00:00:41,000
Mieszkam na części stosu pamięci.

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

15
00:00:43,960 --> 00:00:47,540
>> Więcej niż jedna funkcja stosu ramki
może występować w pamięci w danym czasie.

16
00:00:47,540 --> 00:00:51,240
Jeśli głównym wywołuje ruch funkcji,
i ruch nazywa kierunek,

17
00:00:51,240 --> 00:00:54,460
Wszystkie trzy funkcje mają otwarte ramki.

18
00:00:54,460 --> 00:00:57,350
Ale nie wszyscy mają aktywnych ramek.

19
00:00:57,350 --> 00:00:59,410
Ramy te są ułożone w stos.

20
00:00:59,410 --> 00:01:01,820
I rama z
ostatnio się

21
00:01:01,820 --> 00:01:04,390
Funkcja ta jest zawsze na górze stosu.

22
00:01:04,390 --> 00:01:07,150
I to jest zawsze aktywna ramka.

23
00:01:07,150 --> 00:01:10,420
Jest tylko jeden naprawdę kiedykolwiek
aktywna funkcja to na raz.

24
00:01:10,420 --> 00:01:12,420
Jest to jeden na górze stosu.

25
00:01:12,420 --> 00:01:17,620
>> Gdy funkcja wymaga innego
Funkcja, to jakby naciska pauzę.

26
00:01:17,620 --> 00:01:20,590
To rodzaj jest zawieszone, czekając.

27
00:01:20,590 --> 00:01:24,050
I kolejna ramka stosu jest wciśnięty
na stos na wierzchu.

28
00:01:24,050 --> 00:01:26,150
I to staje się aktywna ramka.

29
00:01:26,150 --> 00:01:28,600
I rama natychmiast
Poniżej musi czekać

30
00:01:28,600 --> 00:01:33,560
dopóki nie jest jeszcze aktywna ramka
zanim będzie mógł wznowić swoje prace.

31
00:01:33,560 --> 00:01:35,870
Kiedy funkcja jest
kompletne i gotowe,

32
00:01:35,870 --> 00:01:37,720
jego rama jest zdejmowana ze stosu.

33
00:01:37,720 --> 00:01:38,950
To jest terminologia.

34
00:01:38,950 --> 00:01:41,110
I rama natychmiast
pod nim, jak już powiedziałem,

35
00:01:41,110 --> 00:01:42,880
staje się nową aktywną ramkę.

36
00:01:42,880 --> 00:01:45,960
>> A jeśli wywołuje inną funkcję,
to się jeszcze wstrzymać.

37
00:01:45,960 --> 00:01:49,290
Stack frame, że nowa funkcja będzie
zostać przesunięta na górze stosu.

38
00:01:49,290 --> 00:01:50,650
To zrobi swoją pracę.

39
00:01:50,650 --> 00:01:52,100
To może pop wycofać.

40
00:01:52,100 --> 00:01:55,630
A druga funkcja
Poniżej można go wznowić.

41
00:01:55,630 --> 00:02:00,080
>> Warto więc przejść przez to jeszcze raz, patrząc
na myśl o funkcji silni

42
00:02:00,080 --> 00:02:03,070
że zdefiniowane w
rekurencja video,

43
00:02:03,070 --> 00:02:07,770
dokładnie, jak magia za tym
Proces odbywa rekurencyjne.

44
00:02:07,770 --> 00:02:09,870
Więc to jest nasz cały plik, tak?

45
00:02:09,870 --> 00:02:14,000
Mamy zdefiniowane dwa
functions-- głównym i fakt.

46
00:02:14,000 --> 00:02:15,980
I jak można się spodziewać,
każdy program C będzie

47
00:02:15,980 --> 00:02:18,470
aby rozpocząć w pierwszej linii głównej.

48
00:02:18,470 --> 00:02:21,660
>> Więc utworzyć nową ramkę stosu dla Głównym.

49
00:02:21,660 --> 00:02:23,320
I to będzie się ukazywać.

50
00:02:23,320 --> 00:02:25,270
Główne połączenia printf.

51
00:02:25,270 --> 00:02:29,390
I printf będzie
wydrukować silni 5.

52
00:02:29,390 --> 00:02:31,440
Cóż, nie wiem,
silnia z 5, co jest,

53
00:02:31,440 --> 00:02:35,620
i tak to wezwanie jest już
w zależności od innego wywołania funkcji.

54
00:02:35,620 --> 00:02:37,270
Tak więc głównym będzie wstrzymać tam.

55
00:02:37,270 --> 00:02:39,103
Zamierzam zostawić jej
strzałka w prawo tam, kolor

56
00:02:39,103 --> 00:02:41,360
to ten sam kolor, jak
stos ramki po prawej stronie,

57
00:02:41,360 --> 00:02:47,720
co oznacza, że ​​główny ma zamrożenia
tutaj natomiast silnia 5 nazywa.

58
00:02:47,720 --> 00:02:49,300
>> Więc silnia 5 nazywa.

59
00:02:49,300 --> 00:02:53,160
I to będzie rozpocząć się bardzo
począwszy od funkcji silni.

60
00:02:53,160 --> 00:02:55,440
To zadaje pytanie mam równa 1?

61
00:02:55,440 --> 00:02:56,810
5 jest równa 1?

62
00:02:56,810 --> 00:02:57,410
Nie dobrze.

63
00:02:57,410 --> 00:03:01,110
Więc to będzie zejść do
else część, powrót n razy

64
00:03:01,110 --> 00:03:02,990
silnia n minus 1.

65
00:03:02,990 --> 00:03:03,490
No, OK.

66
00:03:03,490 --> 00:03:07,070
>> Więc teraz, silnia 5 jest
w zależności od innego połączenia

67
00:03:07,070 --> 00:03:09,740
do czynnikowych, przechodząc
w 4 jako parametru.

68
00:03:09,740 --> 00:03:14,210
I tak silnia
5 ramka, że ​​czerwoną ramką,

69
00:03:14,210 --> 00:03:17,160
zamierza zamrozić tam
w tym wierszu Mam wskazany

70
00:03:17,160 --> 00:03:21,914
i czekać na silni 4 do końca
co trzeba zrobić, aby następnie go

71
00:03:21,914 --> 00:03:23,330
może stać się ponownie aktywną ramkę.

72
00:03:23,330 --> 00:03:26,890
>> Tak silni 4 startów w
początek silnia.

73
00:03:26,890 --> 00:03:28,556
Czy 4 równe 1?

74
00:03:28,556 --> 00:03:30,180
Nie, tak to będzie to samo.

75
00:03:30,180 --> 00:03:31,590
To będzie zejść z innego oddziału.

76
00:03:31,590 --> 00:03:33,240
To będzie dostać się do tej linii kodu.

77
00:03:33,240 --> 00:03:35,710
OK, mam zamiar wrócić cztery razy.

78
00:03:35,710 --> 00:03:41,270
Och, silnia 3-- tak silni
4 zależy od silni 3 wykończenia.

79
00:03:41,270 --> 00:03:43,055
>> A więc musi zadzwonić silni 3.

80
00:03:43,055 --> 00:03:45,180
I to będzie przejść przez
Ten sam proces ponownie.

81
00:03:45,180 --> 00:03:48,200
Zaczyna poprzez, dostaje tutaj.

82
00:03:48,200 --> 00:03:50,980
Silnia 3 zależy
na silni 1.

83
00:03:50,980 --> 00:03:53,750
Więc silnia 2 startów, dostaje tutaj.

84
00:03:53,750 --> 00:03:56,310
To zależy od silni 1.

85
00:03:56,310 --> 00:03:57,430
Silnia 1 startów.

86
00:03:57,430 --> 00:03:57,650
>> OK.

87
00:03:57,650 --> 00:03:59,775
Więc teraz, że jesteśmy coraz
gdzieś ciekawe, prawda?

88
00:03:59,775 --> 00:04:02,190
Teraz, 1 oznacza liczbę 1.

89
00:04:02,190 --> 00:04:05,130
I tak wracamy 1.

90
00:04:05,130 --> 00:04:06,770
W tym momencie wracamy.

91
00:04:06,770 --> 00:04:07,880
Funkcja zrobić.

92
00:04:07,880 --> 00:04:11,140
To zachowanie jest-- tam
nic innego nie robić,

93
00:04:11,140 --> 00:04:17,006
i tak ramka stosu dla
silnia 1 pojawia się.

94
00:04:17,006 --> 00:04:17,589
Jest skonczone.

95
00:04:17,589 --> 00:04:19,480
Powrócił 1.

96
00:04:19,480 --> 00:04:23,370
A teraz, silnia 2, które
Rama była natychmiast pod nim

97
00:04:23,370 --> 00:04:26,160
w stosie, staje się aktywnym ramki.

98
00:04:26,160 --> 00:04:29,030
>> I może odebrać
dokładnie, w którym zostało przerwane.

99
00:04:29,030 --> 00:04:32,240
To już czeka na silni
od 1 do zakończenia prac.

100
00:04:32,240 --> 00:04:33,610
Obecnie zakończył.

101
00:04:33,610 --> 00:04:35,510
I tak oto jesteśmy.

102
00:04:35,510 --> 00:04:38,080
>> Silnia 1 wrócił wartość 1.

103
00:04:38,080 --> 00:04:42,430
Więc silnia 2 puszki
powiedzmy powrócić 2 razy 1.

104
00:04:42,430 --> 00:04:43,680
Jej praca jest teraz zrobić.

105
00:04:43,680 --> 00:04:49,110
To zwróciło 2 do czynnikowych
3, który czekał na niego.

106
00:04:49,110 --> 00:04:53,370
Silnia 3 jest górna ramka,
aktywna ramka w stosie.

107
00:04:53,370 --> 00:04:58,617
I tak to się mówi, dobrze, dobrze, będę
powrót 3 razy 2, który jest 6.

108
00:04:58,617 --> 00:05:00,700
I mam zamiar dać, że
wartość z powrotem do silnia

109
00:05:00,700 --> 00:05:03,430
4, który został na mnie czeka.

110
00:05:03,430 --> 00:05:04,500
Mam dość.

111
00:05:04,500 --> 00:05:09,410
Silnia 3 schodzi ze stosu, a
silnia 4 jest teraz aktywna ramka.

112
00:05:09,410 --> 00:05:13,510
>> 4 mówi, OK, mam zamiar wrócić 4 razy
silnia 3, co było sześć.

113
00:05:13,510 --> 00:05:15,980
To było od wartości, które
silnia 3 wrócił.

114
00:05:15,980 --> 00:05:19,010
I tak 4 razy 6 jest 24.

115
00:05:19,010 --> 00:05:20,990
I mam zamiar przejść
że powrót do czynnikowych

116
00:05:20,990 --> 00:05:23,160
5, który został na mnie czeka.

117
00:05:23,160 --> 00:05:25,270
Silnia 5 jest teraz aktywna ramka.

118
00:05:25,270 --> 00:05:30,700
To będzie powrót 5 razy
silnia 4-- 5 razy 24 lub 120--

119
00:05:30,700 --> 00:05:32,722
i podać tę wartość
Powrót do głównej, która ma

120
00:05:32,722 --> 00:05:35,680
czekali cierpliwie dla
długi czas na dole stosu.

121
00:05:35,680 --> 00:05:36,640
>> To gdzie to się zaczęło.

122
00:05:36,640 --> 00:05:37,670
Wykonana jest to wezwanie.

123
00:05:37,670 --> 00:05:39,400
Kilka ramek przejął na górze.

124
00:05:39,400 --> 00:05:41,890
Jest teraz z powrotem w górnej części stosu.

125
00:05:41,890 --> 00:05:43,450
Jest to aktywna ramka.

126
00:05:43,450 --> 00:05:47,810
Tak więc głównym ma wartość 120
z powrotem z silni 5.

127
00:05:47,810 --> 00:05:50,750
To już czeka na
wydrukować tę wartość.

128
00:05:50,750 --> 00:05:51,657
I wtedy to się robi.

129
00:05:51,657 --> 00:05:53,240
Nie ma więcej linii kodu w głównym.

130
00:05:53,240 --> 00:05:56,800
Tak więc głównym pojawi się ramka użytkownika
stos, i gotowe.

131
00:05:56,800 --> 00:05:58,992
>> I to jest, jak działa rekurencji.

132
00:05:58,992 --> 00:06:00,200
Tak właśnie działa ramki stosu.

133
00:06:00,200 --> 00:06:03,120
Te wywołania funkcji
to się stało wcześniej

134
00:06:03,120 --> 00:06:06,620
to tylko na przerwie czeka
dla kolejnych połączeń

135
00:06:06,620 --> 00:06:12,050
do końca, dzięki czemu stają się one aktywne
kadrowanie i dokończyć to, co trzeba zrobić.

136
00:06:12,050 --> 00:06:13,060
>> Jestem Doug Lloyd.

137
00:06:13,060 --> 00:06:14,880
To CS50.

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