[MUSIC JOC] 

DOUG LLOYD: Probabil Crezi că cod este folosit doar pentru a realiza o sarcină. Ai scrie. Ea face ceva. Asta e destul de mult. 

Ai compilați. Rulați programul. Tu esti bine să plec. 

Dar crezi sau nu, în cazul în care vă codul de mult timp, de fapt, s-ar putea veni tu pentru a vedea cod ca ceva care este frumos. Se rezolvă o problemă în un mod foarte interesant, sau e doar ceva cu adevărat elegant despre felul in care arata. S-ar putea râde la mine, dar e adevărat. Și recursivitate este o modalitate la fel de a obține această idee Codul de frumos, elegant cu aspect. Se rezolvă problemele în moduri care sunt interesante, ușor de vizualizat, și surprinzător de scurt. 

Lucrările mod recursivitate este, o funcție recursivă este definit ca o funcție care solicită se ca parte a executării sale. Care ar putea părea un pic ciudat, si vom vedea un pic despre modul în care funcționează într-o clipă. Dar, din nou, acestea Procedurile sunt recursive O să fie atât de elegant pentru că ei vor pentru a rezolva această problemă, fără având toate aceste alte funcții sau aceste bucle lungi. Veți vedea că aceste recursive Procedurile vor arata atat de scurt. Și ei cu adevărat de gând să facă codul arata mult mai frumos. 

Am să vă dau un exemplu de această pentru a vedea cum o procedură recursivă poate fi definit. Deci, dacă sunteți familiarizați cu această de la ora de matematică mulți ani în urmă, E ceva numit Funcția factorială, care este de obicei notat ca un semn de exclamare, care este definită peste toate numere întregi pozitive. Și modul în care n factorial este calculat este vă înmulțiți toate numerele mai puțin sau egal cu n together-- toate numerele întregi mai puțin decât sau egală cu n împreună. 

Deci 5 factorial este de 5 ori 4 ori 3 ori 2 ori 1. Și 4 factorial este de 4 ori De 3 ori 2 ori 1 și așa mai departe. Ai idee. 

Ca programatori, nu avem utiliza n, semn de exclamare. Deci, vom defini factorialului funcționează ca fapt de n. Și vom folosi pentru a crea factorial o soluție recursivă a unei probleme. Și cred că ar putea găsi că este mult mai vizual atrăgătoare decât iterativ versiune a acestui, care vom lua de asemenea, o privire la într-o clipă. 

Deci, aici sunt un cuplu de joc de cuvinte facts-- intended-- despre factorial-- Funcția factorial. Factorialul 1, așa cum am spus, este o. Factorialul 2 este de 2 ori 1. Factorialul 3 este 3 ori de 2 ori 1, și așa mai departe. Am vorbit despre 4 și 5 deja. 

Dar uita la asta, nu e adevărat? Nu este factorială a 2 doar 2 ori factorial de 1? Adică, factorialul 1 este de 1. Deci, de ce nu putem spune doar că, deoarece factorial de 2 este de 2 ori 1, este într-adevăr doar de 2 ori factorialul 1? 

Și apoi se extinde această idee, nu este factorialul 3 doar de 3 ori factorial de 2? Și factorialul 4 este de 4 ori factorialul 3, și așa mai departe? De fapt, factorialul de orice număr poate doar fi exprimată dacă ne-am cam a efectua acest lucru pentru totdeauna. Putem fel de generaliza problema factorial ca este de n ori factorial de n minus 1. Este n ori produsul de toate numerele mai mici decât mine. 

Această idee, aceasta generalizare a problemei, ne permite să recursiv defini funcția factorial. Când definiți o funcție recursiv, nu e două lucruri care trebuie să fie o parte din ea. Ai nevoie de ceva numit un cazul de bază, care, atunci când îl declanșa, va opri procesul recursiv. 

