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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Sabiex wieħed jifhem
recursion, inti għandek

3
00:00:10,190 --> 00:00:13,820
ewwel jifhmu recursion.

4
00:00:13,820 --> 00:00:17,280
Wara recursion fil-programm mezzi disinn
li inti għandek awto-referenzjali

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

6
00:00:18,570 --> 00:00:21,520
Strutturi ta 'dejta rikursivi, per eżempju,
huma strutturi ta 'dejta li

7
00:00:21,520 --> 00:00:23,990
jinkludu ruħhom
definizzjonijiet tagħhom.

8
00:00:23,990 --> 00:00:27,160
Imma llum, aħna qed tmur biex tiffoka
fuq funzjonijiet jirrikorri.

9
00:00:27,160 --> 00:00:31,160
>> Ifakkar li l-funzjonijiet tieħu inputs,
argumenti, u r-ritorn ta 'valur bħala tagħhom

10
00:00:31,160 --> 00:00:34,480
output rappreżentata minn
dan dijagramma hawn.

11
00:00:34,480 --> 00:00:38,060
Aħna ser jaħseb il-kaxxa bħala l-korp ta '
il-funzjoni, li jkun fih is-sett ta '

12
00:00:38,060 --> 00:00:42,340
istruzzjonijiet li tinterpreta l-
input u jipprovdu output.

13
00:00:42,340 --> 00:00:45,660
Teħid ħarsa aktar mill-qrib ġewwa l-korp ta '
il-funzjoni tista 'tikxef sejħiet għal

14
00:00:45,660 --> 00:00:47,430
funzjonijiet oħra kif ukoll.

15
00:00:47,430 --> 00:00:51,300
Ħu din il-funzjoni sempliċi, foo, li
tieħu string waħda bħala input u

16
00:00:51,300 --> 00:00:54,630
prints kemm ittri
li string għandha.

17
00:00:54,630 --> 00:00:58,490
Il strlen funzjoni, għat-tul string,
huwa msejjaħ, li l-output huwa

18
00:00:58,490 --> 00:01:01,890
meħtieġa għas-sejħa għall printf.

19
00:01:01,890 --> 00:01:05,770
>> Issa, dak li jagħmel funzjoni jirrikorri
speċjali huwa li jitlob huwa stess.

20
00:01:05,770 --> 00:01:09,610
Nistgħu jirrappreżenta dan rikursivi
sejħa ma 'dan vleġġa oranġjo

21
00:01:09,610 --> 00:01:11,360
looping lura għalih innifsu.

22
00:01:11,360 --> 00:01:15,630
Iżda eżekuzzjoni nnifisha mill-ġdid biss se
jagħmlu sejħa rikursivi ieħor, u

23
00:01:15,630 --> 00:01:17,150
ieħor u ieħor.

24
00:01:17,150 --> 00:01:19,100
Iżda funzjonijiet jirrikorri
ma tistax tkun infinita.

25
00:01:19,100 --> 00:01:23,490
Huma għandhom jispiċċaw b'xi, jew tiegħek
programm ser ikun għaddej għal dejjem.

26
00:01:23,490 --> 00:01:27,680
>> Għalhekk għandna bżonn li ssib mod biex jinkiser
barra tas-sejħiet repetuti.

27
00:01:27,680 --> 00:01:29,900
Aħna nsejħu dan il-każ bażi.

28
00:01:29,900 --> 00:01:33,570
Meta l-kundizzjoni każ bażi hija sodisfatta,
il-funzjoni lura mingħajr ma jagħmel

29
00:01:33,570 --> 00:01:34,950
sejħa jirrikorri ieħor.

30
00:01:34,950 --> 00:01:39,610
Ħu din il-funzjoni, hi, funzjoni null
li jieħu n int bħala input.

31
00:01:39,610 --> 00:01:41,260
Il-każ bażiku jiġi l-ewwel.

32
00:01:41,260 --> 00:01:46,220
Jekk n tkun inqas minn żero, bye print u
ritorn Għall-każijiet l-oħra, il-

33
00:01:46,220 --> 00:01:49,400
funzjoni se print hi u tesegwixxi
is-sejħa jirrikorri.

34
00:01:49,400 --> 00:01:53,600
Sejħa oħra għall-hi funzjoni ma '
valur input decremented.

