>> ZAMYLA: Da bi se razumjelo rekurzija, morate
prvi razumjeti rekurziju.
Nakon što je rekurzija u programu dizajna sredstvima da imate samoodnoseću
definicije.
Rekurzivnih struktura podataka, na primjer, su strukture podataka koje
uključuju u njihove definicije.
Ali danas, mi ćemo se usredotočiti na rekurzivnim funkcijama.
>> Sjetite se da je funkcija uzeti ulaza, Argumenti i vratiti vrijednost kao i njihovi
Izlaz zastupa ovaj dijagram ovdje.
Smislit ćemo okvira kao tijelo funkcija, sadrži niz
Upute koji interpretiraju ulaz i osigurati izlaz.
Uzimajući bliži pogled unutar tijela Funkcija mogao otkriti pozive
ostale funkcije.
Iskoristite ovu jednostavnu funkciju, Foo, da traje jedan niz kao ulaz i
ispisuje koliko slova da žica ima.
Funkcija strlen, za duljinu niza, naziva, čiji je izlaz
potreban za poziv na printf.
>> Sada, ono što čini rekurzivna funkcija Poseban je da se zove.
Mi može predstavljati ovu rekurzivna poziv s ovom narančastom strelicom
vraćanja do sebe.
Ali opet se izvršavaju će samo napraviti još jedan rekurzivni poziv, a
još jedan i drugi.
No, rekurzivna funkcija ne može biti beskonačan.
Oni su na kraju nekako, ili tvoje Program će se izvoditi zauvijek.
>> Dakle, moramo naći način da raskine iz rekurzivnih poziva.
Mi to nazivamo osnovni scenarij.
Kad je upoznao osnovni scenarij stanje, Funkcija vraća bez
još jedna rekurzivna poziva.
Iskoristite ovu funkciju, hi, funkcija void koji traje int n kao ulaz.
Baza slučaj na prvom mjestu.
Ako je n manji od nule, print i bye Za povratak svim drugim slučajevima,
Funkcija će ispisati hi i izvršiti rekurzivna poziva.
Još jedan poziv na funkcije bok s smanjene vrijednosti ulaza.
>> Sada, iako smo ispisali hi, Funkcija neće prekinuti sve dok ne
vratiti svoju vrstu povrata, u ovom slučaju praznini.
Dakle, za svaki n, osim osnovnog scenarija, ova funkcija hi hi će se vratiti
n minus 1.
Budući da je ova funkcija void iako smo neće izrijekom upišete povratak ovdje.
Samo ćemo izvršiti funkciju.
Dakle pozivom hi (3) će ispisati hi i izvršavanje hi (2) koji izvodi hi (1) jedan
koji izvršava hi (0), u kojoj osnovni scenarij uvjet zadovoljen.
Dakle hi (0) ispisuje bye i vraća.
>> OK.
Tako da sada možemo razumjeti osnove rekurzivna funkcija, koje su im potrebne
najmanje jedne baze, kao slučaj rekurzivna poziva, neka je premjestiti na
više smisla primjer.
One koji ne samo da se vrate poništiti bez obzira.
>> Idemo pogledati Faktorijalni Operacija se koristi najčešće u
izračuni vjerojatnosti.
Faktorijel n je proizvod svakog pozitivan cijeli broj manji od
i jednak n.
Dakle faktorjela pet je 5 puta 4 puta 3 puta 2 puta 1, čime se dobije 120.
Četiri faktorjela je 4 puta 3 puta 2 puta 1 da se dobije 24.
A isto pravilo vrijedi na bilo koji pozitivni cijeli broj.
>> Pa kako bismo mogli napisati rekurzivna funkcija koja izračunava faktorijel
broja?
Pa, mi ćemo morati identificirati i osnovni scenarij i rekurzivna poziva.
Rekurzivna poziva neće biti isti za svim slučajevima osim za bazu
slučaj, što znači da ćemo morati pronaći model koji će nam dati našim
željeni rezultat.
>> Na ovom primjeru vidimo kako 5 faktorjela uključuje množenjem 4 x 3 za 2 za 1
I to isto množenja nalazi se ovdje,
Definicija 4. faktorjela.
Dakle, vidimo da je 5 faktorjela samo 5 puta 4 faktorjela.
Sada se taj obrazac primjenjuju do 4 faktorjela kao i?
Da.
Vidimo da je 4 faktorjela sadrži Množenje 3 puta 2 puta 1,
Isti definicija kao 3 faktorjela.
Do 4 faktorijel jednak 3 do 4 puta faktora, i tako dalje i tako bliže našem
Uzorak drži do 1. faktora, koji po definiciji je jednak 1.
>> Nema drugog pozitivno cijeli brojevi napustio.
Dakle, imamo uzorak za naš rekurzivna poziva.
n je jednak faktorijel N puta faktorjela n minus 1.
I naš osnovni scenarij?
To će biti samo naša definicija od 1 faktorjela.
>> Dakle, sada možemo prijeći na pisanje broj za funkciju.
Za baznu slučaju, imat ćemo Uvjet je n = jednako 1, gdje je
vratit ćemo se jednom.
Tada kreće na rekurzivni poziv, vratit ćemo se n puta
faktorjela n minus 1.
>> Sada ćemo testirati ovaj naš.
Pokušajmo faktorijel 4.
Po našoj funkciji je jednaka do 4 puta faktorski (3).
Faktorijel (3) je jednak 3 puta faktorijel (2).
Faktorijel (2) je jednak 2 puta faktorijel (1), koji vraća 1.
Faktorijela (2) sada vraća 2 puta 1, 2.
Faktorijela (3) se sada može vratiti 3 puta 2, 6.
I na kraju, faktorjela (4) vraća 4 puta 6, 24.
>> Ako se pojave bilo kakvih poteškoća s rekurzivni poziv, pretvarati se da
funkcija radi već.
Što mislim to je da treba Vaše povjerenje rekurzivnih poziva da se vrate
prave vrijednosti.
Na primjer, ako znam da je faktorjela (5) iznosi 5 puta
faktorjela (4), ja ću vjerovati da je faktorjela (4) će mi dati 24.
Razmislite o tome kao varijable, ako će se, kao da je već definirana
faktorijel (4).
Dakle, za bilo faktorjela (n), to je Produkt n i
natrag faktorjela.
A to natrag faktorjela Dobije pozivom
faktorjela n minus 1.
>> Sada, vidjeti ako možete provesti rekurzivna funkcija sebe.
Natrpati svoj terminal, ili run.cs50.net, i napisati funkciju suma
koji traje cijeli broj N i vraća Zbroj svih uzastopna pozitivna
cijeli brojevi iz N u jedan.
Ja sam napisao out sume neke Vrijednosti će vam pomoći naš.
Prvo, shvatiti osnovni scenarij stanje.
Zatim, pogled na sumu (5).
Možete li ga izraziti u smislu drugog iznosa?
Sada, što je suma (4)?
Kako možete izraziti sumu (4) u odnosu na drugu sumu?
>> Nakon što su iznos (5) i zbroj (4) izražena u smislu drugih iznosa, vidjet
ako mogu identificirati Obrazac za sumu (n).
Ako ne, pokušajte još nekoliko brojeva i izraziti svoje sume u
Uvjeti još brojeva.
Identificiranjem obrasce za diskretne brojevi, da ste na dobrom putu da
identificiranje uzorak za bilo koji n.
>> Rekurzije je jako moćan alat, pa naravno, to nije ograničeno na
matematičkih funkcija.
Rekurzija se može koristiti vrlo učinkovito kada se bave s drveća za primjer.
Pogledajte kratki na stablima za temeljitiji pregled, ali za sada
podsjetiti da pretraživanje po binarnom stabala, u Osobito su sastavljene od čvorova, svaka
s vrijednošću i dva čvora naputke.
Obično, to je predstavljen roditelj čvor ima jednu liniju koja pokazuje
na lijevom čvor dijete i jedan na pravo čvor dijete.
Struktura binarnog pretraživanja Stablo se posuđuje i
na rekurzivni pretraživanje.
Rekurzivna poziva ili prolazi u lijevo ili desno čvor, ali više
od toga u stablo Short.
>> Recimo da želite obaviti operaciju svaki čvor u binarnom stablu.
Kako možete ići o tome?
Pa, što bi mogao napisati rekurzivna funkcija koja obavlja rad
na roditeljski čvor i čini rekurzivna pozvati na istu funkciju,
prolazi u lijevo i prava djece čvorova.
Na primjer, ova funkcija, Foo, da mijenja vrijednost danog čvora i
sve svoje djece na 1.
Baza slučaj null čvorova uzroka funkcija za povratak, što upućuje
da ne postoje nikakvi čvorovi ostavio u tom pod-stabla.
>> Idemo prošetati kroz nju.
Prvi roditelj 13.
Mi promijeniti vrijednost na 1, a zatim pozvati naša funkcija na lijevoj strani, kao i
kao pravu.
Funkcija, Foo, zove se na lijevoj strani pod-stablo prvo, pa lijevo čvor
će se rasporediti na 1. i Foo će se pozvao djecu da čvora,
Prvi lijevo, a zatim desno, i tako dalje i tako dalje.
I reci im da grane ne moraju bilo više djece pa isti proces
nastavit će se za pravo djece dok cijela stabla su čvorovi
rasporediti na jedan.
>> Kao što možete vidjeti, niste ograničeni na samo jedan rekurzivna poziva.
Upravo onoliko koliko će dobiti posao ispunjavanja.
Što ako je stablo u kojem svaki čvora je imao troje djece,
Lijevo, srednji, i zar ne?
Kako biste uredili Foo?
Pa, jednostavno.
Samo dodati još jedan rekurzivni poziv i prođe u srednji čvor pokazivača.
>> Rekurzije je vrlo moćan i da ne spomenuti elegantna, ali to može biti
Teško koncept u početku, pa se strpljivi i uzmite si vremena.
Počnite s osnovnom scenariju.
To je obično najlakše prepoznati, i onda možete raditi
unatrag od tamo.
Vi znate da je potrebno doći do svoje osnovni scenarij, tako da bi moglo
dati vam nekoliko savjeta.
Pokušajte izraziti jedan specifičan slučaj u Uvjeti drugim slučajevima, ili u pod-seta.
>> Hvala što gledate ovaj kratki.
U najmanju ruku, sada možete razumiju viceve kao što je ovaj.
Moje ime je Zamyla, a to je CS50.
>> Iskoristite ovu funkciju, hi, void funkcija koja traje
int n, kao ulaz.
Baza slučaj na prvom mjestu.
Ako je n manji od 0, print "Bye" i povratak.