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

2
00:00:05,587 --> 00:00:07,670
DOUG LLOYD: Om du har sett
videon på rekursion,

3
00:00:07,670 --> 00:00:10,170
hela processen kan ha
verkade lite magiskt.

4
00:00:10,170 --> 00:00:10,930
Hur fungerar det?

5
00:00:10,930 --> 00:00:15,010
Hur vet funktionerna vet att de
måste vänta och vänta på ett annat värde

6
00:00:15,010 --> 00:00:19,150
att återvända från en annan funktion
ringa för att få det resultat vi vill ha?

7
00:00:19,150 --> 00:00:22,550
>> Tja, är orsaken det fungerar eftersom
av något som kallas anropsstacken.

8
00:00:22,550 --> 00:00:26,360
När du ringer en funktion,
systemet upphäver utrymme i minnet

9
00:00:26,360 --> 00:00:28,120
för denna funktion att göra sitt arbete.

10
00:00:28,120 --> 00:00:31,720
Och vi kallar dessa bitar av minne som
är avsätts för varje funktion

11
00:00:31,720 --> 00:00:35,670
ringa en stapel ram eller en funktion ram.

12
00:00:35,670 --> 00:00:38,290
Och som man kan förvänta sig,
dessa stapelramar

13
00:00:38,290 --> 00:00:41,000
lever på stacken del av minnet.

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

15
00:00:43,960 --> 00:00:47,540
>> Mer än en funktion stack ram
kan existera i minnet vid en given tidpunkt.

16
00:00:47,540 --> 00:00:51,240
Om huvud anropar en funktion flytta,
och flytta samtal riktning,

17
00:00:51,240 --> 00:00:54,460
alla tre funktionerna har öppna ramar.

18
00:00:54,460 --> 00:00:57,350
Men de har inte alla har aktiva ramar.

19
00:00:57,350 --> 00:00:59,410
Dessa ramar är anordnade i en stapel.

20
00:00:59,410 --> 00:01:01,820
Och ramen från
senast kallade

21
00:01:01,820 --> 00:01:04,390
funktion är alltid på toppen av stacken.

22
00:01:04,390 --> 00:01:07,150
Och det är alltid den aktiva ramen.

23
00:01:07,150 --> 00:01:10,420
Det finns egentligen bara någonsin en
funktion som är aktiv åt gången.

24
00:01:10,420 --> 00:01:12,420
Det är den en på toppen av stacken.

25
00:01:12,420 --> 00:01:17,620
>> När en funktion anropar en annan
funktion, typ av pressar det paus.

26
00:01:17,620 --> 00:01:20,590
Det är typ av på is, väntar.

27
00:01:20,590 --> 00:01:24,050
Och en annan stapel ramen skjuts
på stacken ovanpå den.

28
00:01:24,050 --> 00:01:26,150
Och det blir den aktiva ramen.

29
00:01:26,150 --> 00:01:28,600
Och ramen omedelbart
nedan den behöver vänta

30
00:01:28,600 --> 00:01:33,560
tills det återigen är den aktiva ramen
innan den kan återuppta sitt arbete.

31
00:01:33,560 --> 00:01:35,870
När en funktion är
fullständig och det är gjort,

32
00:01:35,870 --> 00:01:37,720
dess ram fälls av stapeln.

33
00:01:37,720 --> 00:01:38,950
Det är terminologin.

34
00:01:38,950 --> 00:01:41,110
Och ramen omedelbart
under det, som jag nyss sagt,

35
00:01:41,110 --> 00:01:42,880
blir ny aktiv ram.

36
00:01:42,880 --> 00:01:45,960
>> Och om den anropar en annan funktion,
det kommer att göra en paus igen.

37
00:01:45,960 --> 00:01:49,290
Den nya funktionen stack ram
skjutas på toppen av stacken.

38
00:01:49,290 --> 00:01:50,650
Det kommer att göra sitt arbete.

39
00:01:50,650 --> 00:01:52,100
Det kan pop tillbaka ut.

40
00:01:52,100 --> 00:01:55,630
Och den andra funktionen
Nedan kan återupptas igen.

41
00:01:55,630 --> 00:02:00,080
>> Så låt oss gå igenom det här igen, ser
vid tanken på fakulteten funktion

42
00:02:00,080 --> 00:02:03,070
att vi definierat i
rekursion video för att se

43
00:02:03,070 --> 00:02:07,770
exakt hur magin bakom detta
rekursiv process äger rum.

44
00:02:07,770 --> 00:02:09,870
Så detta är hela vår fil, eller hur?

45
00:02:09,870 --> 00:02:14,000
Vi definierade två
functions-- huvud och faktum.