În caz contrar, o funcție care solicită itself-- ca s-ar putea imagine-- ar putea continua la nesfârșit. Funcția apelează funcția solicită apelurile de funcții funcția apelează funcția. Dacă nu aveți un mod să-l oprească, programul va fi blocat în mod eficient la o buclă infinită. Acesta se va prăbuși în cele din urmă, deoarece acesta va alerga afară de memorie. Dar asta e pe langa punctul de. 

Avem nevoie de un alt mod de a opri lucruri în afară de crashing programul nostru, deoarece un program care blochează este probabil, nu frumos sau elegant. Și astfel noi numim acest caz de bază. Aceasta este o soluție simplă la o problemă care se oprește procesul recursiv de la care apar. Deci asta este o parte din o funcție recursivă. 

A doua parte este cazul recursiv. Și acest lucru este în cazul în care recursivitate va avea loc de fapt. Acest lucru este în cazul în care Funcția se va apela. 

Ea nu se va apela în exact la fel a fost numit. Va fi o ușoară variație care face problema este încearcă să rezolve un pic teeny mici. Dar, în general, trece dolar de rezolvare cea mai mare parte a soluției la un apel diferit pe linie. 

Care dintre aceste priviri cum ar fi cazul de bază aici? Care dintre aceste arata ca simplă soluție la o problemă? Avem o grămadă de factorialele, și am putea continua merge on-- 6, 7, 8, 9, 10, și așa mai departe. 

Dar unul dintre aceste arata ca un caz bun pentru a fi cazul de bază. Este o soluție foarte simplă. Noi nu trebuie să facem nimic special. 

Factorialul 1 este la doar 1. Noi nu trebuie să facem nici un multiplicare, la toate. Se pare că, dacă vrem pentru a încerca și de a rezolva această problemă, si avem nevoie pentru a opri recursivitate undeva, probabil că doriți să opriți aceasta când vom ajunge la 1. Noi nu vrem să se oprească înainte de asta. 

Deci, dacă suntem definirea Funcția noastră factorial, aici e un schelet de cum am putea face asta. Avem nevoie să conectați în cele două lucruri-- cazul de bază și în cazul recursiv. Care e cazul de bază? Dacă n este egal cu 1, se întoarcă 1-- e o problemă foarte simplu de rezolvat. 

Factorialul 1 este de 1. Este nu 1 ori nimic. E doar o. Este un fapt foarte ușor. Și astfel încât să poată fi cazul nostru de bază. Dacă suntem trecut 1 în această funcție, vom returna doar 1. 

Care este recursiv caz, probabil, arata ca? Pentru fiecare alt număr în afară de 1, ceea ce este modelul? Ei bine, dacă luăm factorialul lui n, Este n ori factorialul lui n minus 1. 

Dacă luăm factorialul 3, e de 3 ori factorialul 3 minus 1, sau 2. Și așa, dacă nu suntem uita la 1, în caz contrar întoarcere n ori a factorial de n minus 1. E destul de simplu. 

Și de dragul de a avea ceva mai curat și mai elegant cod, știu că, dacă avem bucle singură linie sau o singură linie de sucursale condiționale, putem scăpa de cele de mai acolade în jurul lor. Astfel încât să putem consolida acest lucru acest lucru. Acest lucru are exact la fel funcționalitate ca aceasta. 

Eu doar ținând departe cret bretele, pentru că nu există decât o singură linie în interiorul acestor ramuri condiționate. Astfel încât acestea să se comporte identic. Dacă n este egal cu 1, randamentul 1. În caz contrar, se întoarcă de n ori factorialul lui n minus 1. Deci facem problema mici. Dacă n începe ca 5, vom a reveni de 5 ori factorialul 4. Și vom vedea într-un minut atunci când vorbim despre stack-- apel într-un alt film în cazul în care vorbim despre apel stack-- vom afla despre ce exact acest proces funcționează. 

Dar în timp ce factorial de 5 spune reveni de 5 ori factorial de 4, și 4 se va spune, OK, bine, întoarcere 4 ori factorial de 3. Și, după cum puteți vedea, suntem un fel de abordare 1. Ne apropiem și mai aproape de acest caz de bază. 

