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.