[Predvaja glasba] 

Doug LLOYD: Verjetno mislite, da Koda se samo uporablja za dokončanje naloge. Pišete ven. To počne nekaj. To je precej to. 

Vam pripravijo ga. Zaženete program. Ste na dobri poti. 

Ampak verjeli ali ne, če ste kodo za dolgo časa, ste dejansko lahko prišli pogledat oznaka, kot nekaj, kar je lepo. Rešuje težave v Zelo zanimiv način, ali pa je samo nekaj res čeden o tem, kako to izgleda. Morda se smejala vame, ampak je res. In rekurzija je eden od načinov da nekako dobili to idejo lepe, elegantne-videti kodo. To rešuje probleme na načine, ki zanimiv, enostaven za vizualizacijo, in presenetljivo kratek. 

Način rekurzija deluje je rekurzivna funkcija je opredeljena kot funkcija, ki kliče sama kot del njegove izvedbe. To se morda zdi malo čudno, in bomo videli malo o tem, kako to deluje v trenutku. Ampak še enkrat, ti rekurzivni postopki bo tako elegantno ker oni gredo da bi rešili ta problem, ne da ob vseh teh drugih funkcij ali te dolge zanke. Boste videli, da ti rekurzivna Postopki bodo videti tako kratka. In res se dogaja, da bi kodo videti veliko lepša. 

Dal vam bom primer to, da vidim, kako rekurzivni postopek se lahko opredeliti. Torej, če ste seznanjeni s tem iz matematike razred pred mnogimi leti, Nekaj ​​je imenovan Funkcija faktorski, ki je ponavadi označimo kot klicajem, ki je opredeljena kot vsa pozitivna cela števila. In način, ki n factorial se izračuna se ti množijo vse številke manj kot ali enako n together-- vsa cela števila manj kot ali enaka n skupaj. 

Torej 5 faktorsko je 5-krat 4-krat 3 krat 2-krat 1. In 4 faktorsko je 4-krat 3 krat 2-krat 1 in tako naprej. Dobiš idejo. 

Kot programerji, ne bomo uporabite N klicaj. Torej bomo opredeliti factorial Funkcija kot dejstvo n. In bomo uporabili fakulteto za ustvarjanje rekurzivna rešitev problema. In mislim, da bi našli da je veliko bolj vizualno privlačna kot iterativni različica tega, kar bomo lahko tudi pogled na v tem trenutku. 

Torej, tukaj je nekaj facts-- pun intended-- o factorial-- factorial funkcija. Fakulteto 1, kot sem rekel, je 1. Fakulteto 2 je 2-krat 1. Fakulteto 3 3 krat 2 krat 1, in tako naprej. Pogovarjala sva se o 4. in 5. že. 

Ampak gledamo na to, ali ni to res? Ne fakulteto 2 le 2-krat fakulteto 1? Mislim, faktorsko od 1. 1. Torej, zakaj ne moremo ravno reči, da, saj faktorsko od 2 je 2-krat 1, to je res samo 2-krat fakulteto 1? 

In potem se razteza to idejo, ni factorial od 3 le 3-krat fakulteto 2? In faktorsko dne 4. je 4-krat fakulteto 3, in tako naprej? V bistvu, faktorsko poljubnega števila lahko samo se je izrazil, če bi nekako za opravljanje tole večno. Mi lahko nekako posploševati fakulteto problem saj je n-krat faktorski n minus 1. To je n-krat produkt vse številke manj kot mene. 

Ta ideja, to posplošitev problema, nam omogoča, da rekurzivno opredeliti faktorsko funkcijo. Ko določite funkcijo rekurzivno, tam je dve stvari, ki jih potrebujejo, da se del tega. Morate imeti nekaj, kar se imenuje osnovna ureditev, ki, ko ga sproži, bodo prenehali rekurzivno proces. 

Sicer funkcija, ki zahteva itself-- kot si morda imagine-- bi šel na večno. Funkcija pokliče funkcijo poziva funkcijskih klicev funkcija pokliče funkcijo. Če nimate pot da bi ga ustavili, vaš program bo učinkovito zatakne na neskončno zanko. To bo crash na koncu, ker bo zmanjkalo pomnilnika. Ampak to je poleg točke. 

Moramo imeti kak drug način za ustavitev Stvari poleg našega programa treskav, ker je program, ki se zruši, je Verjetno ni lepa in elegantna. In zato pravimo ta osnovna ureditev. To je enostavna rešitev na problem, ki se ustavi rekurzivni proces, ki se pojavljajo. Torej, to je en del rekurzivna funkcija. 

Drugi del je rekurzivnega primera. In to je, če rekurzijska bo dejansko potekala. To je, če Funkcija bo sam poklical. 

To se ne bo poklical v točno na enak način je bil imenovan. To bo rahla sprememba da naredi problem, da je poskuša rešiti poskočno malo manjši. Vendar je na splošno prehaja buck reševanja večji del raztopine v drug klic po vrsti. 