Și odată ce ne-am lovit cazul de bază, toate funcțiile anterioare au răspuns ei căutau. Factorial de 2 spunea retur 2 ori factorial de 1. Ei bine, factorial de 1 revine 1. Deci, apelul pentru factorial de 2 poate returna de 2 ori 1, și să dea înapoi la factorial de 3, care este în așteptare pentru acest rezultat. 

Si apoi poate calcula sale de rezultat, de 3 ori 2 este de 6, și da înapoi factorial de 4. Și din nou, avem o video de pe stiva de apel în cazul în care acest lucru este ilustrat un pic mai mult decât ceea ce spun acum. Dar asta este. Numai acest lucru este soluția la calcularea factorialul unui număr. 

E doar patru linii de cod. Asta e destul de tare, nu? E un fel de sexy. 

Deci, în general, dar nu întotdeauna, o funcție recursivă poate înlocui o buclă într-o Funcția non-recursive. Deci, aici, cot la cot, este iterativ versiune a funcției factorial. Ambele calcula exact același lucru. 

Amândoi calcula factorialul lui n. Versiunea pe stânga foloseste recursivitate să o facă. Versiunea pe dreapta foloseste repetare a face acest lucru. 

Și notificare, trebuie să declare o variabilă un produs număr întreg. Și apoi am bucla. Atât timp cât n este mai mare decât 0, am păstra înmulțirea acest produs de n și decrementarea n până vom calcula produsul. Deci, aceste două funcții, din nou, face exact același lucru. Dar ei nu o fac în exact în același mod. 

Acum, este posibil să se au mai mult de un punct caz sau mai mult de un caz recursiv, în funcție asupra a ceea ce funcția încearcă să facă. Tu nu sunt neapărat doar limitate la un singur caz de bază sau un singur recursive caz. Deci un exemplu de ceva cu cazuri de bază multiple ar putea fi asta: Secvență număr Fibonacci. 

Vă amintiți de la zile de școală elementară că secvența Fibonacci este definit ca asta: primul element este 0. Al doilea element este de 1. Ambele sunt doar prin definiție. 

Apoi fiecare alt element este definit ca suma n minus 1 și n minus 2. Deci al treilea element ar fi 0 plus 1 este 1. Apoi al patrulea element ar fi al doilea element, 1, plus al treilea element, 1. Și care ar fi de 2. Și așa mai departe și așa mai departe. 

Deci, în acest caz, avem două cazuri de bază. Dacă n este egal cu 1, randamentul 0. Dacă n este egal cu 2, se întoarcă 1. În caz contrar, se întoarcă Fibonacci de n minus 1 plus Fibonacci de n minus 2. 

Așa că e cazul de bază multiple. Ce zici de mai multe cazuri recursive? Ei bine, e ceva numit conjectura COLLATZ. Eu nu am de gând să spun, Știi ce este că, pentru că este de fapt ultima noastră problemă pentru acest videoclip special. Și este exercițiul nostru să lucreze împreună. 

Deci, aici e ceea ce COLLATZ conjecture este-- se aplică pentru orice număr întreg pozitiv. Și se speculează că este întotdeauna posibil să mă întorc la 1, dacă urmați acești pași. Dacă n este 1, opri. Avem înapoi la 1 dacă n este 1. 

În caz contrar, trece prin aceasta proces din nou pe n împărțit la 2. Și a vedea dacă puteți obține înapoi la 1. În caz contrar, dacă n este impar, trece prin acest proces din nou pe 3n plus 1, sau de 3 ori n plus 1. Deci, aici avem un singur caz de bază. Dacă n este egal cu 1, opri. Nu facem nici mai recursivitate. 

Dar avem două cazuri recursive. Dacă n este chiar, vom face o recursive caz, de asteptare n împărțit la 2. Dacă n este impar, facem un alt caz recursiv pe 3 ori n plus 1. 

