>> ZAMYLA: Selleks, et mõista rekursioon, peate
kõigepealt aru rekursioon.
Võttes rekursioon on programmi koostamisel tähendab, et teil on eneseleosutavad
mõisted.
Rekursiivne andmestruktuuride näiteks on andmestruktuurid
sisaldama ise nende definitsioonid.
Aga täna me ei kavatse keskenduda on rekursiivne funktsioone.
>> Tuletame meelde, et ülesandeid võtma sisendite argumente ning tagastab väärtuse kui nende
väljund esindajad see skeem siin.
Me mõtleme kasti kehas Funktsiooni sisaldav komplekt
juhiseid, et tõlgendada sisend ja annab väljundi.
Võttes lähemalt kehas funktsioon võiks paljastada kõned
muud funktsioonid samuti.
Võtke see lihtne ülesanne, suva, et võtab ühe stringi sisendiks ja
prindib mitu tähte et string on.
Funktsioon strlen, keelpilliorkestrile pikkus, nimetatakse, kelle toodang on
vajalik helistage printf.
>> Nüüd teebki rekursiivne funktsioon eriline on see, et ta nimetab ennast.
Me ei esinda see rekursiivne kutsuvad seda oranž arrow
silmukoiminen tagasi ise.
Aga täidesaatva ennast uuesti alles teha teise rekursiivne kõne ja
teine ​​ja teine.
Aga rekursiivne funktsioone ei saa olla lõpmatu.
Nad peavad lõpetama kuidagi, või oma Programm kestab igavesti.
>> Nii et me peame leidma viisi, kuidas murda välja rekursiivne kõne.
Me nimetame seda tugipunkti.
Kui tugipunkti tingimus on täidetud, tagastab funktsioon tegemata
teine ​​rekursiivne kõne.
Võta see funktsioon, hi, tühine funktsioon mis võtab int n sisendiks.
Baasjuhtumi jõuab.
Kui n on väiksem kui null, print bye ja tagasi Kõikidel muudel juhtudel,
funktsioon prindib hi ja ellu rekursiivne kõne.
Teine kõne funktsioon hi koos decremented sisendkäibemaks.
>> Nüüd, kuigi me printida hi, funktsioon ei lõpe enne, kui me
tagasi tema naasmise tüüp sel juhul tühine.
Seega iga n peale baasi juhul Selle funktsiooni hi naaseb hi
n miinus 1.
Kuna see funktsioon on tühine küll, me ei ole selgesõnaliselt kirjuta siia tagasi.
Me lihtsalt funktsiooni täitmiseks.
Nii kutsutakse hi (3) prinditakse hi ja täita hi (2), mis käivitab hi (1) üks
täitval hi (0), kus tugipunkti tingimus on täidetud.
Nii hi (0) prindib bye ja tagastab.
>> OK.
Nüüd, kui me aru põhitõdesid rekursiivne funktsioone, mida nad vajavad
vähemalt ühe aluse puhul samuti rekursiivne kõne, liigume edasi
otstarbekam näiteks.
Üks, mis ei ole lihtsalt tagasi tühistada ükskõik mida.
>> Võtame pilk faktoriaal toiming, mida kasutatakse kõige sagedamini
tõenäosuse arvutused.
Faktoriaal n on toote iga positiivse täisarvu alla
ja võrdne n.
Nii faktoriaal viis on 5 korda 4 korda 3 korda 2 korda 1, saades 120.
Neli faktoriaal on 4 korda 3 korda 2 korda 1, saadi 24.
Ja sama reegel kehtib mistahes positiivse täisarvu.
>> Niisiis, kuidas võiks me kirjutada rekursiivne funktsioon, mis arvutab faktoriaali
on number?
Noh, me peame kindlaks nii tugipunkti ja rekursiivne kõne.
Kirjutan üleskutse on sama Kõigi juhtudel arvatud aluse
puhul, mis tähendab, et me peame leida muster, mis annab meile meie
soovitud tulemus.
>> Selle näiteks näha, kuidas 5 faktoriaalses hõlmab korrutades 4 3 2 1
Ja selsamal korrutamine leidub siin
määratlus 4 faktoriaal.
Nii me näeme, et 5 faktoriaal on ainult 5 korda 4 faktoriaal.
Nüüd see muster kohaldatakse 4 faktoriaal ka?
Jah.
Me näeme, et 4 faktoriaal sisaldab korrutamine 3 korda 2 korda 1,
väga määratlusega 3 faktoriaal.
Nii 4 faktoriaal on võrdne 4 korda 3 faktorilise, ja nii edasi ja nii edasi meie
muster paistab kuni 1 faktoriaal, mis definitsiooni on võrdne 1.
>> Ei ole muid positiivseid täisarvud vasakule.
Nii et meil on mustri meie rekursiivne kõne.
n faktoriaal on võrdne n korda faktoriaali n miinus 1.
Ja meie baasi puhul?
See lihtsalt on meie definitsioon 1 faktoriaal.
>> Nüüd me saame liikuda kirjalikult kood funktsiooni.
Baastestis juhul on meil tingimus n on võrdne 1, kus
me tagasi 1.
Siis lähevad peale rekursiivne kõne, me tagasi n korda
faktoriaali n miinus 1.
>> Nüüd testida meie.
Proovime faktoriaal 4.
Per meie funktsioon on võrdne 4 korda faktoriaal (3).
Faktoriaali (3) on võrdne 3 korda faktoriaal (2).
Faktoriaali (2) on võrdne 2 korda faktoriaal (1), mis tagastab 1.
Faktoriaali (2) nüüd tagasi 2 korda 1, 2.
Faktoriaali (3) saab nüüd tagasi 3 korda 2, 6.
Ja lõpuks, faktoriaal (4) tagasi 4 korda 6, 24.
>> Kui sul tekib mingeid raskusi koos kirjutan Kõne teeselda, et
funktsioon töötab juba.
Mida ma mõtlen on see, et sa peaksid usalda oma rekursiivne kõne tagasi
õigeid väärtusi.
Näiteks, kui ma tean, et faktoriaali (5) võrdub 5 korda
faktoriaal (4) ma usun, et faktoriaali (4) annab mulle 24.
Mõtle seda muutujat, kui te Will, kui sa juba määratletud
faktorilise (4).
Nii tahes faktoriaalses (n), on see produkti n ja
Eelmise faktoriaal.
Ja see eelmine faktoriaal Saadakse helistades
faktoriaali n miinus 1.
>> Nüüd, vaata kui saad rakendada rekursiivne funktsioon ise.
Laadi üles oma terminali või run.cs50.net, ja kirjutada funktsiooni summa
mis võtab täisarv n ja tagastab summa kõikide järjestikust positiivset
täisarvud n 1.
Olen kirjutanud välja summasid mõne väärtused, mis aitavad teil oma.
Esiteks, selgitada, tugipunkti seisukorras.
Siis vaatame summa (5).
Kas sa väljendada seda teise summa?
Nüüd, kuidas summa (4)?
Kuidas saab väljendada summa (4) poolest teine ​​summa?
>> Kui teil on summa (5) ja summa (4) väljendatud muude summade, vt
kui saate tuvastada mustrit koguhulk (n).
Kui ei, siis proovige mõne muu numbrid ja väljendada oma summasid
tingimustel teise numbrid.
Tuues välja patterns diskreetne numbrid, sa oled hästi oma viis
identifitseerimiseks mustri tahes n.
>> Recursion on tõesti võimas vahend, nii et muidugi see ei ole piiratud
matemaatilisi funktsioone.
Rekursioon saab kasutada väga tõhusalt kui tegemist on puud näiteks.
Tutvu lühike puud põhjalikumat läbivaatamist, kuid nüüd
Meenutame, et binaarne otsing puud sisse Eelkõige koosnevad sõlmed, iga
väärtusega ja kaks sõlme suunanäitajaks.
Tavaliselt on see esindab ematipp on üks joon suunaga
vasakule Järglassõlme ja üks paremal Järglassõlme.
Struktuuri binaarne otsing puu sobib hästi
et rekursiivne otsing.
Rekursiivne kõne kas möödub vasakule või paremale sõlme, kuid rohkem
Selle puu lühike.
>> Ütle, et tahad teha operatsioon iga sõlme kahendpuu.
Kuidas võiks edasi minna on?
Noh, sa võiksid kirjutada rekursiivne funktsioon, mis täidab operatsiooni
vanemale sõlme ja teeb rekursiivne kõne on sama funktsioon,
kulgeb vasakule ja õige tütartippu.
Näiteks see funktsioon, suva, mis muudab väärtust antud sõlm ja
kõik tema lapsed 1.
Baasi puhul null sõlme põhjused funktsioon tagastama, näidates
et seal ei ole sõlmede jäänud, et sub-tree.
>> Vaatame seda.
Esimene vanem on 13.
Muudame väärtus 1 ja seejärel kõne Meie ülesanne vasakul samuti
kui paremale.
Funktsioon, suva, mida nimetatakse vasakul sub-tree esiteks nii vasaku sõlme
saab ümber jaotada 1 ja foo kutsutakse, et sõlm lapsed
esimene vasakule ja seejärel paremale ja nii edasi ja nii edasi.
Ja ütle neile, et oksad ei ole veel lapsi nii sama protsessi
jätkub õiges lapsed kuni kogu puu sõlmed
ümber jaotada 1.
>> Nagu näete, siis ei ole piiratud ainult ühe rekursiivse helistada.
Just nii palju kui saad töö tehtud.
Mida teha, kui teil on olnud puu, kus iga sõlm oli kolm last,
Vasakpoolne, keskmine ja parempoolne?
Kuidas sa muuta suva?
Noh, lihtne.
Lihtsalt lisada veel rekursiivne kõne ja edasi keset sõlme pointer.
>> Recursion on väga võimas ja mitte mainida elegantne, kuid see võib olla
keeruline mõiste esimesel, nii et patsient ja võtke aega.
Alusta tugipunkti.
See on tavaliselt kõige lihtsam selgitada, ja siis saate töötada
tagasi sealt.
Sa tead, mida vajate, et saavutada oma tugipunkti, nii et võiks
teile mõned vihjed.
Püüdke väljendada ühe konkreetse juhtumi Muid juhtumeid või sub-komplekti.
>> Täname vaadates seda lühike.
Vähemalt nüüd saab mõista nalja nagu see.
Minu nimi on Zamyla ja see on CS50.
>> Võta see funktsioon, hi, void funktsioon, mis võtab
int n, kui sisend.
Baasjuhtumi jõuab.
Kui n on väiksem kui 0, print "Bye" ja tagasi.