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

2
00:00:05,587 --> 00:00:07,670
DOUG LLOYD: Hvis du har sett
videoen på rekursjon,

3
00:00:07,670 --> 00:00:10,170
hele prosessen kan ha
virket litt magisk.

4
00:00:10,170 --> 00:00:10,930
Hvordan fungerer det?

5
00:00:10,930 --> 00:00:15,010
Hvordan vet de funksjonene vet at de
må vente og vente på en annen verdi

6
00:00:15,010 --> 00:00:19,150
å returnere fra en annen funksjon
ringe for å få det resultatet vi ønsker?

7
00:00:19,150 --> 00:00:22,550
>> Vel, er årsaken til at dette fungerer fordi
av noe som kalles anrops stabelen.

8
00:00:22,550 --> 00:00:26,360
Når du ringer en funksjon,
Systemet setter til side plass i minnet

9
00:00:26,360 --> 00:00:28,120
for at funksjonen for å gjøre sitt arbeid.

10
00:00:28,120 --> 00:00:31,720
Og vi kaller disse biter av minnet som
blir satt til side for hver funksjon

11
00:00:31,720 --> 00:00:35,670
kalle en stabel ramme eller en funksjon ramme.

12
00:00:35,670 --> 00:00:38,290
Og som du kanskje forventer,
disse stakkrammer

13
00:00:38,290 --> 00:00:41,000
leve på stakken delen av minnet.

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

15
00:00:43,960 --> 00:00:47,540
>> Mer enn én funksjon takken
kan eksistere i minnet på et gitt tidspunkt.

16
00:00:47,540 --> 00:00:51,240
Hvis hoved kaller en funksjon flytte,
og flytte samtaler retning,

17
00:00:51,240 --> 00:00:54,460
alle tre funksjonene har åpne rammer.

18
00:00:54,460 --> 00:00:57,350
Men ikke alle har aktive rammer.

19
00:00:57,350 --> 00:00:59,410
Disse rammene er ordnet i en stabel.

20
00:00:59,410 --> 00:01:01,820
Og rammen fra
ringt

21
00:01:01,820 --> 00:01:04,390
Funksjonen er alltid på toppen av bunken.

22
00:01:04,390 --> 00:01:07,150
Og det er alltid den aktive rammen.

23
00:01:07,150 --> 00:01:10,420
Det er egentlig bare noen gang en
funksjon som er aktiv om gangen.

24
00:01:10,420 --> 00:01:12,420
Det er den ene på toppen av bunken.

25
00:01:12,420 --> 00:01:17,620
>> Når en funksjon kaller en annen
funksjon, det liksom presser pause.

26
00:01:17,620 --> 00:01:20,590
Det er liksom på vent, venter.

27
00:01:20,590 --> 00:01:24,050
Og en annen takken er skjøvet
på stakken på toppen av det.

28
00:01:24,050 --> 00:01:26,150
Og det blir den aktive rammen.

29
00:01:26,150 --> 00:01:28,600
Og rammen straks
under den trenger å vente

30
00:01:28,600 --> 00:01:33,560
inntil det er igjen den aktive rammen
før den kan gjenoppta sitt arbeid.

31
00:01:33,560 --> 00:01:35,870
Når en funksjon er
komplett og det er gjort,

32
00:01:35,870 --> 00:01:37,720
rammen er popped av stabelen.

33
00:01:37,720 --> 00:01:38,950
Det er terminologien.

34
00:01:38,950 --> 00:01:41,110
Og rammen straks
under den, som jeg nettopp sa,

35
00:01:41,110 --> 00:01:42,880
blir den nye aktive rammen.

36
00:01:42,880 --> 00:01:45,960
>> Og hvis den kaller en annen funksjon,
det kommer til å ta en pause igjen.

37
00:01:45,960 --> 00:01:49,290
Det nye funksjonen er takken vil
skyves på toppen av bunken.

38
00:01:49,290 --> 00:01:50,650
Det vil gjøre sitt arbeid.

39
00:01:50,650 --> 00:01:52,100
Det kan komme tilbake på.

40
00:01:52,100 --> 00:01:55,630
Og den andre funksjonen
Nedenfor kan fortsette igjen.

41
00:01:55,630 --> 00:02:00,080
>> Så la oss gå gjennom dette igjen, ser
ved tanken på fakultetet funksjon

42
00:02:00,080 --> 00:02:03,070
at vi definert i
rekursjon videoen for å se

43
00:02:03,070 --> 00:02:07,770
nøyaktig hvordan magien bak dette
rekursiv prosess pågår.

44
00:02:07,770 --> 00:02:09,870
Så dette er vår hele filen, ikke sant?

