>> ZAMYLA: Sabiex wieħed jifhem recursion, inti għandek
ewwel jifhmu recursion.
Wara recursion fil-programm mezzi disinn li inti għandek awto-referenzjali
definizzjonijiet.
Strutturi ta 'dejta rikursivi, per eżempju, huma strutturi ta 'dejta li
jinkludu ruħhom definizzjonijiet tagħhom.
Imma llum, aħna qed tmur biex tiffoka fuq funzjonijiet jirrikorri.
>> Ifakkar li l-funzjonijiet tieħu inputs, argumenti, u r-ritorn ta 'valur bħala tagħhom
output rappreżentata minn dan dijagramma hawn.
Aħna ser jaħseb il-kaxxa bħala l-korp ta ' il-funzjoni, li jkun fih is-sett ta '
istruzzjonijiet li tinterpreta l- input u jipprovdu output.
Teħid ħarsa aktar mill-qrib ġewwa l-korp ta ' il-funzjoni tista 'tikxef sejħiet għal
funzjonijiet oħra kif ukoll.
Ħu din il-funzjoni sempliċi, foo, li tieħu string waħda bħala input u
prints kemm ittri li string għandha.
Il strlen funzjoni, għat-tul string, huwa msejjaħ, li l-output huwa
meħtieġa għas-sejħa għall printf.
>> Issa, dak li jagħmel funzjoni jirrikorri speċjali huwa li jitlob huwa stess.
Nistgħu jirrappreżenta dan rikursivi sejħa ma 'dan vleġġa oranġjo
looping lura għalih innifsu.
Iżda eżekuzzjoni nnifisha mill-ġdid biss se jagħmlu sejħa rikursivi ieħor, u
ieħor u ieħor.
Iżda funzjonijiet jirrikorri ma tistax tkun infinita.
Huma għandhom jispiċċaw b'xi, jew tiegħek programm ser ikun għaddej għal dejjem.
>> Għalhekk għandna bżonn li ssib mod biex jinkiser barra tas-sejħiet repetuti.
Aħna nsejħu dan il-każ bażi.
Meta l-kundizzjoni każ bażi hija sodisfatta, il-funzjoni lura mingħajr ma jagħmel
sejħa jirrikorri ieħor.
Ħu din il-funzjoni, hi, funzjoni null li jieħu n int bħala input.
Il-każ bażiku jiġi l-ewwel.
Jekk n tkun inqas minn żero, bye print u ritorn Għall-każijiet l-oħra, il-
funzjoni se print hi u tesegwixxi is-sejħa jirrikorri.
Sejħa oħra għall-hi funzjoni ma ' valur input decremented.
>> Issa, anke jekk aħna jistampaw hi, il- funzjoni mhux se jtemm sakemm aħna
ritorn tip ritorn tagħha, f'dan il-każ nulli.
Allura għal kull n minbarra l-każ bażi, din hi funzjoni se terġa 'lura hi
ta 'n minus 1.
Peress li din il-funzjoni hija nulla għalkemm, aħna mhux se tip b'mod espliċitu ritorn hawn.
Aħna ser biss teżegwixxi l-funzjoni.
Allura ssejjaħ hi (3) se print hi u tesegwixxi hi (2) li tesegwixxi hi (1) wieħed
li tesegwixxi hi (0), fejn il- kundizzjoni każ bażi hija sodisfatta.
Allura hi (0) prints bye u prospetti.
>> OK.
Allura issa li aħna nifhmu l-baŜi ta ' funzjonijiet jirrikorri, li jkollhom bżonn
inqas każ wieħed bażi kif ukoll sejħa rikursivi, ejja jimxu fuq
eżempju aktar sinifikanti.
Wieħed li ma biss ritorn null x'ikun.
>> Ejja tagħti ħarsa lejn il-fatturi operazzjoni aktar komunement użati fil-
kalkoli probabbiltà.
Fattorjali ta n huwa l-prodott ta 'kull numru sħiħ pożittiv inqas minn
u ugwali għal n.
Ħamsa Allura factorial huwa 5 darbiet 4 darbiet 3 darbiet 2 darbiet 1 biex jagħtu 120.
Erba factorial huwa 4 darbiet 3 darbiet 2 darbiet 1 biex jagħtu 24.
U l-istess regola tapplika għal kull numru sħiħ pożittiv.
>> Allura kif tista aħna jiktbu rikursivi funzjoni li tikkalkula l-fatturi
ta 'numru?
Well, aħna ser bżonn biex tidentifika kemm il- każ bażi u s-sejħa rikursiv.
Is-sejħa jirrikorri se jkun l-istess għall-każijiet kollha ħlief għall-bażi
każ, li jfisser li aħna ser ikollhom isibu disinn li se tagħtina tagħna
riżultat mixtieq.
>> Għal dan l-eżempju, tara kif 5 fattorjali tinvolvi multiplikazzjoni 4 bi 3 bi 2 minn 1
U li ħafna istess multiplikazzjoni jinstab hawnhekk, il-
definizzjoni ta '4 fattorjali.
Allura naraw li 5 fattorjali hija biss 5 darbiet 4 fattorjali.
Issa ma japplikax dan il-mudell għal 4 fatturi kif ukoll?
Iva.
Naraw li 4 fattorjali fiha l- multiplikazzjoni 3 darbiet 2 darbiet 1, l-
ħafna istess definizzjoni 3 fattorjali.
Allura 4 fattorjali huwa ugwali għal 4 darbiet 3 fatturi, u hekk u ibqa 'sejjer hekk tagħna
mudell bsaten sa l-1 fatturi, li b'definizzjoni huwa ugwali għal 1.
>> M'hemm l-ebda pożittiv ieħor interi xellug.
Allura aħna għandna l-mudell għall- sejħa jirrikorri tagħna.
n fatturi hija ugwali għal n darbiet l fattorjali ta n minus 1.
U l-każ bażi tagħna?
Li ser jkun biss definizzjoni tagħna tal-1 fattorjali.
>> Allura issa nistgħu jimxu fuq kitba kodiċi għall-funzjoni.
Għall-każ bażiku, aħna ser ikollhom l- kundizzjoni n ugwali daqs 1, fejn
aħna ser terġa 'lura 1.
Mbagħad jimxu fuq il-call rikursivi, aħna ser jirritorna n darbiet l-
fattorjali ta n minus 1.
>> Issa ejja test ta 'dan tagħna.
Ejja nippruvaw fattorjali 4.
Per funzjoni tagħna huwa ugwali 4 darbiet fattorjali (3).
Fattorjali (3) hija ugwali għal 3 darbiet fattorjali (2).
Fattorjali (2) hija ugwali għal 2 darbiet fattorjali (1), li jirritorna 1.
Fattorjali (2) issa prospetti 2 darbiet 1, 2.
Fattorjali (3) issa jistgħu jirritornaw 3 darbiet 2, 6.
U fl-aħħarnett, fattorjali (4) prospetti 4 darbiet 6, 24.
>> Jekk int jiltaqgħu kull diffikultà mas-sejħa rikursivi, nippretendu li
il-funzjoni xogħlijiet diġà.
What I jfisser minn dan hija li għandek fiduċja sejħiet jirrikorri tiegħek li tirritorna
il-valuri dritt.
Per eżempju, jekk naf li fattorjali (5) huwa daqs 5 darbiet
fattorjali (4), jien ser fiduċja li fattorjali (4) se jagħti me 24.
Jaħsbu li bħala varjabbli, jekk inti , sa jekk inti diġà definiti
fattorjali (4).
Allura għal kull fattorjali (n), huwa il-prodott ta 'nu
il-fatturi ta 'qabel.
U dan fatturi preċedenti jinkiseb billi ċċempel
fattorjali ta n minus 1.
>> Issa, ara jekk inti tista 'timplimenta rikursivi jiffunzjonaw yourself.
Tagħbija up terminal tiegħek, jew run.cs50.net, u jiktbu somma funzjoni
li jieħu n integer u jirritorna l- somma ta 'kollha pożittivi konsekuttivi
interi minn n għal 1.
Stajt miktub s-somom ta 'xi Valuri biex jgħinuk tagħna.
L-ewwel, insemmu l- kundizzjoni każ bażi.
Imbagħad, tħares lejn is-somma (5).
Tista jesprimuha f'termini ta 'somma ieħor?
Issa, dak dwar is-somma (4)?
Kif tista 'tesprimi somma (4) f'termini ta 'ammont ieħor?
>> Ladarba inti tkun somma (5) u somma (4) espressa f'termini ta 'ammonti oħrajn, ara
jekk inti tista 'tidentifika mudell għal somma (n).
Jekk le, ipprova numri oħra ftit u jesprimu somom tagħhom
f'termini ta 'għadd ieħor.
Billi jiġu identifikati xejriet għall diskreti numri, int ukoll fuq tiegħek mod biex
tidentifika l-mudell għal kull n.
>> Recursion huwa għodda verament b'saħħtu, hekk naturalment huwa mhux limitati għal
funzjonijiet matematiċi.
Recursion jistgħu jintużaw b'mod effettiv ħafna meta jittrattaw siġar per eżempju.
Iċċekkja l-qasir fuq siġar għal reviżjoni aktar bir-reqqa, iżda għal issa
ifakkar li s-siġar tat-tiftix binarju, b'mod partikolari, huma magħmula minn għoqiedi, kull
b'valur u żewġ pointers node.
Normalment, dan huwa rappreżentat mill- node ġenitur li jkollu linja tipponta waħda
l-node wild xellug u wieħed l-node wild dritt.
L-istruttura ta 'tfittxija binarja siġra jippresta ruħu tajjeb
għal tfittxija rikursiv.
Is-sejħa jirrikorri jew għaddew fil- xellug jew il-node dritt, iżda aktar
ta 'dik fil-qosor siġra.
>> Tgħid li inti tixtieq li twettaq operazzjoni fuq kull node wieħed fil-siġra binarju.
Kif tista 'inti tmur dwar dan?
Ukoll, inti tista 'tikteb rikursivi funzjoni li jwettaq l-operazzjoni
fuq il-node ġenitur u jagħmel rikursivi jiġbdu l-istess funzjoni,
tgħaddi fil-xellug u lymph tfal dritt.
Per eżempju, din il-funzjoni, foo, li bidliet l-valur ta 'node partikolari u
kollha tat-tfal tagħha lill 1.
Il-xenarju bażi ta 'xi kawżi glandoli nulla il-funzjoni li jirritornaw, li jindika
li ma jkunx hemm xi nodes xellug f'dak is-siġra.
>> Ejja jimxu permezz tiegħu.
L-ewwel ġenitur huwa 13.
Aħna jibdlu l-valur għal 1, u mbagħad is-sejħa funzjoni tagħna fuq ix-xellug kif ukoll
id-dritt.
Il-funzjoni, foo, tissejjaħ fuq ix-xellug ewwel sub-siġra, hekk l-node xellug
se jkunu assenjati għal 1 u foo se jiġi msejjaħ fuq it-tfal li node, il-
ewwel ix-xellug u mbagħad il-lemin, u hekk u ibqa 'sejjer hekk.
U jgħidulhom li l-fergħat m'għandhomx kwalunkwe aktar tfal sabiex l-istess proċess
se tkompli għat-tfal dritt sakemm nodes-siġra kollha huma
mibgħut għal 1.
>> Kif tistgħu taraw, inti mhux limitati għal wieħed biss sejħa rikursiv.
Just kemm se x-xogħol isir.
X'jiġri jekk kellek siġra fejn kull node kellhom tlett itfal,
Xellug, tan-nofs, u d-dritt?
Kif inti jeditjaw foo?
Well, sempliċi.
Just żid sejħa rikursivi ieħor u jgħaddu fil-pointer node nofs.
>> Recursion hija qawwija ħafna u li ma nsemmux eleganti, imma tista 'tkun
kunċett diffiċli għall-ewwel, sabiex ikunu pazjent u jieħdu ħin tiegħek.
Tibda bil-każ bażi.
Huwa ġeneralment l-eħfef biex jidentifikaw, u allura inti tista 'taħdem
lura minn hemm.
Inti taf li għandek bżonn biex tilħaq tiegħek każ ta 'bażi, sabiex sitwazzjoni tista
jagħtuk ftit ideat.
Ipprova jesprimu każ speċifiku wieħed F'termini ta 'każijiet l-oħra, jew sub-settijiet.
>> Grazzi għall-ħars dan qasir.
Għall-inqas, issa tista ' jifhmu ċajt bħal dan.
Jisimni Zamyla, u dan huwa cs50.
>> Ħu din il-funzjoni, hi, a funzjoni null li jieħu
ta int, n, bħala input.
Il-każ bażiku jiġi l-ewwel.
Jekk n tkun inqas minn 0, print "Bye" u r-ritorn.