35
00:01:53,600 --> 00:01:56,790
>> Issa, anke jekk aħna jistampaw hi, il-
funzjoni mhux se jtemm sakemm aħna

36
00:01:56,790 --> 00:02:00,370
ritorn tip ritorn tagħha,
f'dan il-każ nulli.

37
00:02:00,370 --> 00:02:04,830
Allura għal kull n minbarra l-każ bażi,
din hi funzjoni se terġa 'lura hi

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

39
00:02:06,890 --> 00:02:10,050
Peress li din il-funzjoni hija nulla għalkemm, aħna
mhux se tip b'mod espliċitu ritorn hawn.

40
00:02:10,050 --> 00:02:12,000
Aħna ser biss teżegwixxi l-funzjoni.

41
00:02:12,000 --> 00:02:16,960
Allura ssejjaħ hi (3) se print hi u
tesegwixxi hi (2) li tesegwixxi hi (1) wieħed

42
00:02:16,960 --> 00:02:20,560
li tesegwixxi hi (0), fejn il-
kundizzjoni każ bażi hija sodisfatta.

43
00:02:20,560 --> 00:02:24,100
Allura hi (0) prints bye u prospetti.

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

45
00:02:24,990 --> 00:02:28,690
Allura issa li aħna nifhmu l-baŜi ta '
funzjonijiet jirrikorri, li jkollhom bżonn

46
00:02:28,690 --> 00:02:32,730
inqas każ wieħed bażi kif ukoll
sejħa rikursivi, ejja jimxu fuq

47
00:02:32,730 --> 00:02:34,120
eżempju aktar sinifikanti.

48
00:02:34,120 --> 00:02:37,830
Wieħed li ma biss ritorn
null x'ikun.

49
00:02:37,830 --> 00:02:41,340
>> Ejja tagħti ħarsa lejn il-fatturi
operazzjoni aktar komunement użati fil-

50
00:02:41,340 --> 00:02:43,660
kalkoli probabbiltà.

51
00:02:43,660 --> 00:02:48,120
Fattorjali ta n huwa l-prodott ta 'kull
numru sħiħ pożittiv inqas minn

52
00:02:48,120 --> 00:02:49,400
u ugwali għal n.

53
00:02:49,400 --> 00:02:56,731
Ħamsa Allura factorial huwa 5 darbiet 4 darbiet
3 darbiet 2 darbiet 1 biex jagħtu 120.

54
00:02:56,731 --> 00:03:01,400
Erba factorial huwa 4 darbiet 3 darbiet
2 darbiet 1 biex jagħtu 24.

55
00:03:01,400 --> 00:03:04,910
U l-istess regola tapplika
għal kull numru sħiħ pożittiv.

56
00:03:04,910 --> 00:03:08,670
>> Allura kif tista aħna jiktbu rikursivi
funzjoni li tikkalkula l-fatturi

57
00:03:08,670 --> 00:03:09,960
ta 'numru?

58
00:03:09,960 --> 00:03:14,700
Well, aħna ser bżonn biex tidentifika kemm il-
każ bażi u s-sejħa rikursiv.

59
00:03:14,700 --> 00:03:18,250
Is-sejħa jirrikorri se jkun l-istess
għall-każijiet kollha ħlief għall-bażi

60
00:03:18,250 --> 00:03:21,420
każ, li jfisser li aħna ser ikollhom
isibu disinn li se tagħtina tagħna

61
00:03:21,420 --> 00:03:23,350
riżultat mixtieq.

62
00:03:23,350 --> 00:03:30,270
>> Għal dan l-eżempju, tara kif 5 fattorjali
tinvolvi multiplikazzjoni 4 bi 3 bi 2 minn 1

63
00:03:30,270 --> 00:03:33,010
U li ħafna istess multiplikazzjoni
jinstab hawnhekk, il-

64
00:03:33,010 --> 00:03:35,430
definizzjoni ta '4 fattorjali.

65
00:03:35,430 --> 00:03:39,810
Allura naraw li 5 fattorjali hija
biss 5 darbiet 4 fattorjali.

66
00:03:39,810 --> 00:03:43,360
Issa ma japplikax dan il-mudell
għal 4 fatturi kif ukoll?

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

68
00:03:44,280 --> 00:03:49,120
Naraw li 4 fattorjali fiha l-
multiplikazzjoni 3 darbiet 2 darbiet 1, l-

