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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Por kompreni
rekursio, vi devas

3
00:00:10,190 --> 00:00:13,820
unue kompreni rekursio.

4
00:00:13,820 --> 00:00:17,280
Havante rekursio en programo dezajno rimedoj
ke vi havas mem-referenca

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

6
00:00:18,570 --> 00:00:21,520
Recursive datumstrukturoj, ekzemple,
Estas datumstrukturoj ke

7
00:00:21,520 --> 00:00:23,990
inkluzivi en
iliaj difinoj.

8
00:00:23,990 --> 00:00:27,160
Sed hodiaŭ, ni tuj enfokusigi
sur rekursiaj funkcioj.

9
00:00:27,160 --> 00:00:31,160
>> Memoru ke funkcioj preni enigoj,
argumentoj, kaj resendas valoron kiel ilia

10
00:00:31,160 --> 00:00:34,480
eligo reprezentita de
ĉi diagramo tie.

11
00:00:34,480 --> 00:00:38,060
Ni pensu pri la skatolon kiel la korpo de
la funkcio, enhavante la aro de

12
00:00:38,060 --> 00:00:42,340
instrukcioj kiujn interpretas la
enigo kaj provizas eligon.

13
00:00:42,340 --> 00:00:45,660
Prenante pli proksiman rigardon interne de la korpo de
la funkcio povus malkaŝi alvokojn al

14
00:00:45,660 --> 00:00:47,430
aliaj funkcioj tiel.

15
00:00:47,430 --> 00:00:51,300
Prenu ĉi simpla funkcio, foo, ke
prenas sola kordo kiel enigo kaj

16
00:00:51,300 --> 00:00:54,630
impresoj kiom da literoj
ke kordoj havas.

17
00:00:54,630 --> 00:00:58,490
La funkcio strlen, por korda longeco,
estas nomita, kies eliro estas

18
00:00:58,490 --> 00:01:01,890
bezonata por la alvoko al printf.

19
00:01:01,890 --> 00:01:05,770
>> Nun, kio faras rekursia funkcio
specialaj estas, ke li nomas sin.

20
00:01:05,770 --> 00:01:09,610
Ni povas reprezenti ĉi rekursiaj
nomas per tiu oranĝo sago

21
00:01:09,610 --> 00:01:11,360
looping reen al sin.

22
00:01:11,360 --> 00:01:15,630
Sed ekzekutante denove volas nur
fari alian rekursia alvoko, kaj

23
00:01:15,630 --> 00:01:17,150
alia kaj alia.

24
00:01:17,150 --> 00:01:19,100
Sed rekursiaj funkcioj
ne povas esti malfinio.

25
00:01:19,100 --> 00:01:23,490
Ili devas fini iel, aŭ via
programo kuros eterne.

26
00:01:23,490 --> 00:01:27,680
>> Do ni devas trovi manieron rompi
el la rekursiaj vokoj.

27
00:01:27,680 --> 00:01:29,900
Ni nomas tiun la baza kazo.

28
00:01:29,900 --> 00:01:33,570
Kiam la baza kazo kondiĉo estas renkontiĝis,
La funkcio redonas sen fari

29
00:01:33,570 --> 00:01:34,950
alia rekursia alvoko.

30
00:01:34,950 --> 00:01:39,610
Prenu ĉi funkcion, hi, malplena funkcio
kiuj prenas int n kiel enigo.

31
00:01:39,610 --> 00:01:41,260
La baza kazo venas unue.

32
00:01:41,260 --> 00:01:46,220
Se n estas malpli ol nulo, presi bye kaj
revenu Por ĉiuj aliaj kazoj, la

33
00:01:46,220 --> 00:01:49,400
funkcio presos hi kaj ekzekuti
la rekursia alvoko.

34
00:01:49,400 --> 00:01:53,600
Alia alvoko al la funkcio hi kun
a decremented eniga valoro.

35
00:01:53,600 --> 00:01:56,790
>> Nun, eĉ kvankam ni presi hi, la
funkcio ne finiĝas ĝis ni

