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

2
00:00:05,587 --> 00:00:07,670
Doug LLOYD: Ako ste vidjeli
video na rekurzije,

3
00:00:07,670 --> 00:00:10,170
cijeli proces bi mogao imati
činilo malo čarobno.

4
00:00:10,170 --> 00:00:10,930
Kako radi?

5
00:00:10,930 --> 00:00:15,010
Kako funkcionira znaju da su
morati čekati i čekati drugu vrijednost

6
00:00:15,010 --> 00:00:19,150
da se vrate iz različitih funkcija
poziv kako bi dobili rezultat koji želimo?

7
00:00:19,150 --> 00:00:22,550
>> Pa, razlog je zato što to radi
nešto poznat kao stog poziva.

8
00:00:22,550 --> 00:00:26,360
Kada pozovete funkciju,
Sustav izdvaja prostor u memoriji

9
00:00:26,360 --> 00:00:28,120
za tu funkciju raditi svoj posao.

10
00:00:28,120 --> 00:00:31,720
I mi zovemo ove komade memorije
se odvojeno za svaku funkciju

11
00:00:31,720 --> 00:00:35,670
pozvati okvir stog ili funkciju okvir.

12
00:00:35,670 --> 00:00:38,290
I kao što ste mogli očekivati,
ove stog okviri

13
00:00:38,290 --> 00:00:41,000
živjeti na stog dio memorije.

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

15
00:00:43,960 --> 00:00:47,540
>> Više od jednog funkcija stog okvira
može postojati u memoriju u određenom trenutku.

16
00:00:47,540 --> 00:00:51,240
Ako glavni naziva funkcija potez,
i potez naziva smjer,

17
00:00:51,240 --> 00:00:54,460
sve tri funkcije imaju otvorene okvire.

18
00:00:54,460 --> 00:00:57,350
Ali nisu svi nemaju aktivne okvire.

19
00:00:57,350 --> 00:00:59,410
Ti okviri su raspoređeni u stog.

20
00:00:59,410 --> 00:01:01,820
A okvir iz
nedavno uputili

21
00:01:01,820 --> 00:01:04,390
Funkcija je uvijek na vrhu snopa.

22
00:01:04,390 --> 00:01:07,150
A to je uvijek aktivan okvir.

23
00:01:07,150 --> 00:01:10,420
Postoji samo jedan doista ikada
funkcija koja je aktivna u isto vrijeme.

24
00:01:10,420 --> 00:01:12,420
To je jedan na vrhu snopa.

25
00:01:12,420 --> 00:01:17,620
>> Kada funkcija poziva drugu
funkcija, ona vrsta preše pauzu.

26
00:01:17,620 --> 00:01:20,590
To je vrsta na čekanju, čeka.

27
00:01:20,590 --> 00:01:24,050
I još hrpa okvir gurnula
na stog na vrhu.

28
00:01:24,050 --> 00:01:26,150
I to postaje aktivni okvir.

29
00:01:26,150 --> 00:01:28,600
A okvir odmah
nastavku treba čekati

30
00:01:28,600 --> 00:01:33,560
dok je ponovno aktivni okvir
prije nego što može nastaviti svoj rad.

31
00:01:33,560 --> 00:01:35,870
Kada je funkcija
potpuna i to je učinio,

32
00:01:35,870 --> 00:01:37,720
njegov okvir je popped off stog.

33
00:01:37,720 --> 00:01:38,950
To je terminologija.

34
00:01:38,950 --> 00:01:41,110
A okvir odmah
ispod nje, kao što sam rekao,

35
00:01:41,110 --> 00:01:42,880
postaje novi aktivni okvir.

36
00:01:42,880 --> 00:01:45,960
>> A ako to zahtijeva drugi funkciju,
to će ponovno pauzirati.

37
00:01:45,960 --> 00:01:49,290
To nova funkcija je stog okvir će
se guraju na vrhu snopa.

38
00:01:49,290 --> 00:01:50,650
To će učiniti svoje.

39
00:01:50,650 --> 00:01:52,100
To bi moglo pop back off.

40
00:01:52,100 --> 00:01:55,630
I druga funkcija
ispod se može nastaviti opet.

41
00:01:55,630 --> 00:02:00,080
>> Tako ćemo proći kroz to opet, u potrazi
na ideji faktorska funkcije

42
00:02:00,080 --> 00:02:03,070
da mi je definirano u
rekurzija videa vidjeti

43
00:02:03,070 --> 00:02:07,770
točno kako je magija iza toga
rekurzivna proces odvija.

44
00:02:07,770 --> 00:02:09,870
Dakle, ovo je naša cijela datoteka, zar ne?

45
00:02:09,870 --> 00:02:14,000
Definirali smo dva
functions-- glavni i činjenica.

