>> 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.