36
00:01:56,790 --> 00:02:00,370
redoni lian revenon tipo,
en ĉi tiu kazo malplenon.

37
00:02:00,370 --> 00:02:04,830
Do por ĉiu n escepte la baza kazo,
tiun funkcion hi redonos hi

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

39
00:02:06,890 --> 00:02:10,050
Ekde ĉi tiu funkcio estas malplena kvankam, ni
ne eksplicite tajpi reveno tie.

40
00:02:10,050 --> 00:02:12,000
Ni simple ekzekuti la funkcio.

41
00:02:12,000 --> 00:02:16,960
Do nomi hi (3) presos hi kaj
ekzekuti hi (2) kiuj ekzekutas hi (1) unu

42
00:02:16,960 --> 00:02:20,560
kiuj ekzekutas hi (0), kie la
bazo kazo kondiĉo renkontis.

43
00:02:20,560 --> 00:02:24,100
Do hi (0) presas bye kaj revenas.

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

45
00:02:24,990 --> 00:02:28,690
Do nun ke ni komprenas la bazojn de
rekursiaj funkcioj, kiujn ili bezonas

46
00:02:28,690 --> 00:02:32,730
almenaŭ unu baza kazo tiel kiel
rekursia alvoko, ni pluiru al

47
00:02:32,730 --> 00:02:34,120
pli signifa ekzemplo.

48
00:02:34,120 --> 00:02:37,830
Kiu ne ĝuste reveni
vanigas negrave kion.

49
00:02:37,830 --> 00:02:41,340
>> Ni rigardu la faktorialo
operacion uzata plej ofte en

50
00:02:41,340 --> 00:02:43,660
probablo kalkuloj.

51
00:02:43,660 --> 00:02:48,120
Faktorialo de n estas la produto de ĉiu
pozitiva entjero malpli ol

52
00:02:48,120 --> 00:02:49,400
kaj egalaj al n.

53
00:02:49,400 --> 00:02:56,731
Do faktorialo kvin estas 5 horoj 4 horoj
3 fojojn 2 horoj 1 doni 120.

54
00:02:56,731 --> 00:03:01,400
Kvar faktorialo estas 4 horoj 3 horoj
2 fojojn 1 doni 24.

55
00:03:01,400 --> 00:03:04,910
Kaj la sama regulo validas
al ĉiu pozitiva entjero.

56
00:03:04,910 --> 00:03:08,670
>> Do kiel povus oni skribi rekursia
Funkcio kiu kalkulas la faktorialo

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

58
00:03:09,960 --> 00:03:14,700
Nu, ni bezonas por identigi ambaŭ la
bazo kazo kaj la rekursia alvoko.

59
00:03:14,700 --> 00:03:18,250
La rekursia alvoko estos la sama
por ĉiuj kazoj krom la bazo

60
00:03:18,250 --> 00:03:21,420
kazo, kio signifas, ke ni devos
trovi modelon, kiu donos al ni nia

61
00:03:21,420 --> 00:03:23,350
deziratan rezulton.

62
00:03:23,350 --> 00:03:30,270
>> Por ĉi tiu ekzemplo, vidi kiel 5 faktorialo
engaĝas multiplikante 4 de 3 per 2 per 1

63
00:03:30,270 --> 00:03:33,010
Kaj tio tre sama multipliko
Estas trovitaj tie, la

64
00:03:33,010 --> 00:03:35,430
difino de 4 faktorialo.

65
00:03:35,430 --> 00:03:39,810
Do ni vidas, ke la 5 faktorialo estas
nur 5 horoj 4 faktorialo.

66
00:03:39,810 --> 00:03:43,360
Nun tiu ĉi ŝablono apliki
4 faktorialo tiel?

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

68
00:03:44,280 --> 00:03:49,120
Ni vidas ke 4 faktorialo enhavas la
multipliko 3 fojojn 2 horoj 1, la

69
00:03:49,120 --> 00:03:51,590
tre sama difino kiel 3 faktorialo.