45
00:02:09,870 --> 00:02:14,000
Vi definert to
functions-- hoved og faktum.

46
00:02:14,000 --> 00:02:15,980
Og som vi kunne forvente,
noen C program kommer

47
00:02:15,980 --> 00:02:18,470
å starte på den første linjen i hoved.

48
00:02:18,470 --> 00:02:21,660
>> Så vi oppretter en ny takken for main.

49
00:02:21,660 --> 00:02:23,320
Og det kommer til å begynne å kjøre.

50
00:02:23,320 --> 00:02:25,270
Hoved samtaler printf.

51
00:02:25,270 --> 00:02:29,390
Og printf kommer til å
skrive ut fakultetet av fem.

52
00:02:29,390 --> 00:02:31,440
Vel, det vet ikke
hva fakultetet av fem er,

53
00:02:31,440 --> 00:02:35,620
og så denne samtalen er allerede
avhengig av en annen funksjon samtale.

54
00:02:35,620 --> 00:02:37,270
Så hoved kommer til å ta en pause der.

55
00:02:37,270 --> 00:02:39,103
Jeg skal forlate sin
pil rett der, farge

56
00:02:39,103 --> 00:02:41,360
det samme farge som
stable rammen til høyre,

57
00:02:41,360 --> 00:02:47,720
for å vise at hoved kommer til å fryse
her mens fakultetet av fem kalles.

58
00:02:47,720 --> 00:02:49,300
>> Så fakultetet av fem kalles.

59
00:02:49,300 --> 00:02:53,160
Og det kommer til å starte helt på
begynnelsen av fakultetet funksjonen.

60
00:02:53,160 --> 00:02:55,440
Det stiller spørsmålet jeg lik en?

61
00:02:55,440 --> 00:02:56,810
Er fem lik 1?

62
00:02:56,810 --> 00:02:57,410
Vel, nei.

63
00:02:57,410 --> 00:03:01,110
Så det kommer til å gå ned til
den andre delen, retur n ganger

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

65
00:03:02,990 --> 00:03:03,490
Vel, ok.

66
00:03:03,490 --> 00:03:07,070
>> Så nå, er fakultetet av 5
avhengig av en annen samtale

67
00:03:07,070 --> 00:03:09,740
til fakultetet, passerer
i 4 som parameter.

68
00:03:09,740 --> 00:03:14,210
Og så fakultetet av
5 ramme, som rød ramme,

69
00:03:14,210 --> 00:03:17,160
kommer til å fryse der
på den linjen jeg har indikert

70
00:03:17,160 --> 00:03:21,914
og vente på fakultetet av fire til slutt
hva den trenger å gjøre, slik at da er det

71
00:03:21,914 --> 00:03:23,330
kan bli den aktive rammen igjen.

72
00:03:23,330 --> 00:03:26,890
>> Så fakultetet av 4 starter ved
I begynnelsen av fakultetet.

73
00:03:26,890 --> 00:03:28,556
4 er lik 1?

74
00:03:28,556 --> 00:03:30,180
Nei, så det kommer til å gjøre det samme.

75
00:03:30,180 --> 00:03:31,590
Det kommer til å gå ned den andre grenen.

76
00:03:31,590 --> 00:03:33,240
Det kommer til å komme til det kodelinje.

77
00:03:33,240 --> 00:03:35,710
OK, jeg kommer til å gå tilbake fire ganger.

78
00:03:35,710 --> 00:03:41,270
Oh, fakultetet av 3-- så Fakultet for
4 avhenger av fakultetet av tre etterbehandling.

79
00:03:41,270 --> 00:03:43,055
>> Og så den trenger å ringe fakultetet av tre.

80
00:03:43,055 --> 00:03:45,180
Og det kommer til å gå gjennom
den samme prosessen på nytt.

81
00:03:45,180 --> 00:03:48,200
Det begynner gjennom, får her.

82
00:03:48,200 --> 00:03:50,980
Fakultetet av tre avhenger
på fakultetet av en.

83
00:03:50,980 --> 00:03:53,750
Så fakultetet av 2 starter, får her.

84
00:03:53,750 --> 00:03:56,310
Det avhenger av fakultetet av en.

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

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

87
00:03:57,650 --> 00:03:59,775
Så nå, vi får
et interessant sted, ikke sant?

88
00:03:59,775 --> 00:04:02,190
Så nå, er en lik en.

89
00:04:02,190 --> 00:04:05,130
Og så vi kommer tilbake en.

90
00:04:05,130 --> 00:04:06,770
På dette punktet, er vi tilbake.

91
00:04:06,770 --> 00:04:07,880
Funksjonen er gjort.

92
00:04:07,880 --> 00:04:11,140
Det er atferd er-- det er
ingenting annet for at den skal gjøre,