46
00:02:14,000 --> 00:02:15,980
Och som vi kan förvänta sig,
någon C-programmet går

47
00:02:15,980 --> 00:02:18,470
att börja på den första raden i huvud.

48
00:02:18,470 --> 00:02:21,660
>> Så skapar vi en ny bunt ram för main.

49
00:02:21,660 --> 00:02:23,320
Och det kommer att börja visas.

50
00:02:23,320 --> 00:02:25,270
Huvudsakliga samtal printf.

51
00:02:25,270 --> 00:02:29,390
Och printf kommer att
skriva ut fakulteten av 5.

52
00:02:29,390 --> 00:02:31,440
Tja, inte vet
vad fakulteten av 5 är,

53
00:02:31,440 --> 00:02:35,620
och så denna inbjudan är redan
beroende på en annan funktionsanrop.

54
00:02:35,620 --> 00:02:37,270
Så huvud kommer att pausa direkt.

55
00:02:37,270 --> 00:02:39,103
Jag ska lämna sin
pil just där, färg

56
00:02:39,103 --> 00:02:41,360
det har samma färg som den
stack ram på höger,

57
00:02:41,360 --> 00:02:47,720
för att indikera att huvud kommer att frysa
här medan fakulteten av 5 heter.

58
00:02:47,720 --> 00:02:49,300
>> Så fakulteten av 5 heter.

59
00:02:49,300 --> 00:02:53,160
Och det kommer att börja på mycket
början av fakulteten.

60
00:02:53,160 --> 00:02:55,440
Det ställer frågan jag lika med 1?

61
00:02:55,440 --> 00:02:56,810
Är 5 lika med 1?

62
00:02:56,810 --> 00:02:57,410
Tja, nej.

63
00:02:57,410 --> 00:03:01,110
Så det kommer att gå ner till
else delen retur n gånger

64
00:03:01,110 --> 00:03:02,990
fakulteten av n minus en.

65
00:03:02,990 --> 00:03:03,490
Okej då.

66
00:03:03,490 --> 00:03:07,070
>> Så nu är fakulteten av 5
beroende på ett annat samtal

67
00:03:07,070 --> 00:03:09,740
att faktoriella, passerar
i 4 som parameter.

68
00:03:09,740 --> 00:03:14,210
Och så fakulteten för
5 ram, som röd ram,

69
00:03:14,210 --> 00:03:17,160
kommer att frysa direkt
på den linje som jag har angett

70
00:03:17,160 --> 00:03:21,914
och vänta på fakulteten av 4 för att avsluta
vad den behöver för att göra så att då det

71
00:03:21,914 --> 00:03:23,330
kan bli den aktiva ramen igen.

72
00:03:23,330 --> 00:03:26,890
>> Så fakulteten av 4 börjar vid
början av faktoriell.

73
00:03:26,890 --> 00:03:28,556
Är 4 lika med 1?

74
00:03:28,556 --> 00:03:30,180
Nej, så det kommer att göra samma sak.

75
00:03:30,180 --> 00:03:31,590
Det kommer att gå ner i annat grenen.

76
00:03:31,590 --> 00:03:33,240
Det kommer att komma till den kodrad.

77
00:03:33,240 --> 00:03:35,710
OK, jag kommer att återvända fyra gånger.

78
00:03:35,710 --> 00:03:41,270
Åh, fakulteten för 3-- så fakulteten av
4 beror på fakulteten av 3 efterbehandling.

79
00:03:41,270 --> 00:03:43,055
>> Och så måste ringa fakulteten av 3.

80
00:03:43,055 --> 00:03:45,180
Och det är gonna gå igenom
samma process igen.

81
00:03:45,180 --> 00:03:48,200
Det börjar genom, kommer hit.

82
00:03:48,200 --> 00:03:50,980
Fakulteten av 3 beror
på fakulteten av 1.

83
00:03:50,980 --> 00:03:53,750
Så fakulteten av 2 startar, blir här.

84
00:03:53,750 --> 00:03:56,310
Det beror på fakulteten av ett.

85
00:03:56,310 --> 00:03:57,430
Fakultet av 1 starter.

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

87
00:03:57,650 --> 00:03:59,775
Så nu, vi får
någonstans intressant, eller hur?

88
00:03:59,775 --> 00:04:02,190
Så nu, ett är lika med 1.

89
00:04:02,190 --> 00:04:05,130
Och så vi tillbaka en.

90
00:04:05,130 --> 00:04:06,770
Vid det här laget är vi tillbaka.

91
00:04:06,770 --> 00:04:07,880
Funktionen är gjort.

92
00:04:07,880 --> 00:04:11,140
Det är beteendet är-- finns
ingenting annat för att det ska göra,