70
00:03:51,590 --> 00:03:56,950
Do 4 faktorialo estas egala al 4 fojoj 3
Faktorialo, kaj tiel plu kaj tiel plu, nia

71
00:03:56,950 --> 00:04:02,170
mastro bastonoj ĝis 1 faktorialo, kiuj
per difino estas egala al 1.

72
00:04:02,170 --> 00:04:04,950
>> Estas neniu alia pozitiva
entjeroj maldekstre.

73
00:04:04,950 --> 00:04:07,870
Do ni havas la skemon por
nia rekursia alvoko.

74
00:04:07,870 --> 00:04:13,260
n faktorialoj estas egala al n fojoj
la faktorialo de n minus 1.

75
00:04:13,260 --> 00:04:14,370
Kaj nia bazo kazo?

76
00:04:14,370 --> 00:04:17,370
Tio estos nur esti nia difino
de 1 faktorialo.

77
00:04:17,370 --> 00:04:19,995
>> Do nun ni povas pluiri al skribo
kodo por la funkcio.

78
00:04:19,995 --> 00:04:24,110
Por la baza kazo, ni havos la
kondiĉo n egalas egaluloj 1, kie

79
00:04:24,110 --> 00:04:25,780
ni revenos 1.

80
00:04:25,780 --> 00:04:29,280
Tiam movanta sur la rekursia alvoko,
ni revenos n fojoj la

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

82
00:04:32,180 --> 00:04:33,590
>> Nun ni testi tiun nian.

83
00:04:33,590 --> 00:04:35,900
Ni provu faktorialo 4.

84
00:04:35,900 --> 00:04:39,420
Per nia funkcio estas egala
4 fojoj faktorialo (3).

85
00:04:39,420 --> 00:04:43,040
Faktorialo (3) estas egala al
3 fojoj faktorialo (2).

86
00:04:43,040 --> 00:04:48,700
Faktorialo (2) estas egala al 2 fojoj
faktorialo (1), kiu denove 1.

87
00:04:48,700 --> 00:04:52,490
Faktorialo (2) nun revenas 2 fojoj 1, 2.

88
00:04:52,490 --> 00:04:55,960
Faktorialo (3) povas nun revenu
3 fojojn 2, 6.

89
00:04:55,960 --> 00:05:02,490
Kaj fine, faktorialo (4)
Revenas 4 fojoj 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Se vi renkontis ajna malfacilaĵo
kun la rekursia alvoko, ŝajnigi ke

91
00:05:06,780 --> 00:05:09,660
la funkcio laboras jam.

92
00:05:09,660 --> 00:05:13,450
Kion mi celas per tio, ke vi devus
fidi vian rekursiaj alvokoj reveni

93
00:05:13,450 --> 00:05:15,100
dekstre valoroj.

94
00:05:15,100 --> 00:05:18,960
Ekzemple, se mi scias ke
faktorialo (5) egalas 5 fojoj

95
00:05:18,960 --> 00:05:24,870
faktorialo (4), mi iros kaj esperas, ke
faktorialo (4) donos al mi 24.

96
00:05:24,870 --> 00:05:28,510
Pensu pri ĝi kiel variablon, se vi
volo, kiel se vi jam difinita

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

98
00:05:30,070 --> 00:05:33,850
Do pro ajna faktorialo (n), ĝi estas
la produto de n kaj

99
00:05:33,850 --> 00:05:35,360
la antaŭan faktorialo.

100
00:05:35,360 --> 00:05:38,130
Kaj tion antaŭa faktorialo
estas ricevita per vokante

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

102
00:05:41,330 --> 00:05:45,130
>> Nun, ĉu vi povas apliki
rekursia funkcio mem.

103
00:05:45,130 --> 00:05:50,490
Ŝarĝi vian terminalo, aŭ run.cs50.net,
kaj skribi funkcion sumo

104
00:05:50,490 --> 00:05:54,770
kiu prenas entjero n kaj redonas la
sumo de ĉiuj sinsekva pozitiva

