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

2
00:00:05,587 --> 00:00:07,670
DOUG Lloyd: Jos olet nähnyt
video rekursio,

3
00:00:07,670 --> 00:00:10,170
koko prosessi voi olla
tuntui hieman maaginen.

4
00:00:10,170 --> 00:00:10,930
Kuinka se toimii?

5
00:00:10,930 --> 00:00:15,010
Miten toiminnot tietävät, että he
täytyy odottaa ja odottaa toista arvo

6
00:00:15,010 --> 00:00:19,150
palata eri toimintoa
soittaa saadakseen tuloksen haluamme?

7
00:00:19,150 --> 00:00:22,550
>> No, syy tämä toimii, koska
jotain tunnetaan kutsupino.

8
00:00:22,550 --> 00:00:26,360
Kun soitat toiminto,
järjestelmä kumoaa muistitilaa

9
00:00:26,360 --> 00:00:28,120
että toiminto tehdä työnsä.

10
00:00:28,120 --> 00:00:31,720
Ja me kutsumme näitä paloina muistin
ollaan varattu kunkin toiminnon

11
00:00:31,720 --> 00:00:35,670
soittaa pinokehys tai toiminnon kehys.

12
00:00:35,670 --> 00:00:38,290
Ja kuten arvata saattaa,
nämä pino kehyksiä

13
00:00:38,290 --> 00:00:41,000
elää pino osa muistia.

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

15
00:00:43,960 --> 00:00:47,540
>> Useampia toimintoja pinokehys
voi esiintyä muistiin tiettynä aikana.

16
00:00:47,540 --> 00:00:51,240
Jos tärkein kutsuu funktiota liikkua,
ja liikkua kehottaa suuntaan,

17
00:00:51,240 --> 00:00:54,460
Kaikkien kolmen toiminnon on auki kehyksiä.

18
00:00:54,460 --> 00:00:57,350
Mutta kaikki eivät ole aktiivisia kehyksiä.

19
00:00:57,350 --> 00:00:59,410
Nämä kehykset on järjestetty pinoon.

20
00:00:59,410 --> 00:01:01,820
Ja kehyksen
viimeksi soittanut

21
00:01:01,820 --> 00:01:04,390
toiminto on aina päällä pinon.

22
00:01:04,390 --> 00:01:07,150
Ja että on aina aktiivinen kehys.

23
00:01:07,150 --> 00:01:10,420
On vain todella koskaan yksi
toiminto se aktiivinen kerrallaan.

24
00:01:10,420 --> 00:01:12,420
Se on päällekkäin pinon.

25
00:01:12,420 --> 00:01:17,620
>> Kun toiminto kutsuu toista
toiminto, se tavallaan painaa tauko.

26
00:01:17,620 --> 00:01:20,590
Se tavallaan on pidossa, odottamassa.

27
00:01:20,590 --> 00:01:24,050
Ja toinen pinokehys työnnetään
pinoon sen päälle.

28
00:01:24,050 --> 00:01:26,150
Ja että tulee aktiivinen kehys.

29
00:01:26,150 --> 00:01:28,600
Ja runko heti
alla se tarvitsee odottaa

30
00:01:28,600 --> 00:01:33,560
kunnes se on jälleen aktiivinen kehys
ennen kuin se voi jatkaa työtään.

31
00:01:33,560 --> 00:01:35,870
Kun toiminto on
täydellinen ja se on tehty,

32
00:01:35,870 --> 00:01:37,720
sen runko on piipahti pinosta.

33
00:01:37,720 --> 00:01:38,950
Se on terminologiaa.

34
00:01:38,950 --> 00:01:41,110
Ja runko heti
sen alla, kuten juuri sanoin,

35
00:01:41,110 --> 00:01:42,880
tulee uusi aktiivinen kehys.

36
00:01:42,880 --> 00:01:45,960
>> Ja jos se kutsuu toisen toiminnon,
se tulee keskeyttää uudelleen.

37
00:01:45,960 --> 00:01:49,290
Tämä uusi toiminto n pinon kehys
työnnetään päällimmäinen.

38
00:01:49,290 --> 00:01:50,650
Se tulee tehdä työnsä.

39
00:01:50,650 --> 00:01:52,100
Se voi pop takaisin pois.

40
00:01:52,100 --> 00:01:55,630
Ja muut toiminto
alla se voi jatkaa uudelleen.

41
00:01:55,630 --> 00:02:00,080
>> Joten mennään läpi tätä uudelleen, etsivät
klo ajatus factorial toiminto

42
00:02:00,080 --> 00:02:03,070
että me määritelty
rekursio videon nähdä

43
00:02:03,070 --> 00:02:07,770
miten taika takana
rekursiivinen prosessi on käynnissä.

44
00:02:07,770 --> 00:02:09,870
Joten tämä on meidän koko tiedosto, eikö?

45
00:02:09,870 --> 00:02:14,000
Me määritelty kaksi
functions-- tärkein ja tosiasia.