46
00:02:14,000 --> 00:02:15,980
I kao što smo mogli očekivati,
bilo C program ide

47
00:02:15,980 --> 00:02:18,470
za početak na prvoj liniji glavna.

48
00:02:18,470 --> 00:02:21,660
>> Tako smo stvorili novu stog okvir za glavni.

49
00:02:21,660 --> 00:02:23,320
I to će se početi prikazivati.

50
00:02:23,320 --> 00:02:25,270
Glavni pozivi printf.

51
00:02:25,270 --> 00:02:29,390
I printf će
ispis faktorijel 5.

52
00:02:29,390 --> 00:02:31,440
Pa, to ne zna
što faktorijalni 5 je,

53
00:02:31,440 --> 00:02:35,620
pa to je poziv već
Ovisno o drugom pozivu funkcije.

54
00:02:35,620 --> 00:02:37,270
Dakle, glavna će pauzirati upravo tamo.

55
00:02:37,270 --> 00:02:39,103
Ja ću ostaviti
arrow pravo postoji, boju

56
00:02:39,103 --> 00:02:41,360
je iste boje kao i
stog okvir na desnoj strani,

57
00:02:41,360 --> 00:02:47,720
naznačiti da je glavna će se smrznuti
ovdje dok faktorijalni 5 zove.

58
00:02:47,720 --> 00:02:49,300
>> Dakle faktorijalni 5 zove.

59
00:02:49,300 --> 00:02:53,160
I to će početi na samom
počevši od faktorska funkcije.

60
00:02:53,160 --> 00:02:55,440
To postavlja pitanje ću jednak 1?

61
00:02:55,440 --> 00:02:56,810
Je 5 jednak 1?

62
00:02:56,810 --> 00:02:57,410
Pa, ne.

63
00:02:57,410 --> 00:03:01,110
Dakle, to će ići dolje
drugi dio, povratak n puta

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

65
00:03:02,990 --> 00:03:03,490
Pa, u redu.

66
00:03:03,490 --> 00:03:07,070
>> Tako sada, faktorski 5 je
ovisno o drugom pozivu

67
00:03:07,070 --> 00:03:09,740
da faktorijalni, prolazeći
u 4 kao parametar.

68
00:03:09,740 --> 00:03:14,210
I tako faktorijel
5 okvira, koji crvenog okvira,

69
00:03:14,210 --> 00:03:17,160
će zamrznuti upravo tamo
na toj liniji sam naznačeno

70
00:03:17,160 --> 00:03:21,914
i čekati faktorijel 4 do kraja
ono što treba učiniti kako bi zatim ga

71
00:03:21,914 --> 00:03:23,330
može ponovno postati aktivnom okviru.

72
00:03:23,330 --> 00:03:26,890
>> Dakle faktorijel 4 počinje u
početak faktorski.

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

74
00:03:28,556 --> 00:03:30,180
Ne, pa to će učiniti istu stvar.

75
00:03:30,180 --> 00:03:31,590
To će ići dolje još granu.

76
00:03:31,590 --> 00:03:33,240
To će doći do te linije koda.

77
00:03:33,240 --> 00:03:35,710
U redu, ja ću se vratiti četiri puta.

78
00:03:35,710 --> 00:03:41,270
Oh, faktorijel 3-- tako faktorijel
4 ovisi o faktorijel 3 dorade.

79
00:03:41,270 --> 00:03:43,055
>> I tako to treba nazvati faktorijel 3.

80
00:03:43,055 --> 00:03:45,180
I to će proći kroz
opet isti proces.

81
00:03:45,180 --> 00:03:48,200
Ona počinje kroz, dobiva ovdje.

82
00:03:48,200 --> 00:03:50,980
Faktorijel 3 ovisi
na faktorijel 1.

83
00:03:50,980 --> 00:03:53,750
Dakle faktorijalni 2 počinje, dobiva ovdje.

84
00:03:53,750 --> 00:03:56,310
To ovisi o faktorijel 1.

85
00:03:56,310 --> 00:03:57,430
Faktorijel 1 počinje.

86
00:03:57,430 --> 00:03:57,650
>> U REDU.

87
00:03:57,650 --> 00:03:59,775
Tako sada, mi smo dobivanje
negdje Zanimljivo, zar ne?

88
00:03:59,775 --> 00:04:02,190
Tako sada, 1 jednak 1.

89
00:04:02,190 --> 00:04:05,130
I tako smo se vratili 1.

90
00:04:05,130 --> 00:04:06,770
U ovom trenutku, mi se vraćaju.

91
00:04:06,770 --> 00:04:07,880
Funkcija je učinio.

