>> ZAMYLA: Siekiant suprasti rekursija, turite
pirmiausia suprasti rekursija.
Atsižvelgdama rekursija programų kūrimo priemones kad jūs turite nuorodų į save
apibrėžimai.
Rekursinės duomenų struktūras, pavyzdžiui, yra duomenų struktūros,
įtraukti save jų apibrėžimai.
Tačiau šiandien mes ketiname sutelkti ant rekursyvinių funkcijas.
>> Prisiminkite, kad funkcijos imtis įėjimai, argumentus ir grąžina reikšmę, nes jų
išėjimo atstovaujamos tai schema čia.
Mes manote dėžutės kaip kūno funkcija, kuriame yra nustatyti
nurodymai, interpretuoti įvesties ir pateikti rezultatus.
Atidžiau pažvelgti viduje kūno funkcija gali atskleisti skambučius
kitas funkcijas, taip pat.
Paimkite šį paprastą funkciją foo, kad užima vieną eilutę kaip įvesties ir
spausdina kiek raidžių kad eilutė yra.
Funkcija strlen, styginių ilgio, vadinamas, kurio išėjimas yra
reikalingas su printf skambutį.
>> Dabar, ką daro rekursinį funkciją ypatinga tuo, kad ji save vadina.
Mes galime atstovauti šiam rekursyvūs skambinti šiuo oranžinė rodyklė
apsisukimo atgal į save.
Bet vykdyti pati vėl bus tik atlikti kitą rekursinį skambutį, ir
kitą, ir kitą.
Bet rekursyvūs funkcijos negali būti begalinis.
Jie turi baigtis kažkaip, arba savo programa bus amžinai.
>> Taigi mums reikia rasti būdą, kaip sulaužyti iš grįžtamojo skambučius.
Mes tai vadiname bazinį scenarijų.
Kai bazinį scenarijų sąlyga yra įvykdyta, Funkcija grąžina nedarant
kitas grįžtamojo skambutis.
Pasinaudokite šia funkcija, hi, tuštumą Function kad mano int n, kaip įvestį.
Bazinį scenarijų ateina pirmiausia.
Jei n yra mažesnis už nulį, spausdinti bye ir grįžti Visais kitais atvejais,
funkcija spausdinti aukštųjų ir vykdyti rekursinis skambutis.
Kitas skambutis funkcija hi su decremented įvesties vertė.
>> Dabar, nors mes spausdinti Sveiki, funkcija nebus nutraukti, kol mes
grįžti savo grįžimo tipo, šiuo atveju negalioja.
Taigi, kas n Asmenys, kiti nei bazinė atveju ši funkcija hi grįš hi
n atėmus 1.
Kadangi ši funkcija yra niekinis, nors mes nebus aiškiai įrašykite grįžti čia.
Mes tik atlikti funkciją.
Taigi skambina hi (3) bus atspausdinti aukštųjų ir vykdyti hi (2), kuris vykdo hi (1) vienas
kuris vykdo Hi (0), kur bazinį scenarijų sąlyga yra įvykdyta.
Taigi, labas (0) spausdina bye ir grįžta.
>> Gerai.
Taigi dabar, kad mes suprantame pagrindai rekursyvūs funkcijas, kad jie turi
bent vieną bazinį scenarijų, taip pat grįžtamojo ryšio, pereikime prie
prasmingesnis pavyzdys.
Vienas, kad ne tik grįžti negalioja, nesvarbu koks.
>> Leiskite pažvelgti į faktorialas atrodo operacija naudojama dažniausiai
tikimybiniai skaičiavimai.
Faktorinė n yra kiekvienas produktas teigiamas sveikasis skaičius mažesnis negu
ir lygus n.
Taigi faktorinė penki yra 5 kartus 4 kartus 3 kartus 2 kartus 1 duoti 120.
Keturi faktorialas yra 4 kartus 3 kartus 2 kartus 1 duoti 24.
Ir taikoma ta pati taisyklė bet teigiamas sveikasis skaičius.
>> Taigi, kaip gali mes rašome rekursinį funkcija, kuri apskaičiuoja faktorialas
iš skaičių?
Na, mes turime nustatyti tiek bazinį scenarijų ir grįžtamojo skambutis.
Rekursinis skambutis bus tas pats visais atvejais, išskyrus pagrindo
atvejis, kuris reiškia, kad mes turime rasti modelį, kuris suteiks mums mūsų
norimas rezultatas.
>> Šiame pavyzdyje matyti, kaip 5 faktorialas apima dauginant 4 3 2 iki 1
Ir kad tą pačią daugyba randamas čia
apibrėžimas 4 faktorialas.
Taigi matome, kad 5 faktorialas yra vos 5 kartus 4 faktorialas.
Dabar ji šis modelis taikomas iki 4 Faktorinė taip pat?
Taip.
Mes matome, kad 4 faktorialas yra dauginimo 3 kartus 2 kartus 1,
Pačią apibrėžimas 3 faktorialas.
Taigi 4 faktorialas yra lygus 4 kartus 3 faktorialas, ir tt ir tt mūsų
modelis lazdos iki 1 faktorialas, kuris pagal apibrėžimą yra lygi 1.
>> Nėra kitų teigiamų sveikieji skaičiai liko.
Taigi, mes turime už raštą mūsų rekursinis skambutis.
n faktorialas yra lygus n kartų n faktorialas minus 1.
Ir mūsų bazinį scenarijų?
Tai bus tiesiog mūsų apibrėžimas 1 faktorialas.
>> Taigi dabar mes galime judėti į raštu kodas funkcija.
Dėl pagrindo atveju, mes turime sąlyga n lygu lygu 1, jei
mes grąžinsime 1.
Tada keliasi į grįžtamojo ryšio metu, mes grąžinsime n kartų
faktorialas n atėmus 1.
>> Dabar galime išbandyti šią mūsų.
Pabandykime faktorialas 4.
Už mūsų funkcija tai lygūs iki 4 kartų faktorialas (3).
Faktorinė (3) yra lygi 3 kartus faktorialas (2).
Faktorinė (2) yra lygus 2 kartus faktorialas (1), kuri grąžina 1.
Faktorinė (2) dabar grąžina 2 kartus 1, 2.
Faktorinė (3) dabar gali grįžti 3 kartus 2, 6.
Ir, pagaliau, faktorialas (4) grąžina 4 kartus 6, 24.
>> Jei iškyla kokių nors sunkumų su grįžtamojo ryšio metu, apsimesti, kad
funkcija veikia jau.
Ką reiškia tai, kad jums reikia pasitikėti savo rekursinių skambučius grąžinti
teisingas vertybes.
Pavyzdžiui, jei aš žinau, kad faktorialas (5) lygu 5 kartus
faktorialas (4), aš tikėti, kad faktorialas (4) duos man 24.
Pagalvokite apie tai, kaip kintamasis, jei bus, nes jei jau apibrėžta
faktorialas (4).
Taigi bet faktorialas (n), tai n produktas ir
ankstesnis faktorialas.
Ir tai praėjusią faktorialas gaunamas telefonu
faktorialas n atėmus 1.
>> Dabar, pamatyti, jei jūs galite įgyvendinti rekursywny veikti patys.
Įdėkite savo terminalą, arba run.cs50.net, ir parašyti funkciją SUM
kad užima sveikasis skaičius n ir grąžina suma visų iš eilės teigiamas
sveikieji skaičiai nuo n iki 1.
Aš parašiau dėmesį į kai sumas vertes, kad padėtų jums mūsų.
Pirma, išsiaiškinti, bazinį scenarijų sąlyga.
Tada pažvelgti sumos (5).
Galite išreikšti tai pagal kitos sumos?
Dabar, ką apie sumą (4)?
Kaip jūs galite išreikšti sumą (4) kalbant apie kitą sumą?
>> Kai jūs turite sumą (5), ir suma (4) išreikšta kitomis sumomis, žr
jei jūs galite nustatyti raštas sumos (n).
Jei ne, pabandykite keletą kitų numerius ir išreikšti savo pinigų sumas
terminai dar numerius.
Nustatant modelius savarankiška numeriai, jums gerai jūsų būdas
nustatyti už bet n modelis.
>> Rekursija yra tikrai galingas įrankis, todėl, žinoma, tai ne tik
matematinės funkcijos.
Rekursija gali būti naudojama labai efektyviai kai sprendžiami su medžių, pavyzdžiui,.
Patikrinkite medelių trumpas daugiau kruopščiai peržiūrėti, bet dabar
priminti, kad dvejetainius paieškos medžius, į pirma, yra sudaryta iš mazgų, kiekvienas
su vertės ir dviejų mazgų rodyklės.
Paprastai tai yra atstovaujama tėvų mazgas turintis vieną eilutę nukreipta
į kairę vaikų mazgas ir vienas į tinkamą vaikų mazgas.
Iš dvejetainis paieškos struktūra medis skolina pati gerai
į grįžtamojo paiešką.
Rekursinis skambutis arba eina kairę arba į dešinę mazgas, bet daugiau
to medžio trumpas.
>> Tarkime, jūs norite atlikti operaciją kiekvienas mazgas dvejetainiu medžiu.
Kaip gali jums eiti apie tai?
Na, jums gali rašyti rekursinį funkcija, kuri atlieka operaciją
patronuojančiai mazgas ir daro rekursyvūs paskambinti į tą pačią funkciją,
einančios į kairę ir dešinysis vaikų mazgai.
Pavyzdžiui, ši funkcija, rūšys, kad keičia tam tikro mazgo vertę ir
visus savo vaikus į 1.
Bazine null mazgas priežasčių Funkcija grąžina, nurodant
kad nėra jokių mazgų liko toje sub-tree.
>> Leiskite vaikščioti per ją.
Pirmasis iš tėvų yra 13.
Mes pakeisti reikšmę į 1, ir tada skambinti mūsų funkcija kairėje, taip pat
kaip gerai.
Funkcija, rūšys, vadinamas kairėje sub-tree pirmas, todėl kairėje mazgas
bus iš naujo 1 ir foo bus būti paprašyta Šis mazgas vaikų,
pirmas į kairę ir tada į dešinę, ir taip toliau ir taip toliau.
Ir pasakykite jiems, kad filialai neturi bet daugiau vaikų, kad pats procesas
toliau už teisę vaikams kol visą medį mazgai yra
paskiriamas į 1.
>> Kaip matote, jūs ne tik tik vienas grįžtamojo skambutis.
Tiesiog kiek gaus darbą.
Ką daryti, jei jūs turėjote medį, kur kiekvienas mazgas turėjo tris vaikus,
Kairysis, vidurinis ir dešinysis?
Kaip redaguoti foo?
Na, paprasta.
Tiesiog pridėkite kitą rekursinį skambutį ir pereiti į vidurį mazgas žymeklis.
>> Rekursija yra labai galingas ir ne paminėti elegantiškas, bet jis gali būti
sudėtinga sąvoka ne pirmas, todėl pacientui ir imtis savo laiką.
Pradėti su bazine.
Tai paprastai lengviausia nustatyti, ir tada jūs galite dirbti
atgal iš ten.
Jūs žinote, jums reikia pasiekti savo pagrindą, idant
duoti jums keletą patarimų.
Stenkitės reikšti vieną konkretų atvejį, sąlygas kitais atvejais, arba pogrupių.
>> Ačiū už žiūrėti šį trumpą.
Bent jau, dabar jūs galite suprasti, anekdotai, kaip šis.
Mano vardas Zamyla, ir tai yra CS50.
>> Pasinaudokite šia funkcija, hi, negaliojančiu funkcija, kuri trunka
int n, kaip įvestį.
Bazinį scenarijų ateina pirmiausia.
Jei n yra mažesnis už 0, spausdinti "Bye" ir grįžti.