[Glazbom] 

Doug LLOYD: Vi vjerojatno mislite da je broj je samo koristiti za izvršenje zadatka. Možete ga napisati. To čini nešto. To je prilično zadovoljni. 

Možete ga sastaviti. Možete pokrenuti program. Ti si dobar to ići. 

No vjerovali ili ne, ako je što kodirati za dugo vremena, možda zapravo došli vidjeti broj kao nešto što je lijepo. Ona rješava problem u vrlo zanimljiv način, ili postoji samo nešto stvarno uredno o načinu izgleda. Možda se smijao na mene, ali to je istina. I rekurzija je jedan od načina na neki način dobili tu ideju od lijepa, elegantna izgleda koda. To rješava probleme na način koji su zanimljive, lako vizualizirati, i iznenađujuće kratko. 

Način na rekurzije radovi je, rekurzivna funkcija definiran kao funkcija koji poziva sama kao dio njegova izvršenja. To se može činiti malo čudno, pa ćemo vidjeti malo o tome kako to radi u ovom trenutku. Ali opet, to rekurzivni postupci će biti tako elegantna jer oni će riješiti ovaj problem bez ima sve te ostale funkcije ili ove duge petlje. Vidjet ćete da su to rekurzivna Postupci će izgledati tako kratko. I doista su idući u izraditi Vaš broj izgleda puno ljepše. 

Dat ću vam jedan primjer to vidjeti kako rekurzivna procedura mogla biti definirana. Dakle, ako ste upoznati s ovim iz matematike klase prije mnogo godina, Ima nešto zove faktorijalni funkcija, što je obično označen kao uskličnik, koji definira se preko svih pozitivnih integers. A način na koji je n faktorijalni izračunava je li pomnožiti sve brojeve manje od ili jednaka n together-- svi cijeli brojevi manje od ili jednak N zajedno. 

Dakle 5 faktorijalni je 5 puta 4 puta 3 puta 2 puta 1. A 4 faktorijalni je 4 puta 3 puta 2 puta 1 i tako dalje. Vi dobijete ideju. 

Kao programera, mi ne koristiti N, uskličnik. Tako ćemo definirati faktorski djeluju kao činjenicu n. A mi ćemo koristiti faktorijel stvoriti rekurzivna rješenje problema. I mislim da bi mogli naći da je puno više vizualno atraktivan nego iterativni Verzija za to, što ćemo također uzeti pogledati u trenutku. 

Dakle ovdje su par facts-- dosjetka intended-- O factorial-- faktorijalni funkcija. Faktorijel 1, kao što sam rekao, je 1. Faktorijel 2 je 2 puta 1. Faktorijel 3 je 3 puta 2 puta 1, i tako dalje. Razgovarali smo o 4 i 5 već. 

No, gledajući to, nije li to istina? Nije faktorijel 2 samo 2 puta faktorijel 1? Mislim, faktorski od 1 1. Pa zašto ne možemo samo reći da je, budući faktorijalni 2 je 2 puta 1, To je zapravo samo 2 puta faktorijel od 1? 

A onda se širi tu ideju, nije faktorski 3 samo 3 puta faktorijel 2? A faktorijalni 4 je 4 puta faktorijel 3, i tako dalje? U stvari, faktorijalni bilo koji broj mogu jednostavno biti izražena, ako smo vrsta od nose ovo zauvijek. Možemo vrsta generalizirati faktorijel problema kao što je n puta faktorijalni n minus 1. To je n puta proizvod sve brojeve manje od mene. 

Ova ideja, ova generalizacija problema, omogućuje nam da rekurzivno definirati faktorsku funkciju. Kada definirate funkciju rekurzivno, postoji dvije stvari koje trebaju biti dio toga. Morate imati nešto što se zove osnovni scenarij, koji, kada ga aktiviraju, će zaustaviti rekurzivni postupak. 

Inače, funkcija koja poziva itself-- kao što ste mogli imagine-- mogao ići na zauvijek. Funkcija poziva funkciju poziva funkcijske pozive funkcija poziva funkcije. Ako nemate način kako ga zaustaviti, vaš program će biti učinkovito zaglavio u beskonačnu petlju. To će se sudariti s vremenom, jer će ponestati memorije. Ali to je uz točku. 

Moramo imati neki drugi način da se zaustavi stvari osim našeg programa pad sustava, jer program koji ruši se vjerojatno nije lijepa ili elegantne. I tako mi to nazivamo osnovnom scenariju. To je jednostavno rješenje na problem koji zaustavlja rekurzivna proces iz pojavio. Dakle, to je jedan dio rekurzivna funkcija. 

Drugi dio je rekurzivna slučaj. I ovo je mjesto gdje se rekurzija zaista i dogoditi. Ovo je mjesto gdje Funkcija će se zvati. 

Neće se pozvati na točno isti način na koji je bio pozvan. To će biti neznatno varijacije koji čini problem je to pokušava riješiti teeny malo manji. Ali to uglavnom prolazi mužjak rješavanja većinu rješenja na drugi poziv niz liniju. 

