1
00:00:00,000 --> 00:00:07,800

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Da bi se razumjelo
rekurzija, morate

3
00:00:10,190 --> 00:00:13,820
prvi razumjeti rekurziju.

4
00:00:13,820 --> 00:00:17,280
Nakon što je rekurzija u programu dizajna sredstvima
da imate samoodnoseću

5
00:00:17,280 --> 00:00:18,570
definicije.

6
00:00:18,570 --> 00:00:21,520
Rekurzivnih struktura podataka, na primjer,
su strukture podataka koje

7
00:00:21,520 --> 00:00:23,990
uključuju u
njihove definicije.

8
00:00:23,990 --> 00:00:27,160
Ali danas, mi ćemo se usredotočiti
na rekurzivnim funkcijama.

9
00:00:27,160 --> 00:00:31,160
>> Sjetite se da je funkcija uzeti ulaza,
Argumenti i vratiti vrijednost kao i njihovi

10
00:00:31,160 --> 00:00:34,480
Izlaz zastupa
ovaj dijagram ovdje.

11
00:00:34,480 --> 00:00:38,060
Smislit ćemo okvira kao tijelo
funkcija, sadrži niz

12
00:00:38,060 --> 00:00:42,340
Upute koji interpretiraju
ulaz i osigurati izlaz.

13
00:00:42,340 --> 00:00:45,660
Uzimajući bliži pogled unutar tijela
Funkcija mogao otkriti pozive

14
00:00:45,660 --> 00:00:47,430
ostale funkcije.

15
00:00:47,430 --> 00:00:51,300
Iskoristite ovu jednostavnu funkciju, Foo, da
traje jedan niz kao ulaz i

16
00:00:51,300 --> 00:00:54,630
ispisuje koliko slova
da žica ima.

17
00:00:54,630 --> 00:00:58,490
Funkcija strlen, za duljinu niza,
naziva, čiji je izlaz

18
00:00:58,490 --> 00:01:01,890
potreban za poziv na printf.

19
00:01:01,890 --> 00:01:05,770
>> Sada, ono što čini rekurzivna funkcija
Poseban je da se zove.

20
00:01:05,770 --> 00:01:09,610
Mi može predstavljati ovu rekurzivna
poziv s ovom narančastom strelicom

21
00:01:09,610 --> 00:01:11,360
vraćanja do sebe.

22
00:01:11,360 --> 00:01:15,630
Ali opet se izvršavaju će samo
napraviti još jedan rekurzivni poziv, a

23
00:01:15,630 --> 00:01:17,150
još jedan i drugi.

24
00:01:17,150 --> 00:01:19,100
No, rekurzivna funkcija
ne može biti beskonačan.

25
00:01:19,100 --> 00:01:23,490
Oni su na kraju nekako, ili tvoje
Program će se izvoditi zauvijek.

26
00:01:23,490 --> 00:01:27,680
>> Dakle, moramo naći način da raskine
iz rekurzivnih poziva.

27
00:01:27,680 --> 00:01:29,900
Mi to nazivamo osnovni scenarij.

28
00:01:29,900 --> 00:01:33,570
Kad je upoznao osnovni scenarij stanje,
Funkcija vraća bez

29
00:01:33,570 --> 00:01:34,950
još jedna rekurzivna poziva.

30
00:01:34,950 --> 00:01:39,610
Iskoristite ovu funkciju, hi, funkcija void
koji traje int n kao ulaz.

31
00:01:39,610 --> 00:01:41,260
Baza slučaj na prvom mjestu.

32
00:01:41,260 --> 00:01:46,220
Ako je n manji od nule, print i bye
Za povratak svim drugim slučajevima,

33
00:01:46,220 --> 00:01:49,400
Funkcija će ispisati hi i izvršiti
rekurzivna poziva.

34
00:01:49,400 --> 00:01:53,600
Još jedan poziv na funkcije bok s
smanjene vrijednosti ulaza.

35
00:01:53,600 --> 00:01:56,790
>> Sada, iako smo ispisali hi,
Funkcija neće prekinuti sve dok ne