69
00:03:49,120 --> 00:03:51,590
ħafna istess definizzjoni 3 fattorjali.

70
00:03:51,590 --> 00:03:56,950
Allura 4 fattorjali huwa ugwali għal 4 darbiet 3
fatturi, u hekk u ibqa 'sejjer hekk tagħna

71
00:03:56,950 --> 00:04:02,170
mudell bsaten sa l-1 fatturi, li
b'definizzjoni huwa ugwali għal 1.

72
00:04:02,170 --> 00:04:04,950
>> M'hemm l-ebda pożittiv ieħor
interi xellug.

73
00:04:04,950 --> 00:04:07,870
Allura aħna għandna l-mudell għall-
sejħa jirrikorri tagħna.

74
00:04:07,870 --> 00:04:13,260
n fatturi hija ugwali għal n darbiet
l fattorjali ta n minus 1.

75
00:04:13,260 --> 00:04:14,370
U l-każ bażi tagħna?

76
00:04:14,370 --> 00:04:17,370
Li ser jkun biss definizzjoni tagħna
tal-1 fattorjali.

77
00:04:17,370 --> 00:04:19,995
>> Allura issa nistgħu jimxu fuq kitba
kodiċi għall-funzjoni.

78
00:04:19,995 --> 00:04:24,110
Għall-każ bażiku, aħna ser ikollhom l-
kundizzjoni n ugwali daqs 1, fejn

79
00:04:24,110 --> 00:04:25,780
aħna ser terġa 'lura 1.

80
00:04:25,780 --> 00:04:29,280
Mbagħad jimxu fuq il-call rikursivi,
aħna ser jirritorna n darbiet l-

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

82
00:04:32,180 --> 00:04:33,590
>> Issa ejja test ta 'dan tagħna.

83
00:04:33,590 --> 00:04:35,900
Ejja nippruvaw fattorjali 4.

84
00:04:35,900 --> 00:04:39,420
Per funzjoni tagħna huwa ugwali
4 darbiet fattorjali (3).

85
00:04:39,420 --> 00:04:43,040
Fattorjali (3) hija ugwali għal
3 darbiet fattorjali (2).

86
00:04:43,040 --> 00:04:48,700
Fattorjali (2) hija ugwali għal 2 darbiet
fattorjali (1), li jirritorna 1.

87
00:04:48,700 --> 00:04:52,490
Fattorjali (2) issa prospetti 2 darbiet 1, 2.

88
00:04:52,490 --> 00:04:55,960
Fattorjali (3) issa jistgħu jirritornaw
3 darbiet 2, 6.

89
00:04:55,960 --> 00:05:02,490
U fl-aħħarnett, fattorjali (4)
prospetti 4 darbiet 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Jekk int jiltaqgħu kull diffikultà
mas-sejħa rikursivi, nippretendu li

91
00:05:06,780 --> 00:05:09,660
il-funzjoni xogħlijiet diġà.

92
00:05:09,660 --> 00:05:13,450
What I jfisser minn dan hija li għandek
fiduċja sejħiet jirrikorri tiegħek li tirritorna

93
00:05:13,450 --> 00:05:15,100
il-valuri dritt.

94
00:05:15,100 --> 00:05:18,960
Per eżempju, jekk naf li
fattorjali (5) huwa daqs 5 darbiet

95
00:05:18,960 --> 00:05:24,870
fattorjali (4), jien ser fiduċja li
fattorjali (4) se jagħti me 24.

96
00:05:24,870 --> 00:05:28,510
Jaħsbu li bħala varjabbli, jekk inti
, sa jekk inti diġà definiti

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

98
00:05:30,070 --> 00:05:33,850
Allura għal kull fattorjali (n), huwa
il-prodott ta 'nu

99
00:05:33,850 --> 00:05:35,360
il-fatturi ta 'qabel.

100
00:05:35,360 --> 00:05:38,130
U dan fatturi preċedenti
jinkiseb billi ċċempel

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

102
00:05:41,330 --> 00:05:45,130
>> Issa, ara jekk inti tista 'timplimenta
rikursivi jiffunzjonaw yourself.

103
00:05:45,130 --> 00:05:50,490
Tagħbija up terminal tiegħek, jew run.cs50.net,
u jiktbu somma funzjoni