Koji od ovih pogleda kao osnovnog ovdje slučaj? Koji od tih izgleda kao Najjednostavnije rješenje problema? Imamo hrpu factorials, a mi mogao nastaviti ide on-- 6, 7, 8, 9, 10, i tako dalje. 

No, jedan od tih izgleda kao dobar slučaj da je osnovni scenarij. To je vrlo jednostavno rješenje. Ne morate učiniti ništa posebno. 

Faktorijel od 1. samo je 1. Ne morate učiniti bilo množenja uopće. Čini se kao da ćemo pokušati riješiti ovaj problem, i moramo zaustaviti rekurzije negdje, smo vjerojatno želite da se zaustavi da kad dođemo do 1. Mi ne želimo zaustaviti prije toga. 

Dakle, ako smo definiranja naš faktorijalni funkcija, ovdje je kostur za Kako bismo mogli to učiniti. Moramo uključiti u te dvije things-- osnovni slučaj i rekurzivni slučaj. Što je osnovni scenarij? Ako je n jednak 1, povratak 1-- to stvarno jednostavan problem riješiti. 

Faktorijel od 1 1. To nije 1 puta ništa. To je samo 1. To je vrlo jednostavno činjenica. I tako to može biti naša baza slučaj. Ako biste smo prošli 1 u ovo funkcija, samo ćemo se vratiti 1. 

Što je rekurzivna Slučaj je vjerojatno izgledati? Za svaki drugi broj osim 1, što je uzorak? Pa, ako ćemo uzimati faktorijel n, to je n puta faktorijalni n minus 1. 

Ako nas da faktorijel 3, to je 3 puta faktorijalni 3 minus 1, ili 2. I tako, ako nismo gleda na 1, inače Povratak n puta faktorijalni n minus 1. To je prilično jednostavan. 

A radi ima malo čišći i elegantniji broj, znam da ako imamo jednog retka petlje ili jednog retka uvjetna grana, možemo riješiti sve od vitičastih zagrada oko njih. Tako možemo objediniti to to. To je točno isti funkcionalnost kao ovaj. 

Samo oduzimanje kovrčavu aparatić, jer postoji samo jedan redak unutar tih uvjetnih grana. Dakle, to se ponašaju identično. Ako je n jednak 1, povratak 1. Inače vratiti n puta faktorijel n minus 1. Tako činimo problem manji. Ako je n počinje kao 5, idemo vratiti 5 puta faktorijel 4. A vidjet ćemo za minutu, kada govorimo o stack-- poziva u drugom videu gdje smo razgovarati o pozvati stack-- ćemo naučiti o tome zašto upravo taj proces funkcionira. 

No, dok faktorijalni 5 kaže vratiti 5 puta faktorijalni 4 i 4 će reći, u redu, dobro, povratak 4 puta faktorijel 3. I kao što možete vidjeti, mi smo vrsta približava 1. Mi smo sve bliže i bliže tom osnovnom scenariju. 

A kad smo hit bazu slučaj, svim prethodnim funkcija imaju odgovor su tražili. Faktorijalni 2 je govorio povratak 2 puta faktorijel od 1. Pa, faktorijel 1 vraća 1. Tako je poziv za faktorski 2 može vratiti 2 puta 1, i dati da leđa faktorijel 3, koji je čeka za taj rezultat. 

I onda se može izračunati njegov rezultat, 3 puta 2 je 6, i dati ga natrag faktorijel 4. I opet, imamo Video na stogu poziva ako je to ilustrirano malo više nego što govorim sada. No, to je to. To samo po sebi je rješenje za izračunavanje faktorijel broja. 

To je samo četiri linije koda. To je prilično cool, zar ne? To je vrsta seksi. 

Tako je u cjelini, ali ne Uvijek, rekurzivna funkcija može zamijeniti petlju se u nerekurzivni funkcija. Dakle ovdje, rame uz rame, je iterativan verzija faktorska funkcije. Obje od tih izračunati upravo ista stvar. 

Obojica su izračunali faktorijel n. Verzija lijevo koristi rekurzija za to. Verzija desno koristi iteracija za to. 

I napomena, moramo proglasiti varijabla cijeli proizvod. A onda smo petlje. Tako dugo dok je n veći od 0, zadržati množenjem taj proizvod po n i decrementing n do možemo izračunati proizvod. Dakle, ove dvije funkcije, opet, učiniti istu stvar. Ali oni ne to učiniti u točno na isti način. 

Sada je moguće imaju više od jedne baze Slučaj ili više rekurzivni slučaj, ovisno na što vaš funkcija pokušava učiniti. Vi ne nužno samo ograničeni na jedan osnovni scenarij ili jedan rekurzivna slučaj. Dakle, primjer nečega s više slučajeva baznih možda this-- Fibonacci nizu broj. 

Vi svibanj podsjetiti iz osnovnoškolci dana da je Fibonacci slijed definiran kao this-- prvi element je 0. Drugi element je 1. Oboje su to samo po definiciji. 

Zatim svaki drugi element koji definira kao zbroj n i n minus 1 minus 2. Tako trećeg elementa će biti 0 i 1 je 1. A onda Četvrti element bi drugi element, 1, plus treći element, 1. I to bi bilo 2. I tako dalje i tako dalje. 