36
00:01:56,790 --> 00:02:00,370
vratiti svoju vrstu povrata,
u ovom slučaju praznini.

37
00:02:00,370 --> 00:02:04,830
Dakle, za svaki n, osim osnovnog scenarija,
ova funkcija hi hi će se vratiti

38
00:02:04,830 --> 00:02:06,890
n minus 1.

39
00:02:06,890 --> 00:02:10,050
Budući da je ova funkcija void iako smo
neće izrijekom upišete povratak ovdje.

40
00:02:10,050 --> 00:02:12,000
Samo ćemo izvršiti funkciju.

41
00:02:12,000 --> 00:02:16,960
Dakle pozivom hi (3) će ispisati hi i
izvršavanje hi (2) koji izvodi hi (1) jedan

42
00:02:16,960 --> 00:02:20,560
koji izvršava hi (0), u kojoj
osnovni scenarij uvjet zadovoljen.

43
00:02:20,560 --> 00:02:24,100
Dakle hi (0) ispisuje bye i vraća.

44
00:02:24,100 --> 00:02:24,990
>> OK.

45
00:02:24,990 --> 00:02:28,690
Tako da sada možemo razumjeti osnove
rekurzivna funkcija, koje su im potrebne

46
00:02:28,690 --> 00:02:32,730
najmanje jedne baze, kao slučaj
rekurzivna poziva, neka je premjestiti na

47
00:02:32,730 --> 00:02:34,120
više smisla primjer.

48
00:02:34,120 --> 00:02:37,830
One koji ne samo da se vrate
poništiti bez obzira.

49
00:02:37,830 --> 00:02:41,340
>> Idemo pogledati Faktorijalni
Operacija se koristi najčešće u

50
00:02:41,340 --> 00:02:43,660
izračuni vjerojatnosti.

51
00:02:43,660 --> 00:02:48,120
Faktorijel n je proizvod svakog
pozitivan cijeli broj manji od

52
00:02:48,120 --> 00:02:49,400
i jednak n.

53
00:02:49,400 --> 00:02:56,731
Dakle faktorjela pet je 5 puta 4 puta
3 puta 2 puta 1, čime se dobije 120.

54
00:02:56,731 --> 00:03:01,400
Četiri faktorjela je 4 puta 3 puta
2 puta 1 da se dobije 24.

55
00:03:01,400 --> 00:03:04,910
A isto pravilo vrijedi
na bilo koji pozitivni cijeli broj.

56
00:03:04,910 --> 00:03:08,670
>> Pa kako bismo mogli napisati rekurzivna
funkcija koja izračunava faktorijel

57
00:03:08,670 --> 00:03:09,960
broja?

58
00:03:09,960 --> 00:03:14,700
Pa, mi ćemo morati identificirati i
osnovni scenarij i rekurzivna poziva.

59
00:03:14,700 --> 00:03:18,250
Rekurzivna poziva neće biti isti
za svim slučajevima osim za bazu

60
00:03:18,250 --> 00:03:21,420
slučaj, što znači da ćemo morati
pronaći model koji će nam dati našim

61
00:03:21,420 --> 00:03:23,350
željeni rezultat.

62
00:03:23,350 --> 00:03:30,270
>> Na ovom primjeru vidimo kako 5 faktorjela
uključuje množenjem 4 x 3 za 2 za 1

63
00:03:30,270 --> 00:03:33,010
I to isto množenja
nalazi se ovdje,

64
00:03:33,010 --> 00:03:35,430
Definicija 4. faktorjela.

65
00:03:35,430 --> 00:03:39,810
Dakle, vidimo da je 5 faktorjela
samo 5 puta 4 faktorjela.

66
00:03:39,810 --> 00:03:43,360
Sada se taj obrazac primjenjuju
do 4 faktorjela kao i?

67
00:03:43,360 --> 00:03:44,280
Da.

68
00:03:44,280 --> 00:03:49,120
Vidimo da je 4 faktorjela sadrži
Množenje 3 puta 2 puta 1,