Kateri od teh pogledov kot osnovnem scenariju tukaj? Kateri od teh izgleda Najpreprostejša rešitev problema? Imamo kup factorials, in bi še naprej tekoč on-- 6, 7, 8, 9, 10, in tako naprej. 

Toda eden od teh izgleda kot dober primer, da je osnovna. To je zelo preprosta rešitev. Nimamo narediti nič posebnega. 

Fakulteto 1. je samo 1. Mi ne bi bilo treba storiti vse množenje sploh. Zdi se, kot če gremo poskusiti in rešiti ta problem, in moramo ustaviti rekurzije nekje, bomo verjetno želeli ustaviti da ko pridemo do 1. Mi ne želimo ustaviti pred tem. 

Torej, če smo opredeljevanju naša faktorski funkcija, tukaj je okostje za kako lahko to storimo. Moramo priključiti v teh dveh things-- osnovna ureditev in rekurzivni primer. Kakšna je osnovna? Če je n enak 1, vrne 1-- to res preprost problem rešiti. 

Fakulteto 1. 1. To ni 1 krat karkoli. To je samo 1. To je zelo preprosto dejstvo. In tako, da se lahko naša baza primera. Če se bomo opravili 1 v to funkcija, bomo samo vrniti 1. 

Kaj je rekurzivna primer verjetno izgledal? Za vsako drugo številko poleg 1, kaj je vzorec? No, če smo ob fakulteto n, da je n-krat faktorsko n minus 1. 

Če smo ob fakulteto od 3, to je 3-krat fakulteto 3 minus 1, ali 2. In tako, če ne bomo gledamo na 1, sicer donosnost n krat faktorski n minus 1. To je precej preprosta. 

In zaradi nekoliko ob čistejše in bolj elegantno kodo, vem, da če imamo enovrstični zanke ali enovrstični pogojni panoge, bomo lahko znebiti vse zaviti oklepaji okoli njih. Tako bomo lahko to utrditi s tem. To je popolnoma enaka funkcionalnosti, kot je ta. 

Jaz sem samo jemlje kodrasti naramnice, ker tam je samo ena vrstica znotraj teh pogojnih podružnic. Torej ti se obnašajo enako. Če je n enak 1, vrne 1. V nasprotnem primeru vrne n-krat fakulteto n minus 1. Tako smo kar problem manjši. Če n začne kot 5, se bomo vrne 5-krat fakulteto 4. In bomo videli čez minuto, ko govorimo o razpisu stack-- v drugi video kadar govorimo o pokličite stack-- bomo naučili o tem, zakaj ravno ta proces deluje. 

Toda medtem ko faktorsko 5 pravi, vrne 5-krat fakulteto 4 in 4 je reči, OK, dobro, vračanje 4-krat fakulteto 3. In kot vidite, smo nekako približuje 1. Mi smo bližje in bližje tej osnovni scenarij. 

In ko smo zadeli osnovno zadevo, vseh prejšnjih funkcij imajo odgovor so iskali. Faktorski dne 2. rekel donos 2-krat fakulteto 1. No, faktorski od 1 donosov 1. Tako da je razpis za fakulteto z dne 2. lahko vrnete 2-krat 1, in dal to nazaj na fakulteto 3, ki je čakala za ta rezultat. 

In potem lahko izračunamo njegove rezultat, 3 krat 2 je 6, in ga dal nazaj na fakulteto 4. In spet, imamo video na klicni dimnika če je to prikazano malo več kot to, kar sem rekel, prav zdaj. Ampak to je to. Že samo s tem je rešitev za izračuna fakulteto števila. 

To je le štiri vrstice kode. To je zelo kul, kajne? To je nekako seksi. 

Torej v splošnem, toda ne Vedno, rekurzivna funkcija more nadomestiti zanke v non-rekurzivna funkcija. Torej, tukaj, drug ob drugem, je iterativen različica faktorski funkcije. Oba izračunajte natanko isto stvar. 

Oba izračuna fakulteto n. Različica na levi uporablja rekurzijo, da to storite. Različica na desni uporablja ponovitev, da to storite. 

In obvestilo, da moramo razglasiti spremenljivka celo izdelek. In potem smo zanka. Dokler je n večji kot 0, smo obdržati pomnoži ta izdelek z N in pomanjšanja n do izračunamo izdelek. Torej ti dve funkciji, še enkrat, narediti točno isto stvar. Ampak tega ne stori v na povsem enak način. 

Zdaj je mogoče imajo več kot eno bazo Primer ali več kot eno rekurzivno primeru, odvisno na kaj vaša funkcija se poskuša narediti. Niste nujno omejen samo na enotna osnova primer ali enojno rekurzivno primer. Torej primer nečesa z več baznih primerih morda this-- Fibonaccijevo zaporedje števil. 

Morda se boste spomnili iz osnovne šole dni da je sekvenca Fibonaccijevo definirano kot this-- prvi element je 0. Drugi element je 1. Oba sta le po definiciji. 

Potem je vsak drugi element je opredeljen kot vsota n minus 1 in n minus 2. Torej tretjega elementa bi 0 in 1 1. In nato četrti element bi drugi element, 1, plus tretji element, 1. In da bi bila 2. In tako naprej in tako naprej. 