46
00:02:14,000 --> 00:02:15,980
Ja kuten voisi odottaa,
kaikki C-ohjelma on menossa

47
00:02:15,980 --> 00:02:18,470
alkamaan ensimmäisellä rivillä tärkein.

48
00:02:18,470 --> 00:02:21,660
>> Joten luomme uuden pinon kehyksen tärkein.

49
00:02:21,660 --> 00:02:23,320
Ja se tulee alkavat näkyä.

50
00:02:23,320 --> 00:02:25,270
Tärkeimmät puhelut printf.

51
00:02:25,270 --> 00:02:29,390
Ja printf on menossa
tulostaa kertoma 5.

52
00:02:29,390 --> 00:02:31,440
Hyvin, se ei tiedä
mitä kertoma 5 on,

53
00:02:31,440 --> 00:02:35,620
ja niin tämä puhelu on jo
riippuen toisen toiminnon puhelu.

54
00:02:35,620 --> 00:02:37,270
Joten tärkein aikoo keskeyttää oikeassa.

55
00:02:37,270 --> 00:02:39,103
Aion jättää sen
nuoli oikeassa, väri

56
00:02:39,103 --> 00:02:41,360
se samanvärinen kuin
pinokehys oikealla,

57
00:02:41,360 --> 00:02:47,720
osoittamaan, että tärkein aikoo jäädyttää
täällä taas kertoma 5 kutsutaan.

58
00:02:47,720 --> 00:02:49,300
>> Joten kertoma 5 kutsutaan.

59
00:02:49,300 --> 00:02:53,160
Ja se tulee aloittaa hyvin
alussa kertoma toiminnon.

60
00:02:53,160 --> 00:02:55,440
Se esittää kysymyksen olen yhtä suuri kuin 1?

61
00:02:55,440 --> 00:02:56,810
On 5 yhtä suuri kuin 1?

62
00:02:56,810 --> 00:02:57,410
No, ei.

63
00:02:57,410 --> 00:03:01,110
Joten se tulee mennä alas
muu osa, paluu n kertaa

64
00:03:01,110 --> 00:03:02,990
kertoma n miinus 1.

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

66
00:03:03,490 --> 00:03:07,070
>> Joten nyt, kertoma 5 on
riippuen toinen puhelu

67
00:03:07,070 --> 00:03:09,740
ja Kertoma, kulkee
4 kuten parametri.

68
00:03:09,740 --> 00:03:14,210
Ja niin kertoma
5 runko, että punainen kehys,

69
00:03:14,210 --> 00:03:17,160
aikoo jäädyttää oikeassa
tuohon linja olen ilmoittanut

70
00:03:17,160 --> 00:03:21,914
ja odottaa kertoma 4 loppuun
mitä se tarvitsee tehdä niin, että se

71
00:03:21,914 --> 00:03:23,330
voi tulla aktiivisen kehyksen uudelleen.

72
00:03:23,330 --> 00:03:26,890
>> Joten kertoma 4 alkaa klo
alussa kertoma.

73
00:03:26,890 --> 00:03:28,556
On 4 yhtä suuri kuin 1?

74
00:03:28,556 --> 00:03:30,180
Ei, niin se tulee tehdä sama asia.

75
00:03:30,180 --> 00:03:31,590
Se tulee alas muuta haara.

76
00:03:31,590 --> 00:03:33,240
Se tulee päästä Koodirivin.

77
00:03:33,240 --> 00:03:35,710
OK, aion palata neljä kertaa.

78
00:03:35,710 --> 00:03:41,270
Voi, kertoma on 3-- niin faktoria
4 riippuu kertoma 3 viimeistely.

79
00:03:41,270 --> 00:03:43,055
>> Ja niin se tarvitsee soittaa kertoma 3.

80
00:03:43,055 --> 00:03:45,180
Ja joka on menossa läpi
saman prosessin uudelleen.

81
00:03:45,180 --> 00:03:48,200
Se alkaa kautta, tulee tänne.

82
00:03:48,200 --> 00:03:50,980
Kertoma 3 riippuu
on kertoman 1.

83
00:03:50,980 --> 00:03:53,750
Joten kertoma 2 alkaa, tulee tänne.

84
00:03:53,750 --> 00:03:56,310
Se riippuu kertoma 1.

85
00:03:56,310 --> 00:03:57,430
Kertoman 1 alkaa.

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

87
00:03:57,650 --> 00:03:59,775
Joten nyt, olemme pääsemässä
jonnekin mielenkiintoinen, eikö?

88
00:03:59,775 --> 00:04:02,190
Joten nyt, 1 on yhtä kuin 1.

89
00:04:02,190 --> 00:04:05,130
Ja niin palaamme 1.

90
00:04:05,130 --> 00:04:06,770
Tässä vaiheessa olemme palaamassa.

91
00:04:06,770 --> 00:04:07,880
Toiminto on tehty.