69
00:03:49,120 --> 00:03:51,590
Isti definicija kao 3 faktorjela.

70
00:03:51,590 --> 00:03:56,950
Do 4 faktorijel jednak 3 do 4 puta
faktora, i tako dalje i tako bliže našem

71
00:03:56,950 --> 00:04:02,170
Uzorak drži do 1. faktora, koji
po definiciji je jednak 1.

72
00:04:02,170 --> 00:04:04,950
>> Nema drugog pozitivno
cijeli brojevi napustio.

73
00:04:04,950 --> 00:04:07,870
Dakle, imamo uzorak za
naš rekurzivna poziva.

74
00:04:07,870 --> 00:04:13,260
n je jednak faktorijel N puta
faktorjela n minus 1.

75
00:04:13,260 --> 00:04:14,370
I naš osnovni scenarij?

76
00:04:14,370 --> 00:04:17,370
To će biti samo naša definicija
od 1 faktorjela.

77
00:04:17,370 --> 00:04:19,995
>> Dakle, sada možemo prijeći na pisanje
broj za funkciju.

78
00:04:19,995 --> 00:04:24,110
Za baznu slučaju, imat ćemo
Uvjet je n = jednako 1, gdje je

79
00:04:24,110 --> 00:04:25,780
vratit ćemo se jednom.

80
00:04:25,780 --> 00:04:29,280
Tada kreće na rekurzivni poziv,
vratit ćemo se n puta

81
00:04:29,280 --> 00:04:32,180
faktorjela n minus 1.

82
00:04:32,180 --> 00:04:33,590
>> Sada ćemo testirati ovaj naš.

83
00:04:33,590 --> 00:04:35,900
Pokušajmo faktorijel 4.

84
00:04:35,900 --> 00:04:39,420
Po našoj funkciji je jednaka
do 4 puta faktorski (3).

85
00:04:39,420 --> 00:04:43,040
Faktorijel (3) je jednak
3 puta faktorijel (2).

86
00:04:43,040 --> 00:04:48,700
Faktorijel (2) je jednak 2 puta
faktorijel (1), koji vraća 1.

87
00:04:48,700 --> 00:04:52,490
Faktorijela (2) sada vraća 2 puta 1, 2.

88
00:04:52,490 --> 00:04:55,960
Faktorijela (3) se sada može vratiti
3 puta 2, 6.

89
00:04:55,960 --> 00:05:02,490
I na kraju, faktorjela (4)
vraća 4 puta 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Ako se pojave bilo kakvih poteškoća
s rekurzivni poziv, pretvarati se da

91
00:05:06,780 --> 00:05:09,660
funkcija radi već.

92
00:05:09,660 --> 00:05:13,450
Što mislim to je da treba
Vaše povjerenje rekurzivnih poziva da se vrate

93
00:05:13,450 --> 00:05:15,100
prave vrijednosti.

94
00:05:15,100 --> 00:05:18,960
Na primjer, ako znam da je
faktorjela (5) iznosi 5 puta

95
00:05:18,960 --> 00:05:24,870
faktorjela (4), ja ću vjerovati da je
faktorjela (4) će mi dati 24.

96
00:05:24,870 --> 00:05:28,510
Razmislite o tome kao varijable, ako
će se, kao da je već definirana

97
00:05:28,510 --> 00:05:30,070
faktorijel (4).

98
00:05:30,070 --> 00:05:33,850
Dakle, za bilo faktorjela (n), to je
Produkt n i

99
00:05:33,850 --> 00:05:35,360
natrag faktorjela.

100
00:05:35,360 --> 00:05:38,130
A to natrag faktorjela
Dobije pozivom

101
00:05:38,130 --> 00:05:41,330
faktorjela n minus 1.

102
00:05:41,330 --> 00:05:45,130
>> Sada, vidjeti ako možete provesti
rekurzivna funkcija sebe.

103
00:05:45,130 --> 00:05:50,490
Natrpati svoj terminal, ili run.cs50.net,
i napisati funkciju suma