93
00:04:11,140 --> 00:04:17,006
og så takken for
fakultetet av en spretter av.

94
00:04:17,006 --> 00:04:17,589
Det er ferdig.

95
00:04:17,589 --> 00:04:19,480
Det returnert en.

96
00:04:19,480 --> 00:04:23,370
Og nå, fakultetet av 2, som
var rammen umiddelbart under det

97
00:04:23,370 --> 00:04:26,160
i stabelen, blir den aktive rammen.

98
00:04:26,160 --> 00:04:29,030
>> Og det kan plukke opp
akkurat der den slapp.

99
00:04:29,030 --> 00:04:32,240
Det er ventet på et fakultet
av en til slutt sitt arbeid.

100
00:04:32,240 --> 00:04:33,610
Det er nå ferdig.

101
00:04:33,610 --> 00:04:35,510
Og så er vi her.

102
00:04:35,510 --> 00:04:38,080
>> Fakultetet av en returnerte verdien av en.

103
00:04:38,080 --> 00:04:42,430
Så fakultetet av 2 kan
si tilbake 2 ganger 1.

104
00:04:42,430 --> 00:04:43,680
Arbeidet er nå ferdig.

105
00:04:43,680 --> 00:04:49,110
Det har returnert to til fakultetet
av tre, som var ventet på det.

106
00:04:49,110 --> 00:04:53,370
Fakultetet av tre er nå den øverste rammen,
den aktive rammen i stabelen.

107
00:04:53,370 --> 00:04:58,617
Og så står det, OK, vel, jeg skal
å returnere 3 ganger 2, som er seks.

108
00:04:58,617 --> 00:05:00,700
Og jeg kommer til å gi den
verds tilbake til fakultetet

109
00:05:00,700 --> 00:05:03,430
av 4, har som ventet på meg.

110
00:05:03,430 --> 00:05:04,500
Jeg er ferdig.

111
00:05:04,500 --> 00:05:09,410
Fakultetet av tre spretter av stabelen, og
fakultetet av 4 er nå den aktive rammen.

112
00:05:09,410 --> 00:05:13,510
>> 4 sier, OK, jeg kommer til å gå tilbake 4 ganger
fakultetet av tre, som var seks.

113
00:05:13,510 --> 00:05:15,980
Som var av verdi som
fakultetet av tre returnert.

114
00:05:15,980 --> 00:05:19,010
Og så 4 ganger 6 er 24.

115
00:05:19,010 --> 00:05:20,990
Og jeg kommer til å passere
det tilbake til fakultetet

116
00:05:20,990 --> 00:05:23,160
av fem, har som ventet på meg.

117
00:05:23,160 --> 00:05:25,270
Fakultetet av fem er nå den aktive rammen.

118
00:05:25,270 --> 00:05:30,700
Det kommer til å gå tilbake 5 ganger
fakultetet av 4-- 5 ganger 24, eller 120--

119
00:05:30,700 --> 00:05:32,722
og gi den verdien
tilbake til hovedsiden, som har

120
00:05:32,722 --> 00:05:35,680
ventet veldig tålmodig på en
lang tid i bunnen av stabelen.

121
00:05:35,680 --> 00:05:36,640
>> Det er der den startet.

122
00:05:36,640 --> 00:05:37,670
Det gjorde denne samtalen.

123
00:05:37,670 --> 00:05:39,400
Flere rammer overtok på toppen.

124
00:05:39,400 --> 00:05:41,890
Det er nå tilbake på toppen av bunken.

125
00:05:41,890 --> 00:05:43,450
Det er den aktive rammen.

126
00:05:43,450 --> 00:05:47,810
Så hoved fikk verdien 120
tilbake fra fakultetet av fem.

127
00:05:47,810 --> 00:05:50,750
Det har vært ventet å
skrive ut denne verdien.

128
00:05:50,750 --> 00:05:51,657
Og så er det gjort.

129
00:05:51,657 --> 00:05:53,240
Det er ingen flere linjer med kode i main.

130
00:05:53,240 --> 00:05:56,800
Så hoved ramme spretter av
stabelen, og vi er ferdige.

131
00:05:56,800 --> 00:05:58,992
>> Og det er hvordan rekursjon fungerer.

132
00:05:58,992 --> 00:06:00,200
Det er slik stack rammer fungere.

133
00:06:00,200 --> 00:06:03,120
Disse funksjonskall
som skjedde tidligere

134
00:06:03,120 --> 00:06:06,620
er bare på pause, venter
for de påfølgende samtaler

135
00:06:06,620 --> 00:06:12,050
til slutt slik at de kan bli virke
ramme og fullføre det de må gjøre.

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

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

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