ZAMYLA: În scopul de a înțelege recursivitate, trebuie să vă înțelegem mai întâi recursivitate. Având recursivitate în programul de mijloace de proiectare care le-au auto-referențială definiții. Structuri de date recursive, de exemplu, sunt structuri de date care se includ în definițiile lor. Dar astăzi, am de gând să se concentreze pe functii recursive. 

Amintiti-va ca funcțiile lua intrări, argumente, și să se întoarcă o valoare ca lor reprezentată de ieșire această schemă de aici. Ne vom gândi din cutie ca organism de funcția, care conține setul de instrucțiuni care să interpreteze de intrare și să ofere o ieșire. Având o privire mai atentă în interiorul corpului funcția ar putea dezvălui apeluri la alte funcții, precum și. Ia această funcție simplă, foo, că are un singur șir ca intrare și printuri cât de multe scrisori că șir are. Funcția strlen, de lungime șir, este numit, a cărui ieșire este necesar pentru apelul la printf. 

Acum, ceea ce face o funcție recursive special este că se numește. Ne putem reprezenta această recursive numesc cu acest Săgeată portocalie looping înapoi la sine. Dar executarea se din nou numai ca va face un alt apel recursiv, și altul și altul. Dar funcțiile recursive nu poate fi infinit. Ei trebuie să se încheie într-un fel, sau dvs. Programul va rula pentru totdeauna. 

Deci, avem nevoie pentru a găsi o modalitate de a sparge din apelurile recursive. Noi numim acest caz de bază. În cazul în care condiția caz de bază este îndeplinită, funcția returnează fără a face un alt apel recursiv. Ia această funcție, hi, o funcție gol care are o int n ca intrare. Scenariul de bază este pe primul loc. Dacă n este mai mică decât zero, la revedere de imprimare și Pentru a reveni toate celelalte cazuri, Funcția va imprima hi și executa apelul recursiv. Un alt apel la funcția de hi cu o valoare de intrare decrementat. 

Acum, chiar dacă ne-am imprima hi, Funcția nu se va termina până când vom reveni tip de întoarcere, în acest caz nule. Deci, pentru orice n alta decât cazul de bază, această funcție va întoarce hi hi de n minus 1. Din moment ce această funcție este nulă, deși, ne-am nu va tip în mod explicit reveni aici. Vom executa doar funcția. Deci, de asteptare hi (3) se vor imprima hi și executa hi (2), care execută hi (1), un care execută hi (0), unde condiție caz de bază este îndeplinită. Deci, hi (0) imprimă revedere și se întoarce. 

OK. Deci, acum că ne-am înțeles elementele de bază ale functii recursive, de care au nevoie cel puțin un caz de bază, precum și un apel recursiv, haideți să trecem la o exemplu mai semnificativ. Unul care nu doar întoarce nule, indiferent de ce. 

Să aruncăm o privire la factorial operație utilizate cel mai frecvent în calcule de probabilitate. Factorial n este produs de fiecare întreg pozitiv mai puțin și egal cu n. Cinci astfel factorial este de 5 ori de 4 ori De 3 ori 2 ori 1 pentru a da 120. Patru factorial este de 4 ori de 3 ori De 2 ori pentru a da un 24. Și se aplică aceeași regulă pentru orice număr întreg pozitiv. 

Deci, cum am putea scrie un recursiv functie care calculeaza factorialul de un număr? Ei bine, avem nevoie pentru a identifica atât cazul de bază și apelul recursiv. Apelul recursiv va fi la fel pentru toate cazurile, cu excepția bazei caz, ceea ce înseamnă că va trebui să găsi un model care ne va da noastre rezultatul dorit. 

Pentru acest exemplu, a se vedea cât de 5 factorial implică înmulțirea 4 de 3 până la 2 până la 1 Și că foarte același multiplicare este găsit aici, definiție de 4 factorial. Deci, vedem că 5 factorial este doar de 5 ori 4 factorial. Acum, se aplică acest model la 4 factoriale, precum și? Da. Vedem că 4 factorial conține multiplicare de 3 ori de 2 ori 1, foarte aceeași definiție ca și 3 factorial. Deci 4 factorial este egală cu de 4 ori 3 factorială, și așa mai departe și așa mai departe noastră model lipeste până la 1 factorial, care prin definiție este egal cu 1. 

Nu există nici o altă pozitiv numere întregi stânga. Așa că avem modelul de apelul nostru recursiv. n factorial este egal cu de n ori factorialul lui n minus 1. Și cazul nostru de bază? Care va fi doar definiția noastră din 1 factorial. 

Deci, acum putem trece la scris cod pentru funcția. Pentru cazul de bază, vom avea condiție n este egal cu 1, unde ne vom intoarce 1. Apoi se deplasează pe apelul recursiv, ne vom intoarce de n ori factorial n minus 1. 