105
00:05:54,770 --> 00:05:57,490
entjeroj el n al 1.

106
00:05:57,490 --> 00:06:01,000
Mi jam skribis el la sumoj de iu
valorojn por helpi al vi nian.

107
00:06:01,000 --> 00:06:04,030
Unue, eltrovi la
bazo kazo kondiĉo.

108
00:06:04,030 --> 00:06:06,170
Tiam, rigardu sumo (5).

109
00:06:06,170 --> 00:06:09,270
Ĉu vi povas esprimi ĝin en terminoj
de alia sumo?

110
00:06:09,270 --> 00:06:11,290
Nun, kio pri sumo (4)?

111
00:06:11,290 --> 00:06:15,630
Kiel vi povas esprimi sumo (4)
en terminoj de alia sumo?

112
00:06:15,630 --> 00:06:19,655
>> Kiam vi havas sumo (5) kaj sumo (4)
esprimita en terminoj de aliaj sumoj, vidu

113
00:06:19,655 --> 00:06:22,970
se vi povas identigi
mastron por sumo (n).

114
00:06:22,970 --> 00:06:26,190
Se ne, provu kelkaj aliaj nombroj
kaj esprimi siajn sumoj en

115
00:06:26,190 --> 00:06:28,410
terminoj de alia numerojn.

116
00:06:28,410 --> 00:06:31,930
Per identiganta ŝablonoj por diskreta
numerojn, vi bone sur via vojo al

117
00:06:31,930 --> 00:06:34,320
identiganta la ŝablono por ĉiu n.

118
00:06:34,320 --> 00:06:38,040
>> Rekursio estas vere potenca ilo,
do kompreneble ĝi ne estas limigita al

119
00:06:38,040 --> 00:06:39,820
matematikaj funkcioj.

120
00:06:39,820 --> 00:06:44,040
Rekursio povas uzi tre efike
kiam kontraktanta kun arboj ekzemple.

121
00:06:44,040 --> 00:06:47,210
Kontrolu la mallonga sur arboj por
pli funda revizio, sed por nun

122
00:06:47,210 --> 00:06:51,140
memoras ke duuma serĉo arboj, en
aparta, estas formitaj de nodoj, ĉiu

123
00:06:51,140 --> 00:06:53,820
kun valoro kaj du nodo montriloj.

124
00:06:53,820 --> 00:06:57,270
Kutime, tiu estas reprezentita de la
patro nodo havanta unu linio notante

125
00:06:57,270 --> 00:07:01,870
maldekstren infano nodo kaj unu
al la dekstra infano nodo.

126
00:07:01,870 --> 00:07:04,510
La strukturo de duuma serĉo
arbo pruntas bone

127
00:07:04,510 --> 00:07:05,940
al rekursia serĉo.

128
00:07:05,940 --> 00:07:09,730
La rekursia alvoko ĉu pasas en la
maldekstra aŭ la dekstra nodo, sed pli

129
00:07:09,730 --> 00:07:10,950
de tiu en la arbo mallonga.

130
00:07:10,950 --> 00:07:15,690
>> Diru vi volas plenumi operacion en
ĉiu simpla nodo en duuma arbo.

131
00:07:15,690 --> 00:07:17,410
Kiel eble vi iru sur tio?

132
00:07:17,410 --> 00:07:20,600
Nu, vi povus skribi rekursia
funkcio kiu plenumas la operacio

133
00:07:20,600 --> 00:07:24,450
je la patro nodo kaj faras rekursia
vokas la saman funkcion,

134
00:07:24,450 --> 00:07:27,630
pasante en la maldekstra kaj
dekstra infano nodoj.

135
00:07:27,630 --> 00:07:31,650
Ekzemple, ĉi tiu funkcio, foo, ke
ŝanĝu la valoron de donita vertico kaj

136
00:07:31,650 --> 00:07:33,830
ĉiujn ĝiajn infanojn al 1.

137
00:07:33,830 --> 00:07:37,400
La baza kazo de nula nodo kaŭzoj
la funkcio por reveni, indikante

