[Zenelejátszási] 

DOUG LLOYD: Ön talán úgy gondolja, hogy kód csak használják, hogy egy feladat végrehajtásának. Akkor írd le. Ez nem valami. Ez nagyjából azt. 

Akkor fordítsuk le. Futtatja a programot. Te jó menni. 

De akár hiszed, akár nem, ha programozzák sokáig, hogy tényleg jöhet látni kódot valamit, ami szép. Ez megoldja a problémát Nagyon érdekes módon, vagy van valami igazán ügyes abban, ahogy kinéz. Lehet, hogy nevetve rám, de ez az igazság. És rekurzió egyik módja a fajta kap ez a gondolat A szép, elegáns megjelenésű kódot. Ez megoldja a problémákat oly módon, hogy Érdekes, könnyű elképzelni, és meglepően rövid. 

Az út rekurzív munkák van, olyan rekurzív úgy definiáljuk, mint egy függvény, amely felhívja magának az annak végrehajtását. Ez talán kissé különösnek tűnik, és majd meglátjuk, egy kicsit arról, hogyan is működik ez egy pillanat alatt. De ismétlem, ezek a rekurzív eljárások lesz olyan elegáns mert ők fognak hogy megoldja ezt a problémát anélkül mivel ezeket a többi funkció vagy ezeket a hosszú hurkok. Látni fogod, hogy ezek a rekurzív eljárásokat fognak nézni olyan rövid. És tényleg megy, hogy a kódot néz ki, szebb. 

Adok neked egy példát E látni, hogy rekurzív eljárást úgy lehetne meghatározni. Tehát ha ismeri ezt re matekórán sok évvel ezelőtt, Van valami az úgynevezett faktoriális függvény, ami általában jelöli egy felkiáltójel, amely meghatározása az összes pozitív egész szám. És az is, hogy N faktoros kiszámítása A megszorozzuk az összes a számok kisebb, mint vagy egyenlő n together-- minden egész kevesebb, mint vagy egyenlő n együttesen. 

Tehát 5 faktoros 5-ször 4-szer 3-szor 2-szer 1. És 4 faktoros 4-szer 3-szor 2-szer 1, és így tovább. Az ötlet. 

Ahogy a programozók, mi nem Használja n, felkiáltójel. Szóval mi határozza meg a faktoriális a funkciója, mint a tény, n. És fogjuk használni faktoros létrehozni rekurzív megoldást a problémára. És azt hiszem, lehet, hogy talál hogy ez sokkal több vizuális tetszetős, mint az iteratív változata ezen, amely mi is megnézzük egy pillanat. 

Tehát itt van egy pár facts-- szójáték intended-- mintegy factorial-- a faktoriális függvény. Faktoriálisát 1, mint mondtam, az 1. Faktoriálisát 2 2-szer 1. Faktoriálisát 3 3 szer 2-szer 1, és így tovább. Beszéltünk a 4. és az 5. már. 

De néztem ezt, nem igaz ez? Nem faktoriálisát 2 csak 2 alkalommal faktoriálisát 1? Úgy értem, faktoriálisát 1 1. Akkor miért nem tudunk csak mondani, hogy mivel faktoriálisát 2 2-szer 1, ez tényleg csak 2-szer faktoriálisát 1? 

És akkor kiterjesztve ezt a gondolatot, nem faktoriálisát 3 mindössze 3-szor faktoriálisát 2? És faktoriálisát 4 4-szer faktoriálisát 3, és így tovább? Tény, hogy a faktoriális bármely szám csak kifejezhető, ha azt a fajta Az e feladatokat örökre. Mi lehet a fajta általánosítani A faktoriális probléma mivel ez n-szer a faktoriálisát n mínusz 1. Ez n-szer a termék az összes számot kevesebb, mint nekem. 

Ez a gondolat, ez a általánosítása a probléma, lehetővé teszi számunkra, hogy rekurzív meghatározza a faktoriális függvény. Ha egy függvény definiálása rekurzív van Két dolog kell hogy legyen a részét. Be kell, hogy egy úgynevezett alapesetet, amely, ha megnyomod, leállítja a rekurzív folyamat. 

