>> ZAMYLA: Ahhoz, hogy megértsük rekurzió, meg kell
először megérteni, rekurzió.
Miután rekurziót program tervezése eszközök hogy van ön-referenciális
definíciók.
Rekurzív adatstruktúrák, például, olyan adat struktúrák
közé magukat a definíciók.
De ma fogunk összpontosítani A rekurzív függvények.
>> Emlékezzünk vissza, hogy működik, hogy bemenet, érveket, és vissza értéket, mint a
kimenet által képviselt ez a rajz itt.
Majd kitalálunk a doboz, mint a test a funkciót, amely tartalmazza a készlet
utasításokat, hogy értelmezze a bemeneti, és kimeneti.
A kezelés ideje alatt egy közelebbi pillantást a testben A funkció fedhet hívások
más funkciókat is.
Vegyük ezt az egyszerű funkciót, ize, hogy vesz egy string bemeneti és
kiírja, hogy hány betű hogy a húr van.
A funkció strlen, string hossza, nevezik, melynek kimenete
szükséges a hívás printf.
>> Most, mitől lesz egy rekurzív függvény különös az, hogy saját magát hívja meg.
Mi is képviseli ezt a rekurzív hívják ezt a narancs nyíl
hurok vissza önmagához.
De végrehajtása magát újra csak akkor újabb rekurzív hívást, és
egy másik, és egy másik.
De a rekurzív függvények nem lehet végtelen.
Ők a végére valahogy, vagy a a program fog örökké.
>> Tehát meg kell találni a módját, hogy megtörje ki a rekurzív hívások.
Ezt nevezzük az alapeset.
Amikor az alapeset feltétel teljesül, A függvény nélkül
egy rekurzív hívást.
Vegyük ezt a funkciót, hi, void függvény hogy vesz egy int n, mint bemenet.
Az alapeset az első.
Ha n kisebb, mint nulla, nyomtatási szia és Cserébe minden más esetben, a
funkció kiírja hi és végrehajtási a rekurzív hívás.
Egy másik függvény hívása hi-vel A csökkenhet bemeneti értéket.
>> Most, még akkor is nyomtatni hi, a funkció nem szünteti meg, amíg meg nem
vissza a visszatérési típus, ebben az esetben érvénytelen.
Így minden n kívüli alapeset, ez a funkció hi visszatér hi
n mínusz 1.
Mivel ez a funkció érvénytelen mégis, akkor nem kifejezetten írja térjen ide vissza.
Majd csak futtasd a funkciót.
Így hívás hi (3) nyomtatja hi és végre hi (2), amely végrehajtja a hi (1) egy
amely végrehajtja a hi (0), ahol a alapeset feltétel teljesül.
Tehát hi (0) nyomtat szia és visszatér.
>> OK.
Tehát most, hogy megértjük az alapjait rekurzív függvények, hogy szükség van
legalább egy bázis esetében, valamint egy rekurzív hívás, menjünk tovább, hogy a
több értelmes példa.
Az egyik, hogy nem csak vissza elvesztésével nem számít, mit.
>> Vessünk egy pillantást a faktoriális működés használják leggyakrabban
valószínűség számítás.
Faktoriális n a termék minden pozitív egész szám kisebb, mint
és egyenlő n.
Tehát faktoriális öt 5-ször 4-szer 3-szor 2-szer 1, hogy 120.
Four faktoriális 4-szer 3-szor 2-szer 1, így 24.
És ugyanaz a szabály vonatkozik bármilyen pozitív egész szám.
>> Szóval, hogyan lehet, hogy írunk egy rekurzív funkció, amely kiszámítja a faktoriális
a szám?
Nos, akkor meg kell határozni azokat mind a alapeset a rekurzív hívást.
A rekurzív hívás ugyanaz lesz minden esetben, kivéve a bázis
eset, ami azt jelenti, hogy meg kell találni egy mintát, hogy megadja nekünk a
kívánt eredményt.
>> Ebben a példában, hogyan 5 faktoriális magában megszorozzuk 4 3 2 1
És, hogy ugyanazon a szorzás itt található, a
meghatározása 4. faktoriális.
Tehát azt látjuk, hogy 5 faktoriális van mindössze 5-ször 4 faktoriális.
Most azonban ez a minta vonatkozik 4 faktoriális is?
Igen.
Látjuk, hogy a 4 faktoriális tartalmazó szorzás 3-szor 2-szer 1, akkor a
ugyanazon definíció 3. faktoriális.
Tehát 4 faktoriális egyenlő 3-4-szer faktoriális, és így tovább és így tovább a mi
minta tapad 1-ig faktoriális, amely definíció szerint egyenlő 1-gyel.
>> Nincs más pozitív egész maradt.
Tehát a mintát a rekurzív hívás.
n faktoriális egyenlő n-szer A faktoriális n mínusz 1.
És a alapeset?
Ez majd csak a definíció 1 faktoriális.
>> Így most már lépni írás kódot a funkciót.
Az alapeset, mi lesz a n értéke feltétel egyenlők 1, ahol
mi vissza 1.
Ezután mozgó rá a rekurzív hívás, visszafizetjük n-szer a
faktoriális n mínusz 1.
>> Most teszteljük ezt a.
Próbáljuk faktoriális 4..
Per a funkció, hogy ez egyenlő -4-szer faktoriális (3).
Faktoriális (3) egyenlő 3 alkalommal faktoriális (2).
Faktoriális (2) egyenlő 2-szer faktoriális (1), amely visszaadja 1..
Faktoriális (2) most visszatér 2-szer 1, 2.
Faktoriális (3) most visszatér 3-szor 2 6.
És végül, faktoriális (4) 4-szer visszatér 6., 24..
>> Ha találkozik bármilyen nehézség a rekurzív hívás, úgy, mintha
A funkció már.
Mit jelent ez, hogy meg kell bízni a rekurzív hívások vissza
a megfelelő értékeket.
Például, ha tudom, hogy faktoriális (5) értéke 5-ször
faktoriális (4), fogok benne, hogy faktoriális (4) ad nekem 24.
Gondold azt, hogy egy változó, ha lesz, mintha már definiált
faktoriális (4).
Így minden faktoros (n), akkor a termék-és n
Az előző faktoriális.
És ez az előző factorial kapjuk meghívásával
faktoriális n mínusz 1.
>> Most nézd meg, hogy végre egy rekurzív függvény magad.
Töltse fel a terminál, vagy run.cs50.net, és írni egy függvény összeget
hogy vesz egy n egész számot, és visszaadja a összessége egymást követő pozitív
egész n 1-re.
Én írtam ki az összegeket néhány értékeket, hogy segítsen a.
Először is, kitalálni a alapeset állapotban.
Aztán nézd meg az összeget (5).
Tudod kifejezni, hogy mind egy másik összeget?
Nos, mi a helyzet az összeget (4)?
Hogyan lehet kifejezni sum (4) szempontjából egy másik összeget?
>> Miután sum (5) és összege (4) kifejezett egyéb kifizetést, lásd
ha tudod azonosítani a mintát összeg (n).
Ha nem, néhány más számot és kifejezni összegekkel
szempontjából egy másik számot.
Azonosításával minták diszkrét számokat, akkor is az utat, hogy
azonosítja a minta minden n.
>> Rekurzió egy nagyon hatékony eszköz, így természetesen ez nem csak a
matematikai funkciókat.
Rekurzió használható nagyon hatékonyan kezelése során fákat például.
Nézze meg a rövid a fák a alaposabb áttekintését, de most
Emlékeztetünk arra, hogy bináris keresés fák, a Különösen, alkotják a csomópontok, amelyek mindegyike
értékű és két csomópont mutatók.
Általában ez képviseli a szülő csomópont, amelynek egy sor mutató
a bal oldalon, és egy gyermek csomópont jobbra gyermek csomópont.
A szerkezet egy bináris keresés fa alkalmas arra is,
a rekurzív keresést.
A rekurzív hívás sem halad a a bal vagy a jobb csomópont, de sokkal
az, hogy a fa rövid.
>> Mondja el, hogy szeretne végre egy műveletet minden egyes csomópont egy bináris fa.
Hogy lehet, hogy megy róla?
Nos, meg tudná írni a rekurzív funkció, amely végrehajtja a műveletet
A szülő csomópont és teszi a rekurzív hívja ugyanazt a funkciót,
halad a bal és jobb gyermek csomópont.
Például, ez a funkció, ize, hogy megváltoztatja az értéke egy adott csomópont és
valamennyi gyermek 1-re.
Az alapeset a null csomópont okai a függvényt, jelezve,
hogy nincsenek csomópontok maradt, hogy az al-fa.
>> Sétáljunk át rajta.
Az első szülő 13.
Mi változik az érték 1-re, majd hívja a funkció a bal oldalon, valamint
mint a jobb.
A funkció, ize, nevezzük a bal oldalon al-fa első, így a bal oldali csomópont
majd áthelyezték az 1-es és ize lesz felszólította, hogy a csomópont gyermekei,
először, majd a bal és a jobb oldalon, és így tovább és így tovább.
És mondd meg nekik, hogy ágai nem több gyereket, így ugyanaz a folyamat
továbbra is a megfelelő gyermekek számára amíg az egész fa csomópontok
áthelyezték 1-re.
>> Mint látható, akkor nem csak csak egy rekurzív hívást.
Csak annyi, mint majd a munkát.
Mi van, ha volt egy fa, ahol minden egyes csomópont volt három gyermek,
Bal, középsõ és jobb?
Hogyan szerkeszteni foo?
Nos, egyszerű.
Csak egy újabb rekurzív hívás át a középső csomópont mutatót.
>> Rekurzió nagyon erős, és nem beszélve elegáns, de ez lehet egy
nehéz fogalom az első, ezért betegre, és vegye be időben.
Kezdje az alapeset.
Ez általában a legkönnyebb azonosítani, és akkor lehet dolgozni
visszafelé onnan.
Tudod, hogy meg kell, hogy elérje a alapeset, hogy a hatalom
kapsz néhány tippet.
Próbáld kifejezni egy adott esetben mind az egyéb esetekben, vagy al-készletek.
>> Köszönöm, hogy néz ez a rövid.
Legalábbis, most már tudod érti a vicceket, mint ez.
A nevem Zamyla, és ez CS50.
>> Vegyük ezt a funkciót, hi, a érvénytelen funkciója, amely
int, n, mint bemenet.
Az alapeset az első.
Ha n kisebb, mint 0, print "Bye" és vissza.