Dakle, u ovom slučaju, imamo dvije bazne slučajeve. Ako je n jednak 1, povratak 0. Ako je n jednak 2, povratak 1. Inače, povratak Fibonacci n minus 1 plus Fibonacci n minus 2. 

Dakle, to je više slučajeva baze. Što je više rekurzivnih slučajevima? Pa, ima nešto zove Collatz nagađanje. Neću reći, znate što je to, jer to je zapravo naš konačni Problem za ovaj video. I to je naša vježbe raditi na zajedno. 

Dakle, ovdje je ono što je Collatz nagađanje is-- to se odnosi na sve pozitivni cijeli broj. I to pretpostavlja da je Uvijek je moguće vratiti na 1 ako slijedite ove korake. Ako n predstavlja 1, zaustavi. Moramo vratiti na 1 ako je n 1. 

Inače, proći kroz ova Proces opet na n podijeljena 2. I vidjeti ako možete dobiti natrag na 1. Inače, ako je n neparan, proći kroz taj proces opet na 3N plus 1, ili 3 puta n plus 1. Dakle, ovdje imamo jedan osnovni slučaj. Ako je n jednak 1, zaustavi. Mi ne radite bilo više rekurzija. 

No, imamo dva rekurzivni slučajeva. Ako je n čak, mi radimo jedan Rekurzivno Slučaj, pozivajući n podijeljena 2. Ako je n neparan, mi drugačiji rekurzivna slučaj na 3 puta n plus 1. 

I tako je cilj za ovu videu uzeti sekundu, pauziranje videozapisa, i pokušati ovo napisati rekurzivna funkcija Collatz gdje prolaze u vrijednosti n, te izračunava koliko ih koraka potrebno da biste dobili na 1 ako počnete od n i slijedite one korake iznad. Ako n predstavlja 1, potrebno je 0 koraka. Inače, to će uzeti jedan korak plus međutim mnogo koraka da preuzima bilo n podijeljeno s 2 ako je n čak, ili 3n plus 1 ako je n neparan. 

Sada sam stavio gore na zaslonu ovdje par ispitnih stvari za vas, par testova predmeta za vas, vidjeti što ti razni Collatz brojevi, i ilustracija od koraka koje treba proći kroz tako da možete vidjeti kakve taj proces u akciji. Dakle, ako je n jednak 1, Collatz n je 0. Vi ne morate učiniti ništa se vratiti do 1. Ti si već tamo. 

Ako je n 2, potrebno jedan korak da se na 1. Možete početi s 2. Pa, 2 nije jednak 1. Dakle, to će biti jedan korak plus no mnogi ga koraka poprima n podijeljena 2. 

2 podijeljeno s 2 je 1. Dakle, to traje jedan korak plus međutim mnogo koraka koje je potrebno za 1. 1 traje nula korake. 

Za 3, kao što možete vidjeti, postoji dosta koraka koji su uključeni. Možete ići od 3. A onda idete 10, 5, 16, 8, 4, 2, 1. Potrebno je sedam koraka za povratak na 1. I kao što možete vidjeti, postoji Par drugi test slučajevi ovdje testirati svoj program. Pa opet, pauziranje videozapisa. A ja ću skočiti natrag sada što je stvarni proces je ovdje, što je to pretpostavka je. 

Pogledajte ako možete shvatiti kako definirati Collatz n tako da se izračunava koliko korake koje je potrebno da se na 1. Pa nadajmo se, da ste zastao video a ne samo me čeka vam dati odgovor. Ali, ako ste, dobro, Ovdje je odgovor svejedno. 

Dakle, ovdje je moguće definicija funkcije Collatz. Naša baza case-- ako je n jednaki 1, vraćamo 0. To ne uzeti bilo koraci da se vratim na 1. 

Inače, imamo dva rekurzivni cases-- jedan za parnih brojeva i jedan za ak. Način na koji sam testirati čak i brojeva je provjeriti ako je n mod 2 jednaka 0. To je u osnovi, opet, postavlja pitanje, ako sjetiti što mod is-- ako podijeli N 2 je nema ostatak? To bi bio paran broj. 

I tako, ako je n mod 2 jednaka 0 je Ispitivanje je to paran broj. Ako je tako, želim se vratiti 1, jer ovo je svakako uzimanje jedan korak plus Collatz od bez obzira na broj je polovica mene. Inače, želim se vratiti 1 plus Collatz od 3 puta n plus 1. To je bio drugi rekurzivna korak koji smo mogao uzeti za izračun Collatz-- broj koraka je potrebno da se vrati na 1 daje broj. Dakle, nadamo se, ovaj primjer dao malo od okusom rekurzivnih postupaka. Nadam se, mislite broj je malo ljepše ako se provodi u elegantnoj, rekurzivni način. No, čak i ako nije, rekurzija je stvarno moćan alat svejedno. I to je definitivno nešto dobiti svoju glavu okolo, jer ćete biti u stanju stvoriti prilično kul programi koriste rekurzija koji bi inače biti složen pisati ako koristite petlje i iteracija. Ja sam Doug Lloyd. Ovo je CS50.