Ellenkező esetben, egy funkció, amely felhívja itself-- mivel lehet imagine-- mehet a végtelenségig. Funkció meghívja a függvényt felszólítja a függvény hívások A funkció meghívja a függvényt. Ha nincs módja megállítani, a programot amelyek ténylegesen beragadt A végtelen ciklust. Ez összeomlik végül, mert akkor elfogy a memória. De ez a lényeg. 

Szükségünk van egy másik módja annak, hogy hagyja abba dolgok mellett a programunk összeomlik, mert egy program, ami összeomlik az Valószínűleg nem szép vagy elegáns. És így hívjuk ezt az alaphelyzetben. Ez egy egyszerű megoldás Egy probléma, ami meggátolja A rekurzív folyamat bekövetkezését. Szóval ez egy része Egy rekurzív függvény. 

A második rész a rekurzív esetében. És ez az, ahol a rekurzió valóban sor kerül. Ez az, ahol a funkció hívja magát. 

Ez nem nevezi magát pontosan ugyanúgy hívták. Ez lesz egy kis eltérés ami a probléma, hogy ez próbálják megoldani egy pici kicsit kisebb. De általában halad a bak megoldására a nagy részét a megoldás egy másik hívást le a pályáról. 

Ezek közül melyik néz ki mint az alapeset itt? Ezek közül a néz ki, a legegyszerűbb megoldást a problémára? Van egy csomó factorials, és még sorolhatnánk megy on-- 6, 7, 8, 9, 10, és így tovább. 

De egy ilyen néz ki, mint egy jó esetben, hogy az alap esetében. Ez egy nagyon egyszerű megoldás. Nem kell semmit se csinálni. 

Faktoriálisát 1 mindössze 1. Nem kell, hogy nem minden szorzás egyáltalán. Úgy tűnik, mintha megyünk hogy megpróbálja megoldani ezt a problémát, és meg kell állnunk a Rekurzió valahol, azt kellene leállítani amikor eljutunk 1. Nem akarjuk, hogy ne az előtt. 

Tehát ha már meghatározó a faktoriális függvény, itt egy vázát hogyan lehet csinálni. Meg kell csatlakoztatni a két things-- Az alapeset és a rekurzív esetében. Mi a alapeset? Ha n = 1, visszatér 1-- ez egy nagyon egyszerű problémát megoldani. 

Faktoriálisát 1 1. Ez nem 1 alkalommal semmit. Ez csak 1. Ez egy nagyon egyszerű tény. És így lehet a mi alapeset. Ha kap telt 1 ebbe funkciót, akkor csak vissza 1. 

Mi a rekurzív esetében valószínűleg kinéznie? Minden más szám mellett 1, mi a minta? Nos, ha elvisszük faktoriálisát n, ez n-szer faktoriálisát n mínusz 1. 

Ha elvisszük faktoriálisát 3, ez 3-szor faktoriálisát 3 mínusz 1, vagy 2. És így van, ha nem néztem 1, egyébként hozam n-szer a faktoriálisát n mínusz 1. Ez elég egyértelmű. 

És kedvéért, amelynek kissé tisztább és sokkal elegánsabb kódot, tudom, hogy ha van egy-zsinórhurkokat vagy egysoros feltételes elágazások, tudunk megszabadulni az összes kapcsoszárójele körülöttük. Így tudjuk megszilárdítása e. Ez pontosan ugyanaz funkciók, mint ez. 

Én csak elvegyék a göndör nadrágtartó, mert ott csak egy sort belül e feltételes elágazások. Tehát ezek viselkedni. Ha n értéke 1, visszatér 1. Ellenkező esetben térjen vissza n-szer faktoriálisát n mínusz 1. Szóval, hogy a probléma kisebb. Ha n indul ki, mint 5, megyünk visszatérni 5-ször faktoriálisát 4. És majd meglátjuk, egy perc, amikor beszélünk a hívás stack-- másik videó ahol beszélünk hívja stack-- tanulunk arról, hogy miért éppen ez a folyamat működik. 