104
00:05:50,490 --> 00:05:54,770
koji traje cijeli broj N i vraća
Zbroj svih uzastopna pozitivna

105
00:05:54,770 --> 00:05:57,490
cijeli brojevi iz N u jedan.

106
00:05:57,490 --> 00:06:01,000
Ja sam napisao out sume neke
Vrijednosti će vam pomoći naš.

107
00:06:01,000 --> 00:06:04,030
Prvo, shvatiti
osnovni scenarij stanje.

108
00:06:04,030 --> 00:06:06,170
Zatim, pogled na sumu (5).

109
00:06:06,170 --> 00:06:09,270
Možete li ga izraziti u smislu
drugog iznosa?

110
00:06:09,270 --> 00:06:11,290
Sada, što je suma (4)?

111
00:06:11,290 --> 00:06:15,630
Kako možete izraziti sumu (4)
u odnosu na drugu sumu?

112
00:06:15,630 --> 00:06:19,655
>> Nakon što su iznos (5) i zbroj (4)
izražena u smislu drugih iznosa, vidjet

113
00:06:19,655 --> 00:06:22,970
ako mogu identificirati
Obrazac za sumu (n).

114
00:06:22,970 --> 00:06:26,190
Ako ne, pokušajte još nekoliko brojeva
i izraziti svoje sume u

115
00:06:26,190 --> 00:06:28,410
Uvjeti još brojeva.

116
00:06:28,410 --> 00:06:31,930
Identificiranjem obrasce za diskretne
brojevi, da ste na dobrom putu da

117
00:06:31,930 --> 00:06:34,320
identificiranje uzorak za bilo koji n.

118
00:06:34,320 --> 00:06:38,040
>> Rekurzije je jako moćan alat,
pa naravno, to nije ograničeno na

119
00:06:38,040 --> 00:06:39,820
matematičkih funkcija.

120
00:06:39,820 --> 00:06:44,040
Rekurzija se može koristiti vrlo učinkovito
kada se bave s drveća za primjer.

121
00:06:44,040 --> 00:06:47,210
Pogledajte kratki na stablima za
temeljitiji pregled, ali za sada

122
00:06:47,210 --> 00:06:51,140
podsjetiti da pretraživanje po binarnom stabala, u
Osobito su sastavljene od čvorova, svaka

123
00:06:51,140 --> 00:06:53,820
s vrijednošću i dva čvora naputke.

124
00:06:53,820 --> 00:06:57,270
Obično, to je predstavljen
roditelj čvor ima jednu liniju koja pokazuje

125
00:06:57,270 --> 00:07:01,870
na lijevom čvor dijete i jedan
na pravo čvor dijete.

126
00:07:01,870 --> 00:07:04,510
Struktura binarnog pretraživanja
Stablo se posuđuje i

127
00:07:04,510 --> 00:07:05,940
na rekurzivni pretraživanje.

128
00:07:05,940 --> 00:07:09,730
Rekurzivna poziva ili prolazi u
lijevo ili desno čvor, ali više

129
00:07:09,730 --> 00:07:10,950
od toga u stablo Short.

130
00:07:10,950 --> 00:07:15,690
>> Recimo da želite obaviti operaciju
svaki čvor u binarnom stablu.

131
00:07:15,690 --> 00:07:17,410
Kako možete ići o tome?

132
00:07:17,410 --> 00:07:20,600
Pa, što bi mogao napisati rekurzivna
funkcija koja obavlja rad

133
00:07:20,600 --> 00:07:24,450
na roditeljski čvor i čini rekurzivna
pozvati na istu funkciju,

134
00:07:24,450 --> 00:07:27,630
prolazi u lijevo i
prava djece čvorova.

135
00:07:27,630 --> 00:07:31,650
Na primjer, ova funkcija, Foo, da
mijenja vrijednost danog čvora i

136
00:07:31,650 --> 00:07:33,830
sve svoje djece na 1.