Acum, haideți să testați acest noastră. Să încercăm factorial 4. Pe funcția noastră este egal la 4 ori factorial (3). Factorial (3) este egal cu De 3 ori factoriale (2). Factorial (2) este egală cu de 2 ori factorial (1), care returnează 1. Factorial (2) se întoarce acum de 2 ori 1, 2. Factorial (3) se pot întoarce acum 3 ori 2, 6. Și, în sfârșit, factorial (4) returnează 4 ori 6, 24. 

Dacă sunteți întâmpină nici o dificultate cu apelul recursiv, pretinde că funcția funcționează deja. Ce vreau să spun prin asta este că ar trebui să încredere în apelurile recursive pentru a reveni valorile corecte. De exemplu, dacă știu că factorial (5) este egal cu de 5 ori factorial (4), am de gând să aibă încredere că factorial (4), va da-mi 24. Ganditi-va ca o variabilă, dacă va fi, ca si cum ai deja definit factorial (4). Deci, pentru orice factorial (n), este produsul de n și factorialul anterior. Și acest factorial anterior este obținut prin apelarea factorial n minus 1. 

Acum, vezi dacă poți să pună în aplicare un funcționeze recursiv-te. Încărcați până terminalul, sau run.cs50.net, și de a scrie o sumă funcție care are un număr întreg n și returnează Suma de toate pozitive consecutive numere întregi de la 1 la n. I-am scris din sumele de unele valori pentru a vă ajuta nostru. În primul rând, dau seama de condiție caz de bază. Apoi, uita-te la suma (5). Poți să-l exprime în termeni de altă sumă? Acum, ce putem spune despre suma (4)? Cum vă puteți exprima suma (4) în ceea ce privește o altă sumă? 

Odată ce aveți suma (5) și suma (4) exprimată în termeni de alte sume, a se vedea dacă vă puteți identifica un model pentru suma (n). Dacă nu, încercați alte câteva numere și exprima sumele lor în ceea ce privește alte numere. Prin identificarea modele de discret numere, esti bine pe cale de a identificarea model pentru orice n. 

Recursivitate este un instrument foarte puternic, astfel, desigur, nu se limitează la funcții matematice. Recursivitatea poate fi folosit foarte eficient atunci când se ocupă cu copaci, de exemplu. Check out scurt pe copaci pentru o mai mult analiză amănunțită, dar pentru acum amintesc că arbori de căutare binare, în special, sunt formate din noduri, fiecare cu o valoare și două indicii nod. De obicei, aceasta este reprezentată de nod părinte având o linie de indicare la nodul copil din stânga și cea la nodul copil din dreapta. Structura unei căutări binare copac se pretează bine la o căutare recursive. Apelul recursiv trece fie în la stânga sau la nodul din dreapta, dar mai mult din care în scurt copac. 

Presupunem că doriți să efectuați o operație pe fiecare nod într-un arbore binar. Cum s-ar putea merge despre asta? Ei bine, ai putea scrie o recursive funcție care efectuează operația pe nodul părinte și face o recursiv apela la aceeași funcție, trece în stânga și noduri copil dreapta. De exemplu, această funcție, foo, că schimba valoarea unui nod dat și toți copii săi la 1. Cazul de bază a unei cauze nod nule funcția de a reveni, indicând că nu există noduri a lăsat în care sub-arbore. 

Să mergem prin ea. Primul-mamă este de 13. Vom schimba valoarea la 1, și apoi apel Funcția noastră pe stânga, precum și ca dreapta. Funcția, foo, este numit pe stânga sub-arbore întâi, așa nodul stâng vor fi realocate la 1 și va fi foo fi numit pe copii că nod, întâi stânga și apoi dreapta, și așa mai departe și așa mai departe. Și spune-le că sucursalele nu au orice mai mulți copii, astfel încât același proces va continua pentru copii potrivite până noduri întreg arborele sunt reatribuit 1. 

După cum puteți vedea, nu sunt limitate la doar un apel recursiv. La fel de multe ca va face treaba. Ce se întâmplă dacă ați avut un copac în care fiecare nod a avut trei copii, Stânga, de mijloc, și nu? Cum ar fi editarea foo? Ei bine, simplu. Trebuie doar să adăugați un alt apel recursiv și trece la indicatorul nod de mijloc. 

Recursivitate este foarte puternic și nu a menționa elegant, dar poate fi un concept greu la început, astfel încât să fie pacient și ia timp. Începeți cu cazul de bază. Este, de obicei, cel mai ușor de a identifica, și apoi puteți lucra înapoi de acolo. Stii ca ai nevoie pentru a ajunge la dvs. cazul de bază, astfel încât s-ar putea vă dau câteva indicii. Încercați să-și exprime un caz specific în ceea ce privește alte cazuri, sau în sub-seturi. 

Vă mulțumim pentru vizionarea acestui scurt. Cel puțin, acum aveți posibilitatea să înțelege glumele de acest gen. Numele meu este Zamyla, iar acest lucru este CS50. 

Ia această funcție, hi, o Funcția gol care ia un int, n, ca intrare. Scenariul de bază este pe primul loc. Dacă n este mai mic decât 0, print "La revedere" și retur.