De míg faktoriálisát 5 mond visszatérni 5 alkalommal faktoriálisát 4 és 4 azt fogja mondani, OK, nos, cserébe 4-szer faktoriálisát 3. És mint látható, nem vagyunk fajta közeledik 1. Mi egyre közelebb és közelebb, hogy alapeset. 

És ha egyszer elérjük a alapeset, az összes előző funkciók Megvan a válasz kerestek. Faktoriálisát 2 mondott hozam 2 alkalommal faktoriálisát 1. Nos, faktoriálisát 1értéke 1. Tehát a felhívás faktoros 2 visszatérhet 2-szer 1, és adja, hogy vissza faktoriálisát 3, amely arra vár, hogy eredményt. 

És akkor ki tudja számítani annak eredménye, 3-szor 2 6, és adja vissza faktoriálisát 4. És megint van egy videó hívás verem ahol ezt az ábrán egy kicsit több, mint amit mondok most. De ez az. Ez önmagában a megoldást kiszámításakor faktoriálisának száma. 

Ez csak négy sornyi kódot. Ez elég jó, nem? Elég szexi. 

Tehát általában, de nem Mindig, olyan rekurzív helyettesítheti a hurok egy nem rekurzív függvény. Tehát itt, egymás mellett, az iteratív változata a faktoriális függvény. Mindkét kiszámolása pontosan ugyanezt. 

Mindketten számítani faktoriálisát n. A verzió a bal használja rekurzió csinálni. A verzió a jobb használja iteráció csinálni. 

És észre, van, hogy állapítsa egy változó egész szám termék. És akkor mi hurok. Mindaddig, amíg az n nagyobb, mint 0, mi tartsa megszorozzuk Termék n és a csökkentés n-ig kiszámítjuk a termék. Szóval ezt a két funkciót, ismét, nem pontosan ugyanaz a dolog. De nem csinálni pontosan ugyanolyan módon. 

Most, lehetséges, hogy több mint egy bázis esetben, vagy több, mint egy rekurzív esetben, attól függően, hogy milyen a funkciót próbál tenni. Nem feltétlenül csak kizárólag a Egyetlen alapeset, vagy egy rekurzív esetében. Tehát egy példa valamit több alap esetben Lehet, hogy a this-- Fibonacci számsor. 

Talán emlékeznek re általános iskola nap hogy a Fibonacci-sorozat definíciója mint this-- az első elem 0. A második elem 1. Mindkettő csak definíció szerint. 

Ezután az összes többi elemhez van meghatározva összegeként n mínusz 1 és n mínusz 2. Így a harmadik elem lenne 0 plusz 1 jelentése 1. És akkor a negyedik elem lenne a második elem, 1, valamint a harmadik elem, 1. És ez lenne 2. És így tovább és így tovább. 

Tehát ebben az esetben, van két alap esetben. Ha n értéke 1, vissza 0. Ha n értéke 2, vissza 1. Ellenkező esetben térjen vissza Fibonacci n mínusz 1 plusz Fibonacci n mínusz 2. 

Szóval ez több bázisállomás esetekben. Mi a helyzet a több rekurzív esetekben? Nos, van valami az úgynevezett Collatz sejtést. Nem fogom azt mondani, Tudja, mi az, mert valójában a végső probléma az adott videót. És ez a mi testmozgás hogy együtt dolgozunk. 

Tehát itt van, amit a Collatz sejtés is-- ez vonatkozik minden pozitív egész szám. És úgy okoskodik, hogy ez mindig lehetséges, hogy újra 1, ha az alábbi lépéseket. Ha n értéke 1, stop. Megvan vissza 1, ha n értéke 1. 

Egyébként végig ezt folyamat ismét n osztva 2. És nézd meg, hogy kap vissza 1. Ellenkező esetben, ha n páratlan, menjen át ez a folyamat újra 3n + 1, vagy 3-szor n + 1. Tehát itt van egy alap esetében. Ha n értéke 1, stop. Mi nem csinálunk többé rekurzió. 