137
00:07:33,830 --> 00:07:37,400
Baza slučaj null čvorova uzroka
funkcija za povratak, što upućuje

138
00:07:37,400 --> 00:07:41,290
da ne postoje nikakvi čvorovi
ostavio u tom pod-stabla.

139
00:07:41,290 --> 00:07:42,620
>> Idemo prošetati kroz nju.

140
00:07:42,620 --> 00:07:44,340
Prvi roditelj 13.

141
00:07:44,340 --> 00:07:47,930
Mi promijeniti vrijednost na 1, a zatim pozvati
naša funkcija na lijevoj strani, kao i

142
00:07:47,930 --> 00:07:49,600
kao pravu.

143
00:07:49,600 --> 00:07:53,910
Funkcija, Foo, zove se na lijevoj strani
pod-stablo prvo, pa lijevo čvor

144
00:07:53,910 --> 00:07:57,730
će se rasporediti na 1. i Foo će
se pozvao djecu da čvora,

145
00:07:57,730 --> 00:08:01,900
Prvi lijevo, a zatim desno,
i tako dalje i tako dalje.

146
00:08:01,900 --> 00:08:05,630
I reci im da grane ne moraju
bilo više djece pa isti proces

147
00:08:05,630 --> 00:08:09,700
nastavit će se za pravo djece
dok cijela stabla su čvorovi

148
00:08:09,700 --> 00:08:11,430
rasporediti na jedan.

149
00:08:11,430 --> 00:08:15,390
>> Kao što možete vidjeti, niste ograničeni
na samo jedan rekurzivna poziva.

150
00:08:15,390 --> 00:08:17,930
Upravo onoliko koliko će dobiti posao ispunjavanja.

151
00:08:17,930 --> 00:08:21,200
Što ako je stablo u kojem svaki
čvora je imao troje djece,

152
00:08:21,200 --> 00:08:23,100
Lijevo, srednji, i zar ne?

153
00:08:23,100 --> 00:08:24,886
Kako biste uredili Foo?

154
00:08:24,886 --> 00:08:25,860
Pa, jednostavno.

155
00:08:25,860 --> 00:08:30,250
Samo dodati još jedan rekurzivni poziv i
prođe u srednji čvor pokazivača.

156
00:08:30,250 --> 00:08:34,549
>> Rekurzije je vrlo moćan i da ne
spomenuti elegantna, ali to može biti

157
00:08:34,549 --> 00:08:38,010
Teško koncept u početku, pa se
strpljivi i uzmite si vremena.

158
00:08:38,010 --> 00:08:39,370
Počnite s osnovnom scenariju.

159
00:08:39,370 --> 00:08:42,650
To je obično najlakše prepoznati,
i onda možete raditi

160
00:08:42,650 --> 00:08:43,830
unatrag od tamo.

161
00:08:43,830 --> 00:08:46,190
Vi znate da je potrebno doći do svoje
osnovni scenarij, tako da bi moglo

162
00:08:46,190 --> 00:08:47,760
dati vam nekoliko savjeta.

163
00:08:47,760 --> 00:08:53,120
Pokušajte izraziti jedan specifičan slučaj u
Uvjeti drugim slučajevima, ili u pod-seta.

164
00:08:53,120 --> 00:08:54,700
>> Hvala što gledate ovaj kratki.

165
00:08:54,700 --> 00:08:58,920
U najmanju ruku, sada možete
razumiju viceve kao što je ovaj.

166
00:08:58,920 --> 00:09:01,250
Moje ime je Zamyla, a to je CS50.

167
00:09:01,250 --> 00:09:04,306

168
00:09:04,306 --> 00:09:07,170
>> Iskoristite ovu funkciju, hi,
void funkcija koja traje

169
00:09:07,170 --> 00:09:09,212
int n, kao ulaz.

170
00:09:09,212 --> 00:09:11,020
Baza slučaj na prvom mjestu.

171
00:09:11,020 --> 00:09:14,240
Ako je n manji od 0, print
"Bye" i povratak.

172
00:09:14,240 --> 00:09:15,490