92
00:04:07,880 --> 00:04:11,140
To je ponašanje is-- postoji
ništa drugo za to učiniti,

93
00:04:11,140 --> 00:04:17,006
pa stog okvir za
faktorijalni od 1. pops off.

94
00:04:17,006 --> 00:04:17,589
To je završio.

95
00:04:17,589 --> 00:04:19,480
Ona se vratila 1.

96
00:04:19,480 --> 00:04:23,370
A sada, faktorski 2, koji je
je okvir odmah ispod nje

97
00:04:23,370 --> 00:04:26,160
u snopu, postaje aktivni okvir.

98
00:04:26,160 --> 00:04:29,030
>> I to može pokupiti
točno tamo gdje je stao.

99
00:04:29,030 --> 00:04:32,240
To je bio čeka faktorski
od 1 završiti svoj rad.

100
00:04:32,240 --> 00:04:33,610
To je sada gotovo.

101
00:04:33,610 --> 00:04:35,510
I tako smo ovdje.

102
00:04:35,510 --> 00:04:38,080
>> Faktorijel 1 vratio vrijednost 1.

103
00:04:38,080 --> 00:04:42,430
Dakle faktorijalni 2 limenke
recimo vratili 2 puta 1.

104
00:04:42,430 --> 00:04:43,680
Njegov rad je sada učinio.

105
00:04:43,680 --> 00:04:49,110
To je vratila 2 do faktorski
3, koji je čekao nju.

106
00:04:49,110 --> 00:04:53,370
Faktorijel 3 je sada na vrhu okvira,
aktivni okvir u snopu.

107
00:04:53,370 --> 00:04:58,617
I tako je, kaže, u redu, dobro, idem
za povratak 3 puta 2, 6.

108
00:04:58,617 --> 00:05:00,700
I ja ću dati da se
vrijednost natrag na faktorski

109
00:05:00,700 --> 00:05:03,430
4, koji je čekao me.

110
00:05:03,430 --> 00:05:04,500
Gotov sam.

111
00:05:04,500 --> 00:05:09,410
Faktorijel 3 pops off stog, a
faktorijalni 4 je sada aktivan okvir.

112
00:05:09,410 --> 00:05:13,510
>> 4 kaže: U redu, ja ću se vratiti 4 puta
faktorijel od 3, što je šest.

113
00:05:13,510 --> 00:05:15,980
To je vrijednost koja
faktorijalni 3 se vraća.

114
00:05:15,980 --> 00:05:19,010
I tako 4 puta 6 je 24.

115
00:05:19,010 --> 00:05:20,990
I ja ću proći
da natrag na faktorski

116
00:05:20,990 --> 00:05:23,160
5, koji je čekao me.

117
00:05:23,160 --> 00:05:25,270
Faktorijel 5 je sada aktivan okvir.

118
00:05:25,270 --> 00:05:30,700
To će vratiti 5 puta
faktorijel 4-- 5 puta 24 ili 120--

119
00:05:30,700 --> 00:05:32,722
i dati tu vrijednost
Povratak na stranicu, koja ima

120
00:05:32,722 --> 00:05:35,680
Čekali vrlo strpljivo za
dugo vremena na dnu snopa.

121
00:05:35,680 --> 00:05:36,640
>> To je mjesto gdje je sve počelo.

122
00:05:36,640 --> 00:05:37,670
To je napravio ovaj poziv.

123
00:05:37,670 --> 00:05:39,400
Nekoliko okviri preuzeo na vrhu.

124
00:05:39,400 --> 00:05:41,890
Sada je ponovno na vrhu dimnjaka.

125
00:05:41,890 --> 00:05:43,450
To je aktivan okvir.

126
00:05:43,450 --> 00:05:47,810
Dakle, glavni je dobio vrijednost 120
natrag od faktorijel 5.

127
00:05:47,810 --> 00:05:50,750
To je čekala da
ispisati tu vrijednost.

128
00:05:50,750 --> 00:05:51,657
I onda se to radi.

129
00:05:51,657 --> 00:05:53,240
Nema više linija koda u glavni.

130
00:05:53,240 --> 00:05:56,800
Dakle, glavni je okvir pops off
stog, a mi smo učinili.

131
00:05:56,800 --> 00:05:58,992
>> I tako je rekurzija radi.

132
00:05:58,992 --> 00:06:00,200
Tako stog okviri raditi.

133
00:06:00,200 --> 00:06:03,120
Ti pozivi funkcija
što se dogodilo prije

134
00:06:03,120 --> 00:06:06,620
samo su na pauzi, čekajući
za naknadne pozive

135
00:06:06,620 --> 00:06:12,050
završiti tako da oni mogu postati aktivni
okvir i završiti ono što im je potrebno učiniti.

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

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

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