93
00:04:11,140 --> 00:04:17,006
och så stapeln ramen för
fakulteten av 1 dyker upp.

94
00:04:17,006 --> 00:04:17,589
Det är avslutat.

95
00:04:17,589 --> 00:04:19,480
Det återvände 1.

96
00:04:19,480 --> 00:04:23,370
Och nu, fakulteten av 2, som
var i ramen omedelbart nedanför det

97
00:04:23,370 --> 00:04:26,160
i stapeln, blir den aktiva ramen.

98
00:04:26,160 --> 00:04:29,030
>> Och det kan plocka upp
precis där den slutade.

99
00:04:29,030 --> 00:04:32,240
Det har väntat på en faktor
1 för att avsluta sitt arbete.

100
00:04:32,240 --> 00:04:33,610
Det har nu avslutats.

101
00:04:33,610 --> 00:04:35,510
Och så här är vi.

102
00:04:35,510 --> 00:04:38,080
>> Fakulteten av en return värdet 1.

103
00:04:38,080 --> 00:04:42,430
Så fakulteten av 2 burk
säg tillbaka 2 gånger 1.

104
00:04:42,430 --> 00:04:43,680
Dess arbete är nu klar.

105
00:04:43,680 --> 00:04:49,110
Det åter 2 faktor
3, som stod.

106
00:04:49,110 --> 00:04:53,370
Fakulteten av 3 är nu den övre ramen,
den aktiva ramen i stapeln.

107
00:04:53,370 --> 00:04:58,617
Och så säger, OK, ja, jag kommer
att återvända 3 gånger 2, vilket är sex.

108
00:04:58,617 --> 00:05:00,700
Och jag kommer att ge det
värderar tillbaka till fakulteten

109
00:05:00,700 --> 00:05:03,430
4, har som väntat på mig.

110
00:05:03,430 --> 00:05:04,500
Jag är färdig.

111
00:05:04,500 --> 00:05:09,410
Fakulteten av 3 poppar av stapeln, och
fakulteten av fyra är nu den aktiva ramen.

112
00:05:09,410 --> 00:05:13,510
>> 4 säger, OK, jag kommer att återvända 4 gånger
fakulteten av 3, vilket var sex.

113
00:05:13,510 --> 00:05:15,980
Det var av värde som
fakulteten av 3 returneras.

114
00:05:15,980 --> 00:05:19,010
Och så 4 gånger 6 är 24.

115
00:05:19,010 --> 00:05:20,990
Och jag kommer att passera
det tillbaka till faktor

116
00:05:20,990 --> 00:05:23,160
av 5, har som väntat på mig.

117
00:05:23,160 --> 00:05:25,270
Fakultet av 5 är nu den aktiva ramen.

118
00:05:25,270 --> 00:05:30,700
Det kommer att återvända 5 gånger
fakulteten av 4-- 5 gånger 24 eller 120--

119
00:05:30,700 --> 00:05:32,722
och ge det värdet
tillbaka till huvud, som har

120
00:05:32,722 --> 00:05:35,680
väntat mycket tålmodigt för
lång tid vid botten av stapeln.

121
00:05:35,680 --> 00:05:36,640
>> Det är där det började.

122
00:05:36,640 --> 00:05:37,670
Det gjorde denna uppmaning.

123
00:05:37,670 --> 00:05:39,400
Flera ramar tog över i toppen.

124
00:05:39,400 --> 00:05:41,890
Det är nu tillbaka på toppen av stacken.

125
00:05:41,890 --> 00:05:43,450
Det är den aktiva ramen.

126
00:05:43,450 --> 00:05:47,810
Så på got värdet 120
tillbaka från fakulteten av 5.

127
00:05:47,810 --> 00:05:50,750
Det har väntat på
skriva ut det värdet.

128
00:05:50,750 --> 00:05:51,657
Och då är det gjort.

129
00:05:51,657 --> 00:05:53,240
Det finns inga fler rader kod i main.

130
00:05:53,240 --> 00:05:56,800
Så huvud ram dyker upp
stacken, och vi är klara.

131
00:05:56,800 --> 00:05:58,992
>> Och det är hur rekursion fungerar.

132
00:05:58,992 --> 00:06:00,200
Det är hur stack ramar fungerar.

133
00:06:00,200 --> 00:06:03,120
Dessa funktionsanrop
som hände tidigare

134
00:06:03,120 --> 00:06:06,620
är bara på paus, väntar
för efterföljande anrop

135
00:06:06,620 --> 00:06:12,050
till slut så att de kan bli aktiva
rama in och avsluta vad de behöver göra.

136
00:06:12,050 --> 00:06:13,060
>> Jag är Doug Lloyd.

137
00:06:13,060 --> 00:06:14,880
Detta är CS50.

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