104
00:05:50,490 --> 00:05:54,770
li jieħu n integer u jirritorna l-
somma ta 'kollha pożittivi konsekuttivi

105
00:05:54,770 --> 00:05:57,490
interi minn n għal 1.

106
00:05:57,490 --> 00:06:01,000
Stajt miktub s-somom ta 'xi
Valuri biex jgħinuk tagħna.

107
00:06:01,000 --> 00:06:04,030
L-ewwel, insemmu l-
kundizzjoni każ bażi.

108
00:06:04,030 --> 00:06:06,170
Imbagħad, tħares lejn is-somma (5).

109
00:06:06,170 --> 00:06:09,270
Tista jesprimuha f'termini
ta 'somma ieħor?

110
00:06:09,270 --> 00:06:11,290
Issa, dak dwar is-somma (4)?

111
00:06:11,290 --> 00:06:15,630
Kif tista 'tesprimi somma (4)
f'termini ta 'ammont ieħor?

112
00:06:15,630 --> 00:06:19,655
>> Ladarba inti tkun somma (5) u somma (4)
espressa f'termini ta 'ammonti oħrajn, ara

113
00:06:19,655 --> 00:06:22,970
jekk inti tista 'tidentifika
mudell għal somma (n).

114
00:06:22,970 --> 00:06:26,190
Jekk le, ipprova numri oħra ftit
u jesprimu somom tagħhom

115
00:06:26,190 --> 00:06:28,410
f'termini ta 'għadd ieħor.

116
00:06:28,410 --> 00:06:31,930
Billi jiġu identifikati xejriet għall diskreti
numri, int ukoll fuq tiegħek mod biex

117
00:06:31,930 --> 00:06:34,320
tidentifika l-mudell għal kull n.

118
00:06:34,320 --> 00:06:38,040
>> Recursion huwa għodda verament b'saħħtu,
hekk naturalment huwa mhux limitati għal

119
00:06:38,040 --> 00:06:39,820
funzjonijiet matematiċi.

120
00:06:39,820 --> 00:06:44,040
Recursion jistgħu jintużaw b'mod effettiv ħafna
meta jittrattaw siġar per eżempju.

121
00:06:44,040 --> 00:06:47,210
Iċċekkja l-qasir fuq siġar għal
reviżjoni aktar bir-reqqa, iżda għal issa

122
00:06:47,210 --> 00:06:51,140
ifakkar li s-siġar tat-tiftix binarju, b'mod
partikolari, huma magħmula minn għoqiedi, kull

123
00:06:51,140 --> 00:06:53,820
b'valur u żewġ pointers node.

124
00:06:53,820 --> 00:06:57,270
Normalment, dan huwa rappreżentat mill-
node ġenitur li jkollu linja tipponta waħda

125
00:06:57,270 --> 00:07:01,870
l-node wild xellug u wieħed
l-node wild dritt.

126
00:07:01,870 --> 00:07:04,510
L-istruttura ta 'tfittxija binarja
siġra jippresta ruħu tajjeb

127
00:07:04,510 --> 00:07:05,940
għal tfittxija rikursiv.

128
00:07:05,940 --> 00:07:09,730
Is-sejħa jirrikorri jew għaddew fil-
xellug jew il-node dritt, iżda aktar

129
00:07:09,730 --> 00:07:10,950
ta 'dik fil-qosor siġra.

130
00:07:10,950 --> 00:07:15,690
>> Tgħid li inti tixtieq li twettaq operazzjoni fuq
kull node wieħed fil-siġra binarju.

131
00:07:15,690 --> 00:07:17,410
Kif tista 'inti tmur dwar dan?

132
00:07:17,410 --> 00:07:20,600
Ukoll, inti tista 'tikteb rikursivi
funzjoni li jwettaq l-operazzjoni

133
00:07:20,600 --> 00:07:24,450
fuq il-node ġenitur u jagħmel rikursivi
jiġbdu l-istess funzjoni,

134
00:07:24,450 --> 00:07:27,630
tgħaddi fil-xellug u
lymph tfal dritt.

135
00:07:27,630 --> 00:07:31,650
Per eżempju, din il-funzjoni, foo, li
bidliet l-valur ta 'node partikolari u

136
00:07:31,650 --> 00:07:33,830
kollha tat-tfal tagħha lill 1.