Și astfel obiectivul pentru acest videoclip este pentru a lua un al doilea, întrerupe clipul video, și să încerce și să scrie acest Funcția recursive COLLATZ în cazul în care va trece într-o valoare n, și se calculează câte măsurile pe care le nevoie pentru a ajunge la 1, dacă începeți de la n și să urmați acești pași deasupra. Dacă n este 1, este nevoie de 0 pași. În caz contrar, se va ia un pas plus cu toate acestea mulți pași pe care le ia pe fiecare n împărțit la 2, dacă n este chiar, sau 3n plus 1 dacă n este impar. 

Acum, am pus pe ecran aici o serie de lucruri de testare pentru tine, un cuplu de cazuri teste pentru tine, pentru a vedea ce aceste diferite numere COLLATZ sunt, și, de asemenea, o ilustrare cu privire la măsurile care trebuie să fie trecut prin astfel încât să puteți un fel de a vedea acest proces în acțiune. Deci, dacă n este egal cu 1, COLLATZ lui n este 0. Tu nu trebuie să faci orice să mă întorc la 1. Ești deja acolo. 

Dacă n este 2, este nevoie un pas pentru a ajunge la 1. Începi cu 2. Ei bine, 2 nu este egal cu 1. Deci, va fi un pas Cu toate acestea, plus mai multe etape IT capătă n împărțit la 2. 

2 împărțit la 2 este 1. Deci, este nevoie de un pas în plus, dar mulți pași este nevoie de timp de 1. 1 ia de zero pași. 

Pentru 3, după cum puteți vedea, există destul de câțiva pași implicate. Tu du-te de la 3. Și apoi te duci la 10, 5, 16, 8, 4, 2, 1. Este nevoie de șapte pași pentru a obține înapoi la 1. Și, după cum puteți vedea, există o cuplu alte cazuri de testare aici pentru a testa programul. Deci, din nou, întrerupe clipul video. Și voi merge sări înapoi acum la ce procesul real este aici, ceea ce aceasta presupunere este. 

Vezi dacă poți da seama cum de a defini COLLATZ de n astfel încât acesta calculează câte pașii este nevoie pentru a ajunge la 1. Deci sperăm, le-ați întrerupt video și nu sunt doar de așteptare pentru mine pentru a vă oferi răspunsul aici. Dar dacă sunteți, ei bine, aici e răspunsul oricum. 

Deci, aici este o posibilă definiție a funcției COLLATZ. Baza noastra de case-- dacă n este egală cu 1, ne întoarcem 0. Aceasta nu ia nici o pași pentru a obține înapoi la 1. 

În caz contrar, avem două cases-- recursiv unul pentru numerele chiar și unul pentru ciudat. Modul în care am testa pentru numere chiar este de a verifica dacă n mod 2 este egal cu 0. Aceasta este, în principiu, din nou, pune întrebarea, dacă vă amintiți ce este-- mod dacă am divide n prin 2 nu există nici o rest? Asta ar fi un număr par. 

Și așa că, dacă n mod 2 este egal cu 0 este Testarea este aceasta un număr par. Dacă este așa, vreau să se întoarcă 1, pentru că acest lucru este cu siguranta luând un pas plus COLLATZ de indiferent de numărul este de jumătate din mine. În caz contrar, vreau să se întoarcă 1 plus COLLATZ de 3 ori n plus 1. Asta a fost de altă parte pas recursiv pe care le ar putea lua pentru a calcula Collatz-- numărul de trepte este nevoie să mă întorc la 1 atribuie un număr. Deci sperăm că, acest exemplu ți-a dat un pic de un gust de proceduri recursive. Sperăm că, crezi că este un cod puțin mai frumos dacă ar fi aplicate într-un mod elegant, recursiv. Dar chiar dacă nu, recursivitate este un instrument foarte puternic cu toate acestea. Și așa este cu siguranta ceva pentru a obține capul în jurul valorii de, pentru că vei fi capabil de a crea programe destul de rece, folosind recursivitate care altfel ar putea fi dificil de a scrie dacă utilizați bucle și repetare. Sunt Doug Lloyd. Acest lucru este CS50.