92
00:04:07,880 --> 00:04:11,140
Se käyttäytyminen is-- siellä
mitään muuta sitä tehdä,

93
00:04:11,140 --> 00:04:17,006
ja niin pino runko
kertoma 1 irtoaa.

94
00:04:17,006 --> 00:04:17,589
Se on valmis.

95
00:04:17,589 --> 00:04:19,480
Se palautti 1.

96
00:04:19,480 --> 00:04:23,370
Ja nyt, kertoma 2, joka
oli kehys sen alapuolella

97
00:04:23,370 --> 00:04:26,160
pinossa, tulee aktiivinen kehys.

98
00:04:26,160 --> 00:04:29,030
>> Ja se voi poimia
tarkalleen, mihin se jäi.

99
00:04:29,030 --> 00:04:32,240
Se on odottanut factorial
1 loppuun työnsä.

100
00:04:32,240 --> 00:04:33,610
Se on nyt valmis.

101
00:04:33,610 --> 00:04:35,510
Ja niin tässä ollaan.

102
00:04:35,510 --> 00:04:38,080
>> Kertoma 1 palasi arvo 1.

103
00:04:38,080 --> 00:04:42,430
Joten kertoma 2 CAN
vaikkapa palata 2 kertaa 1.

104
00:04:42,430 --> 00:04:43,680
Sen työ on nyt tehty.

105
00:04:43,680 --> 00:04:49,110
Se palasi 2 Factorial
3, joka odotti sitä.

106
00:04:49,110 --> 00:04:53,370
Kertoma 3 on nyt yläkehyksen,
aktiivinen kehys pinossa.

107
00:04:53,370 --> 00:04:58,617
Ja niin se sanoo, OK, hyvin, aion
palata 3 kertaa 2, joka on 6.

108
00:04:58,617 --> 00:05:00,700
Ja aion antaa siitä, että
arvostavat takaisin kertoma

109
00:05:00,700 --> 00:05:03,430
4, joka on odottanut minua.

110
00:05:03,430 --> 00:05:04,500
Minulle riitti.

111
00:05:04,500 --> 00:05:09,410
Kertoma 3 irtoaa pinon, ja
kertoma 4 on nyt aktiivinen kehys.

112
00:05:09,410 --> 00:05:13,510
>> 4 sanoo, OK, aion palata 4 kertaa
kertoma 3, mikä oli kuusi.

113
00:05:13,510 --> 00:05:15,980
Se oli arvo
kertoma 3 palasi.

114
00:05:15,980 --> 00:05:19,010
Ja niin 4 kertaa 6 on 24.

115
00:05:19,010 --> 00:05:20,990
Ja aion siirtää
että takaisin Factorial

116
00:05:20,990 --> 00:05:23,160
5, joka on odottanut minua.

117
00:05:23,160 --> 00:05:25,270
Kertoma 5 on nyt aktiivinen kehys.

118
00:05:25,270 --> 00:05:30,700
Se tulee palauttaa 5 kertaa
kertoma on 4-- 5 kertaa 24, tai 120--

119
00:05:30,700 --> 00:05:32,722
ja antaa siitä, että arvo
Takaisin, joka on

120
00:05:32,722 --> 00:05:35,680
odottanut erittäin kärsivällisesti
Kauan alareunassa pinon.

121
00:05:35,680 --> 00:05:36,640
>> Siellä se alkoi.

122
00:05:36,640 --> 00:05:37,670
Se teki tämän puhelun.

123
00:05:37,670 --> 00:05:39,400
Useat kehykset otti yläreunassa.

124
00:05:39,400 --> 00:05:41,890
Nyt takaisin pinon.

125
00:05:41,890 --> 00:05:43,450
Se on aktiivinen kehys.

126
00:05:43,450 --> 00:05:47,810
Joten tärkein sai arvon 120
takaisin kertoma 5.

127
00:05:47,810 --> 00:05:50,750
Se odottanut
tulostaa että arvo.

128
00:05:50,750 --> 00:05:51,657
Ja sitten se on tehty.

129
00:05:51,657 --> 00:05:53,240
Ei ole enää riviä koodia tärkein.

130
00:05:53,240 --> 00:05:56,800
Joten tärkein runko ponnahtaa pois
pino, ja olemme tehneet.

131
00:05:56,800 --> 00:05:58,992
>> Ja siitä rekursio toimii.

132
00:05:58,992 --> 00:06:00,200
Näin pino kehyksiä toimivat.

133
00:06:00,200 --> 00:06:03,120
Ne funktiokutsut
joka tapahtui aiemmin

134
00:06:03,120 --> 00:06:06,620
ovat juuri tauko, odottaa
annettavasta puhelut

135
00:06:06,620 --> 00:06:12,050
loppuun jotta he voivat tulla aktiivinen
runko ja lopuksi mitä he tarvitsevat.

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

137
00:06:13,060 --> 00:06:14,880
Tämä on CS50.

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