137
00:07:33,830 --> 00:07:37,400
Il-xenarju bażi ta 'xi kawżi glandoli nulla
il-funzjoni li jirritornaw, li jindika

138
00:07:37,400 --> 00:07:41,290
li ma jkunx hemm xi nodes
xellug f'dak is-siġra.

139
00:07:41,290 --> 00:07:42,620
>> Ejja jimxu permezz tiegħu.

140
00:07:42,620 --> 00:07:44,340
L-ewwel ġenitur huwa 13.

141
00:07:44,340 --> 00:07:47,930
Aħna jibdlu l-valur għal 1, u mbagħad is-sejħa
funzjoni tagħna fuq ix-xellug kif ukoll

142
00:07:47,930 --> 00:07:49,600
id-dritt.

143
00:07:49,600 --> 00:07:53,910
Il-funzjoni, foo, tissejjaħ fuq ix-xellug
ewwel sub-siġra, hekk l-node xellug

144
00:07:53,910 --> 00:07:57,730
se jkunu assenjati għal 1 u foo se
jiġi msejjaħ fuq it-tfal li node, il-

145
00:07:57,730 --> 00:08:01,900
ewwel ix-xellug u mbagħad il-lemin,
u hekk u ibqa 'sejjer hekk.

146
00:08:01,900 --> 00:08:05,630
U jgħidulhom li l-fergħat m'għandhomx
kwalunkwe aktar tfal sabiex l-istess proċess

147
00:08:05,630 --> 00:08:09,700
se tkompli għat-tfal dritt
sakemm nodes-siġra kollha huma

148
00:08:09,700 --> 00:08:11,430
mibgħut għal 1.

149
00:08:11,430 --> 00:08:15,390
>> Kif tistgħu taraw, inti mhux limitati
għal wieħed biss sejħa rikursiv.

150
00:08:15,390 --> 00:08:17,930
Just kemm se x-xogħol isir.

151
00:08:17,930 --> 00:08:21,200
X'jiġri jekk kellek siġra fejn kull
node kellhom tlett itfal,

152
00:08:21,200 --> 00:08:23,100
Xellug, tan-nofs, u d-dritt?

153
00:08:23,100 --> 00:08:24,886
Kif inti jeditjaw foo?

154
00:08:24,886 --> 00:08:25,860
Well, sempliċi.

155
00:08:25,860 --> 00:08:30,250
Just żid sejħa rikursivi ieħor u
jgħaddu fil-pointer node nofs.

156
00:08:30,250 --> 00:08:34,549
>> Recursion hija qawwija ħafna u li ma
nsemmux eleganti, imma tista 'tkun

157
00:08:34,549 --> 00:08:38,010
kunċett diffiċli għall-ewwel, sabiex ikunu
pazjent u jieħdu ħin tiegħek.

158
00:08:38,010 --> 00:08:39,370
Tibda bil-każ bażi.

159
00:08:39,370 --> 00:08:42,650
Huwa ġeneralment l-eħfef biex jidentifikaw,
u allura inti tista 'taħdem

160
00:08:42,650 --> 00:08:43,830
lura minn hemm.

161
00:08:43,830 --> 00:08:46,190
Inti taf li għandek bżonn biex tilħaq tiegħek
każ ta 'bażi, sabiex sitwazzjoni tista

162
00:08:46,190 --> 00:08:47,760
jagħtuk ftit ideat.

163
00:08:47,760 --> 00:08:53,120
Ipprova jesprimu każ speċifiku wieħed
F'termini ta 'każijiet l-oħra, jew sub-settijiet.

164
00:08:53,120 --> 00:08:54,700
>> Grazzi għall-ħars dan qasir.

165
00:08:54,700 --> 00:08:58,920
Għall-inqas, issa tista '
jifhmu ċajt bħal dan.

166
00:08:58,920 --> 00:09:01,250
Jisimni Zamyla, u dan huwa cs50.

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

168
00:09:04,306 --> 00:09:07,170
>> Ħu din il-funzjoni, hi, a
funzjoni null li jieħu

169
00:09:07,170 --> 00:09:09,212
ta int, n, bħala input.

170
00:09:09,212 --> 00:09:11,020
Il-każ bażiku jiġi l-ewwel.

171
00:09:11,020 --> 00:09:14,240
Jekk n tkun inqas minn 0, print
"Bye" u r-ritorn.

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