>> ZAMYLA: Da bi razumeli rekurzija, morate
najprej razumeti rekurzijo.
Ob rekurzijo v program za načrtovanje sredstev da imate avtoreferenčni
opredelitve.
Rekurzivne podatkovne strukture, na primer, so podatkovne strukture, ki
se vključujejo v njihove definicije.
Toda danes se bomo osredotočili na rekurzivnih funkcij.
>> Spomnimo se, da funkcije, da vložkov, argumente, in vrne vrednost kot njihovi
izhod, ki ga zastopa Ta diagram tukaj.
Mi bomo pomislite na polja v telesu funkcijo, ki vsebuje niz
navodila, ki razlagajo vhod in izhodno.
Ob podrobnejši pogled v notranjost telesa funkcijo bi lahko razkrili klicev na
druge funkcije, kot tudi.
Vzemite to preprosto funkcijo, foo, da traja samo en niz, kot vhod in
natisne, koliko črk da ima niz.
Funkcija strlen, za dolžino niza, se imenuje, katerih proizvodnja je
potrebna za klic v printf.
>> Zdaj, kaj naredi rekurzivno funkcijo Posebno je, da je sama zahteva.
Lahko zastopajo to rekurzivno Klicanje s tem oranžna puščica
vračanjem na sebi.
Samo, ampak se je spet izvršitvena vzpostavite nov rekurzivni klic, in
drugo in drugo.
Ampak rekurzivne funkcije ne more biti neskončna.
Imajo na koncu nekako, ali vaš Program bo trajal večno.
>> Zato moramo najti način, da bi prekinil ven iz rekurzivnih klicev.
Osnovna pravimo tega.
Ko je izpolnjen pogoj osnovna izpolnjen, funkcija vrne, ne da bi
en rekurzivni klic.
Vzemite to funkcijo, hi, funkcijo void ki traja int n kot vhod.
Osnovna na prvem mestu.
Če je n manj kot nič, tiskanje in adijo vrnitev vseh drugih primerih,
Funkcija bo izpisal hi in izvršitev rekurzivni klic.
Še en klic funkcije hi s decremented vhodna vrednost.
>> Sedaj, čeprav smo natisniti hi, funkcija ne preneha, dokler ne bomo
vrnitev svoje vrste vračanja, v tem primeru praznini.
Torej za vsak n razen osnovnem scenariju ta funkcija hi hi bo vrnil
n minus 1.
Ker je ta funkcija ničen, čeprav smo ne bo vrnitve izrecno vpišite tukaj.
Mi bomo samo izvršitev funkcije.
Torej kliče hi (3), se natisne in hi izvršiti hi (2), ki izvaja hi (1) en
ki izvaja hi (0), kjer je Pogoj osnovna izpolnjen.
Torej, hi (0) natisne adijo in se vrne.
>> OK.
Torej sedaj, da smo razumeli osnove rekurzivne funkcije, ki jih potrebujejo
vsaj ene baze primera, kakor tudi rekurzivni klic, gremo na
bolj smiselno primer.
Tisti, ki ne samo vrnitev izničijo ni važno kaj.
>> Oglejmo si na fakulteto Delovanje uporabljajo najpogosteje v
izračuni verjetnosti.
Fakulteta n je produkt vsak pozitivno celo število manj kot
in enako n.
Torej faktorski pet je 5 krat 4 krat 3 krat 2-krat 1, da dobimo 120.
Štiri faktorski je 4 krat 3 krat 2-krat 1, da dobimo 24.
In velja enako pravilo za vsako pozitivno celo število.
>> Torej, kako bi lahko napišemo rekurzivno Funkcija, ki izračuna fakulteto
številnih?
No, bomo morali opredeliti tako osnovna in rekurzivni klic.
Rekurzivni klic, bo enaka v vseh primerih, razen za bazo
primera, kar pomeni, da bomo morali najti vzorec, ki nam bo dala našim
želeni rezultat.
>> Za ta primer, kako 5 faktorjev vključuje pomnoži 4 za 3 za 2 za 1
In to zelo isto razmnoževanje najdemo tod
definicija 4. fakulteto.
Tako vidimo, da je 5 faktorjev le 5 krat 4 fakulteto.
Zdaj se uporablja ta vzorec do 4 fakulteto, pa tudi?
Da.
Vidimo, da je 4. faktorjev vsebuje množenje 3 krat 2 krat 1,
Zelo enaka opredelitev kot 3 fakulteto.
Torej 4 faktorski je enako 4-krat 3 faktorski, in tako naprej in tako naprej naši
Vzorec palice do 1. fakulteto, ki po definiciji je enak 1.
>> Ni druge pozitivne cela levo.
Torej imamo vzorec za naš rekurzivni klic.
n faktorski je enako n krat fakulteta n minus 1.
In naša baza primer?
Da bom samo naša definicija 1. fakulteto.
>> Sedaj se lahko premaknemo na pisno koda za funkcijo.
Pri osnovnem scenariju, bomo morali pogoj n enak enak 1, kjer je
bomo vrnili 1.
Nato pa se gibljejo na rekurzivnega klica, bomo vrnili n-krat
fakulteta n minus 1.
>> Zdaj pa se preizkusite to naša.
Poskusimo fakulteto 4.
Na našem funkcijo je enaka do 4-krat faktorski (3).
Faktorski (3) je enak 3-krat faktorski (2).
Faktorski (2) je enak 2 krat faktorski (1), ki vrne 1.
Faktorski (2) sedaj vrne 2 krat 1, 2.
Faktorski (3), lahko sedaj vrnete 3 krat 2, 6.
In končno, faktorski (4) vrne 4-krat 6, 24.
>> Če ste naleteli na težave z rekurzivnega klica, se pretvarjamo, da
Funkcija deluje že.
Kaj mislim s tem je, da bi morala zaupajo svoje rekurzivne klice, da se vrnete
prave vrednote.
Na primer, če vem, da je faktorski (5) je enaka 5-krat
faktorski (4), bom zaupal, da faktorski (4), mi bo dal 24.
Think of it kot spremenljivko, če bo, kot če že opredeljena
faktorski (4).
Torej za vsako fakulteto (n), to je produkt n in
Predhodna fakulteto.
In ta prejšnja fakulteto dobimo tako, da zahteva
fakulteta n minus 1.
>> Zdaj pa poglej, če lahko izvajajo rekurzivna funkcija sami.
Vstavite vaš terminal, ali run.cs50.net, in napisati funkcijo SUM
ki traja celo število n in vrne Vsota vseh zaporedni pozitivni
cela števila od n do 1.
Napisal sem ven vsote nekaterih Vrednosti, ki vam pomaga naša.
Najprej ugotovimo, Pogoj osnovna.
Potem, poglej vsoto (5).
Lahko si ga izraziti druge vsote?
Zdaj, kaj pa vsota (4)?
Kako lahko izrazite vsoto (4) V smislu drugega vsote?
>> Ko imate vsoto (5) in vsota (4) izražene v drugih zneskov, glej
če se lahko opredelijo Vzorec za vsoto (n).
Če ni, poskusite nekaj drugih številk in izrazijo svoje zneske
Pogoji nadaljnjih številk.
S prepoznavanjem vzorcev za diskretnih številke, ste na dobri poti, da
identifikacijo vzorec za vsak n.
>> Rekurzija je zelo močno orodje, Tako seveda ni omejen samo na
matematične funkcije.
Rekurzija se lahko zelo učinkovito uporablja ko se ukvarjajo z drevesi, na primer.
Oglejte si kratko o drevesih bolj temeljit pregled, vendar za zdaj
opozarjajo, da binarnih iskalnih dreves, v Zlasti so sestavljeni iz vozlišč, vsak
z vrednostjo in dveh vozlišč kazalcev.
Ponavadi je to zastopa nadrejeno vozlišče, ki ima eno vrstico kazanje
na levo vozlišča in eno na desni vozlišča.
Strukturo binarnega iskanja Drevo je zelo primerna tudi
na rekurzivnega iskanja.
Rekurzivni klic, bodisi prehaja v levo ali desno vozlišče, ampak bolj
od tega v drevo kratkega stika.
>> Da želite izvesti operacijo na vsak vozlišče v binarnem drevesu.
Kako lahko greste o tem?
No, lahko napišete rekurzivno Funkcija, ki izvaja operacijo
na starša in naredi rekurzivno klic na isto funkcijo,
poteka v levo in pravica otrok vozlišča.
Na primer, ta funkcija, foo, da spremeni vrednost danega vozlišča in
vsi njeni otroci do 1.
Osnova primeru ničelnih vozlišču vzrokov Funkcija za vrnitev, kar pomeni,
da ni vsa vozlišča ostane v tem sub-tree.
>> Sprehodimo se skozi to.
Prvi staršev je 13.
Spremenimo vrednost na 1, nato pa pokličite Naša funkcija na levi kot tudi
kot je prav.
Funkcija, foo, se imenuje na levi sub-tree prvi, tako levi vozlišče
bo premeščen na 1. in foo bo se imenuje za otroke, ki vozlišča,
najprej levo in nato desno in tako naprej in tako naprej.
In jim povedal, da jim podružnice nimajo več otrok tako enak postopek
bo še za pravico otrok dokler so vozlišča celemu drevesa
prerazporedili 1.
>> Kot lahko vidite, niste omejeni samo en rekurzivni klic.
Ravno toliko, kot bo dobil delo opravljeno.
Kaj če bi imeli na drevo, kjer je vsak vozlišče imela tri otroke,
Levi, srednji in desni?
Kako bi vi uredite foo?
No, preprosto je.
Dodajte še en rekurzivni klic in prenese na kazalec srednji vozlišča.
>> Rekurzija je zelo močna in da ne portalu elegantno, vendar je lahko
zapleten pojem na prvi, zato bodite bolnika in si vzemite čas.
Začnite z osnovnim scenarijem.
To je običajno najlažje ugotoviti, in potem si lahko delo
nazaj od tam.
Saj veš, kar potrebujete, da bi dosegli svoj referenčnem primeru, tako da bi
vam nekaj namigov.
Poskusi, da izrazi en poseben primer v Pogoji ostalih primerih ali v pod-sklopov.
>> Hvala za gledanje ta kratko.
Vsaj, sedaj lahko razumejo šale, kot je ta.
Ime je Zamyla, in to je CS50.
>> Vzemite to funkcijo, hi, void funkcija, ki traja
int n, kot vhod.
Osnovna na prvem mestu.
Če je n manj kot 0, tiskanje "Adijo" in povratka.