138
00:07:37,400 --> 00:07:41,290
ke estas nenia nodoj
lasis en tiu sub-arbo.

139
00:07:41,290 --> 00:07:42,620
>> Ni iru tra ĝi.

140
00:07:42,620 --> 00:07:44,340
La unua patro estas 13.

141
00:07:44,340 --> 00:07:47,930
Ni ŝanĝu la valoron 1, kaj tiam nomita
nia funkcio sur la maldekstra tiel

142
00:07:47,930 --> 00:07:49,600
kiel la rajto.

143
00:07:49,600 --> 00:07:53,910
La funkcio, foo, nomiĝas maldekstre
sub-arbo unue, do la maldekstra vertico

144
00:07:53,910 --> 00:07:57,730
estos reasignada al 1 kaj foo volo
nomi sur tiu nodo de filoj,

145
00:07:57,730 --> 00:08:01,900
unue la maldekstran kaj tiam dekstre,
kaj tiel plu kaj tiel plu.

146
00:08:01,900 --> 00:08:05,630
Kaj diru al ili, ke branĉoj ne havas
plu filoj por la sama procezo

147
00:08:05,630 --> 00:08:09,700
sekvos por la rajto infanoj
ĝis la tuta arbo de la nodoj estas

148
00:08:09,700 --> 00:08:11,430
reasignada al 1.

149
00:08:11,430 --> 00:08:15,390
>> Kiel vi povas vidi, vi ne estas limigita
al nur unu rekursia alvoko.

150
00:08:15,390 --> 00:08:17,930
Nur tiom, kiom ricevos la laboron farita.

151
00:08:17,930 --> 00:08:21,200
Kio, se vi havis arbon kie ĉiu
nodo havis tri filojn,

152
00:08:21,200 --> 00:08:23,100
Maldekstra, meza, kaj ĝuste?

153
00:08:23,100 --> 00:08:24,886
Kiel vi redaktanton foo?

154
00:08:24,886 --> 00:08:25,860
Nu, simplaj.

155
00:08:25,860 --> 00:08:30,250
Nur aldonu alian rekursia alvoko kaj
Iam en la mezo nodo montrilo.

156
00:08:30,250 --> 00:08:34,549
>> Rekursio estas tre potenca kaj ne
mencii eleganta, sed gxi povas esti

157
00:08:34,549 --> 00:08:38,010
malfacila koncepto je la komenco, tiel estu
pacienca kaj prenu vian tempon.

158
00:08:38,010 --> 00:08:39,370
Starti kun la baza kazo.

159
00:08:39,370 --> 00:08:42,650
Ĝi estas kutime la plej facila al identigi,
kaj tiam vi povas labori

160
00:08:42,650 --> 00:08:43,830
malantaŭen de tie.

161
00:08:43,830 --> 00:08:46,190
Vi scias, ke vi bezonas por atingi viajn
bazo kazo, tiel ke forteco

162
00:08:46,190 --> 00:08:47,760
doni al vi kelkajn aludojn.

163
00:08:47,760 --> 00:08:53,120
Provu esprimi unu specifa kazo en
terminoj de aliaj kazoj, aŭ en la sub-aroj.

164
00:08:53,120 --> 00:08:54,700
>> Dankon por rigardi ĉi mallonga.

165
00:08:54,700 --> 00:08:58,920
Almenaŭ, nun vi povas
kompreni ŝercoj kiel ĉi tio.

166
00:08:58,920 --> 00:09:01,250
Mia nomo estas Zamyla, kaj ĉi tiu estas cs50.

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

168
00:09:04,306 --> 00:09:07,170
>> Prenu ĉi funkcion, hi, a
void funkcio kiu prenas

169
00:09:07,170 --> 00:09:09,212
an int n, kiel enigo.

170
00:09:09,212 --> 00:09:11,020
La baza kazo venas unue.

171
00:09:11,020 --> 00:09:14,240
Se n estas malpli ol 0, presi
"Bye" kaj reveno.

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