De van két rekurzív esetben. Ha n páros, akkor tegye rekurzív ügyben, amelyben n osztva 2. Ha n páratlan, mi más rekurzív esetben a 3-szor n + 1. 

És így a cél ez a videó hogy egy második, szünetelteti a videót, és megpróbálja írni ezt rekurzív függvény Collatz ahol át egy értéket n, és kiszámítja, hogy hány lépést is ahhoz, hogy kap 1 ha elkezd n és hajtsa végre azokat fölé. Ha n értéke 1, tart 0 lépéseket. Egyébként ez lesz egy lépést plusz azonban sok lépést tart mindkét n osztva 2, ha n páros, vagy 3n plusz 1 ha n páratlan. 

Most, tettem fel a képernyőn itt Pár tesztet dolog az Ön számára, Pár tesztek esetben az Ön számára, hogy amit ezek a különböző Collatz számok, és egy illusztráció azokat a lépéseket, kell ment keresztül, így tudsz fajta látni ezt a folyamatot működés közben. Tehát, ha n egyenlő 1, Collatz n értéke 0. Nem kell csinálni semmit, hogy újra 1. Te már ott van. 

Ha n jelentése 2, tart egy lépés eljutni 1. Elkezdesz 2. Nos, 2 nem egyenlő 1. Szóval ez lesz az egyik lépés plusz azonban számos lépést meg veszi n osztva 2. 

2. osztva 2 1. Tehát vesz egy lépéssel plusz azonban sok lépést tart az 1. 1 vesz nulla lépéseket. 

3, mint látható, van jó néhány lépésből. Menj a 3. És akkor megy 10, 5, 16, 8, 4, 2, 1. Tart hét lépésben, hogy újra 1. És mint látható, van egy pár másik teszt eseteket itt kipróbálni a programot. Tehát ismét szünetelteti a videót. És én megyek ugrik vissza most mi a tényleges folyamat itt, mi ez a sejtés. 

Nézd meg, hogy kitaláljuk, hogyan határozzák meg Collatz n oly módon, hogy kiszámítja, hogy hány lépéseket kell ahhoz, hogy az 1. Így remélhetőleg, akkor megállt a videót és akkor nem csak arra vár, hogy megadja a választ itt. De ha, nos, Itt a válasz egyébként. 

Tehát itt egy lehetséges definíciója A Collatz funkciót. A bázis case-- ha n egyenlő 1, visszatérünk 0. Ez nem tesz lépéseket, hogy újra 1. 

Egyébként van két rekurzív Esetek egy a páros számok és egy a páratlan. Én úgy tesztelje a páros számok hogy ellenőrizze, ha n mod 2 értéke 0. Ez alapvetően, ismét, kérdezi a kérdést, ha felidézni, mit mod is-- ha oszd n 2 nem látható a többi? Ez lenne páros szám. 

És így ha n mod 2értéke 0 tesztelés ez páros szám. Ha igen, szeretnék visszatérni 1, mert ez határozottan hogy egy lépést plusz Collatz a bármilyen szám felem. Ellenkező esetben, szeretnék visszatérni 1 plusz Collatz 3-szor n + 1. Ez volt a másik rekurzív lépés, hogy vehetné kiszámításához Collatz-- a lépések száma tart, hogy újra 1 kap egy számot. Így remélhetőleg ez a példa kaptál egy kicsit Egy kis ízelítőt a rekurzív eljárások. Remélhetőleg, úgy gondolja, a kód egy kicsit szebb, ha végre Az elegáns, rekurzív módon. De még ha nem, rekurzió egy Nagyon hatékony eszköz mégis. És ez így biztosan valami hogy a fejed körül, mert akkor lesz képes létrehozni nagyon klassz programok segítségével rekurzió amelyek egyébként bonyolult a levelet ha használ hurkok és ismétlés. Én Doug Lloyd. Ez CS50.