Torej, v tem primeru imamo dve osnovnih zadev. Če je n enak 1, vrne 0. Če je n enak 2, vrne 1. V nasprotnem primeru, se vrnite Fibonacci n minus 1 plus Fibonaccijevo n minus 2. 

Torej, to je več baznih primere. Kaj več rekurzivnih primerih? No, nekaj je imenuje Collatz ugibanje. Ne bom povedal, veste, kaj to je, ker je dejansko naša končna Problem pri tem videu. In to je naša vadba delati skupaj. 

Torej, tukaj je tisto, kar Collatz domneva is-- to velja za vsako pozitivno celo število. In špekulira, da je vedno mogoče, da bi dobili nazaj 1, če boste sledili korakom. Če je n 1, ustavi. Dobili smo nazaj na 1, če je n 1. 

V nasprotnem primeru, iti skozi to Postopek spet na n deljeno z 2. In videli, če lahko dobite nazaj na 1. V nasprotnem primeru, če je n liho, iti skozi ta proces spet na 3N plus 1, ali 3-krat n plus 1. Torej, tukaj imamo eno samo osnovno zadevo. Če je n enak 1, ustavi. Mi ne delaš nič več rekurzijo. 

Ampak imamo dve rekurzivne primere. Če je n celo, naredimo eno rekurzivno Primer, ki pristajajo n deljeno z 2. Če je n liho, delamo drugačen rekurzivni primer na 3-krat n + 1. 

In tako je cilj za ta video je vzeti sekundo, pavza video, in poskusite napisati to rekurzivna funkcija Collatz kjer se boste peljali v vrednosti n, in izračunava koliko korakov je meni, da bi dobili 1, če začnete z n in sledite tiste korake tam zgoraj. Če je n 1, je potrebno 0 korake. Sicer pa se dogaja, da vzemite en korak plus Vendar veliko korakov je potrebnih, na obeh n deliti z 2, če je n celo ali 3n plus 1 če je n sodo. 

Sedaj sem dal gor na zaslonu tukaj nekaj testnih stvari za vas, nekaj testov primerih za vas, da bi videli kaj ti različni Collatz številke, in tudi ilustracija od korakov, ki treba šla skozi, tako da lahko nekako se ta proces v akciji. Torej, če je n enak 1, Collatz n je 0. Nimate storiti karkoli, da bi dobili nazaj na 1. Ste že tam. 

Če je n 2, je potrebno en korak, da pridete do 1. Začnete z 2. No, 2 ni enak 1. Tako se dogaja, da so en korak plus pa veliko korakov je prevzame n deljeno z 2. 

2 deljeno z 2 1. Tako da traja en korak plus Vendar veliko korakov je potrebno za 1. 1 je nič korake. 

Za 3, kot lahko vidite, obstaja vključenih kar nekaj korakov. Greš od 3. In potem greš na 10, 5, 16, 8, 4, 2, 1. To traja sedem korakov, da bi dobili nazaj na 1. In kot lahko vidite, obstaja Nekaj ​​drugih testnih primerov tukaj preizkusiti svoj program. Torej še enkrat, pavza video. In jaz bom skočil nazaj zdaj kaj je dejanski proces je tukaj, kaj je ta domneva je. 

Glejte, če lahko ugotovimo, kako opredeliti Collatz n tako, da izračunava koliko korakov je potrebno, da pridete do 1. Torej upajmo, da ste zamrznili video in vi ste ne samo me čaka da vam odgovora. Ampak, če ste, no, tukaj je odgovor vseeno. 

Torej, tukaj je možna opredelitev funkcije Collatz. Naša baza case-- če je n enaka 1, se vrnemo 0. To ne bo vsaka koraki, da bi dobili nazaj na 1. 

Sicer pa imamo dve rekurzivni cases-- eden za celo številk in eno za sodo. Pot I test za celo števil je, da preveri, če n mod 2 enak 0. To je v bistvu, še enkrat, asking vprašanje, Če se spomnimo, kaj mod is-- če sem razkorak n z 2 ne obstaja preostanek? To bi bilo sodo število. 

In tako, če n mod 2 enaka 0, je Testiranje je to celo število. Če je tako, želim, da se vrnete 1, ker to je definitivno pri čemer en korak plus Collatz od ne glede na število je polovica mene. Sicer pa želim, da se vrnete 1 plus Collatz za 3-krat n plus 1. To je bila druga rekurzivni korak, ki smo bi lahko za izračun Collatz-- število korakov je potrebno, da bi dobili nazaj do 1. dobijo številko. Torej, upam, da ta primer ti je dal malo z okusom rekurzivnih postopkov. Upam, da misliš, da koda je malo lepše, če izvajajo v elegantnem, rekurzivni način. Toda tudi če ne, rekurzija je res močno orodje vseeno. In zato je definitivno nekaj , da bi dobili svojo glavo okoli, saj boste lahko ustvarili precej kul programi uporabljajo rekurzijo ki bi sicer zapletena, da napišete če uporabljate zank in ponovitev. Sem Doug Lloyd. To je CS50.