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.