>> ZAMYLA: Lai saprastu rekursijas, jums ir
vispirms ir jāsaprot rekursija.
Ņemot rekursijas programmā dizaina līdzekļiem ka jums ir self-godbijīgs
definīcijas.
Progresiju datu struktūras, piemēram, ir datu struktūras, kas
ietver sevi to definīcijas.
Bet šodien, mēs spēsim koncentrēties gada rekursīvs funkcijas.
>> Atgādināt, ka funkcijas veikt ieguldījumus, argumenti, un atgriež vērtību, kā to
produkciju pārstāv šī shēma šeit.
Mēs domājam par kastes, kā ķermeņa funkcija, kas satur kopu
instrukcijas, kas interpretē ievades un nodrošināt produkciju.
Ņemot tuvāk apskatīt ķermeņa iekšpusē funkcija varētu atklāt zvanus
citas funkcijas, kā arī.
Veikt šo vienkāršo funkciju, foo, ka aizņem vienu virkni kā ievade un
izdrukas, cik daudz burtus ka string ir.
Funkciju strlen, stīgu garumu, sauc, kuru produkcija
kas nepieciešama, lai zvanu uz printf.
>> Tagad, kas padara rekursīvā funkcija īpašs ir tas, ka tā sevi dēvē.
Mēs varam pārstāvēt šo rekursīvā zvanu ar šo oranža bultiņa
looping atpakaļ uz sevi.
Bet izpildot sevi atkal būs tikai veikt citu rekursīvas zvanu, un
vēl un vēl.
Bet rekursīvas funkcijas nevar būt bezgalīgs.
Viņiem ir beigt kaut kā, vai jūsu Programma darbosies uz visiem laikiem.
>> Tāpēc mums ir nepieciešams, lai atrastu veidu, kā lauzt ārā no rekursīvas zvanu.
Mēs to saucam par bāzes scenārijs.
Ja bāzes scenārijs nosacījums ir izpildīts, funkcija atgriež neveicot
cits rekursīvas zvanu.
Veikt šo funkciju, hi, tukšumu Function kas ņem int n kā priekšnodokli.
Bāzes scenārijs ir pirmajā vietā.
Ja n ir mazāks par nulli, print bye un atgriezties Visos citos gadījumos,
funkcija drukāt hi un izpildīt rekursīvas zvanu.
Vēl viens zvans uz funkciju hi ar decremented ievades vērtība.
>> Tagad, pat ja mēs drukāt hi, funkcija nebeidzas, kamēr mēs
atpakaļ atgriešanas veidu, šajā gadījumā spēkā neesošu.
Tā, lai katrs n izņemot bāzes gadījumā šī funkcija hi atgriezīsies hi
mīnus n 1.
Jo šī funkcija nav spēkā, lai gan, mēs nav skaidri ierakstīt šeit atgriezties.
Mēs vienkārši izpildīt funkciju.
Tāpēc zvanot hi (3) tiks izdrukātas hi un izpildīt hi (2), kas izpilda hi (1), viena
kas izpilda hi (0), kurā bāzes scenārijs nosacījums ir izpildīts.
Tāpēc hi (0) drukā bye un atdevi.
>> OK.
Tāpēc tagad, ka mēs saprotam pamatus rekursīvas funkcijas, kas tiem nepieciešams
vismaz vienu gadījumu, kā arī rekursīvs zvanu, pieņemsim pāriet uz
vairāk jēgpilnu piemērs.
Viens, kas ne tikai atgriezties neesošu vienalga ko.
>> Pieņemsim apskatīt faktoriāliem operācija izmanto visbiežāk
varbūtības aprēķini.
Faktorilāls no n ir produkts, katru pozitīvs vesels skaitlis mazāks par
un ir vienāds ar n.
Tāpēc faktoriāls pieci ir 5 reizes 4 reizes 3 reizes 2 reizes 1, lai sniegtu 120.
Četri faktoriāls ir 4 reizes 3 reizes 2 reizes 1, lai sniegtu 24.
Un tas pats noteikums attiecas jebkuram pozitīvam skaitlim.
>> Tātad, kā mēs varbūt uzrakstīt rekursīvs funkcija, kas aprēķina faktoriālu
no vairākiem?
Nu, mums būs nepieciešams, lai noteiktu gan gadījumu, un rekursīvas zvanu.
Rekursīvas zvans ir tāds pats visos gadījumos, izņemot pamatnes
gadījumā, kas nozīmē, ka mums būs atrast modeli, kas dos mums mūsu
vēlamais rezultāts.
>> Šim piemēram, redzēt, kā 5 faktoriāls ietver reizinot 4 3 ar 2 līdz 1
Un ka tas pats pavairošana ir atrodams šeit
definīcija 4 faktori.
Tātad mēs redzam, ka 5 faktoriāls ir tikai 5 reizes 4 faktori.
Tagad tas modelis piemērojams 4 Faktoriāls, kā arī?
Jā.
Mēs redzam, ka 4 faktoriāls satur reizināšanas 3 reizes 2 reizes 1,
Pašā definīcija 3 faktori.
Tātad 4 faktoriāls ir vienāds ar 4 reizes 3 faktoriālo, un tā tālāk, un tā tālāk mūsu
modelis pielīp līdz 1 faktoriāliem, kas pēc būtības ir vienāds ar 1.
>> Nav neviena cita pozitīva veseli skaitļi pa kreisi.
Tāpēc mums ir modeli Mūsu rekursīvas zvanu.
n faktoriāls ir vienāds ar n reizes faktoriāls n mīnus 1.
Un mūsu bāzes scenārijs?
Tas būs vienkārši mūsu definīcija 1 faktori.
>> Tāpēc tagad mēs varam virzīties uz rakstiski kods funkciju.
Attiecībā uz pamata lietas, mums būs nosacījums n vienāds vienāds ar 1, ja
mēs atgrieztos 1.
Tad pārvietojas uz rekursīvo zvanu, mēs atpakaļ n reizes
faktoriāls no n mīnus 1.
>> Tagad pieņemsim pārbaudīt šo mūsu.
Pamēģināsim faktoriālu 4.
Per mūsu funkcijas, tas ir vienāds līdz 4 reizes faktoriālā (3).
Faktorilāls (3) ir vienāda 3 reizes faktoriālās (2).
Faktorilāls (2), ir vienāda ar 2 reizes faktoriāls (1), kas atgriež 1.
Faktoriāls (2), kas tagad atgriežas 2 reizes 1, 2.
Faktoriāls (3), tagad var atgriezties 3 reizes 2, 6.
Un, visbeidzot, faktoriālā (4) atgriež 4 reizes 6, 24.
>> Ja radušās kādas grūtības ar rekursīvas zvanu, izlikties, ka
funkcija darbojas jau.
Ko es domāju ar šo ir tas, ka jums vajadzētu uzticēties jūsu rekursīvas zvanu, lai atgrieztos
pareizās vērtības.
Piemēram, ja es zinu, ka faktoriāls (5) ir vienāds ar 5 reizes
faktoriāls (4), es esmu gatavojas ticu, ka faktoriāls (4) dos man 24.
Domājiet par to kā mainīgo, ja jūs , tāpat kā tad, ja jūs jau ir definēts
faktoriāls (4).
Tātad jebkuram faktoriāliem (n), tas ir n produktu un
iepriekšējā faktori.
Un šī iepriekšējā faktoriāls iegūst zvanot
faktoriāls no n mīnus 1.
>> Tagad, redzēt, ja jūs varat īstenot rekursīvā funkcija sevi.
Ielādēt savu terminālu, vai run.cs50.net, un rakstīt funkciju summu
kas notiek veselu n un atgriež summa visiem pēc kārtas pozitīvs
veseli skaitļi no n līdz 1.
Es esmu rakstiski no summas dažu vērtībām, lai palīdzētu jums mūsu.
Pirmkārt, izdomāt bāzes scenārijs stāvoklī.
Tad, apskatīt summa (5).
Vai jūs varat izteikt to ziņā cita summa?
Tagad, ko par summu (4)?
Kā jūs varat izteikt summu (4) ziņā citā summa?
>> Kad jums ir summa, (5), un summa (4) izteikts citu summu, sk
ja jūs varat noteikt Paraugs summu (n).
Ja tā nav, mēģiniet daži citi skaitļi un izteikt savas summas
noteikumi citu numuru.
Nosakot modeļus diskrēti numuru, jūs labi pa ceļam uz
identificējot modeli jebkuru n.
>> Rekursija ir ļoti spēcīgs instruments, tāpēc, protams, tas neattiecas tikai uz
matemātiskās funkcijas.
Recursion var izmantot ļoti efektīvi , strādājot ar kokiem, piemēram.
Pārbaudiet īsi par koku rūpīgāka pārskatīšana, bet tagad
atgādināt, ka bināro meklēšanas koku, kas Konkrēti, ir izgatavoti no mezgliem, katrs
ar vērtību un diviem mezglu norādes.
Parasti tas pārstāv mātes mezglā ar vienu līniju kas norāda
uz kreiso bērnu mezglu un vienu uz labo bērnu mezglā.
Bināro meklēšanu struktūra koku pakļauj sevi labi
uz rekursīvo meklēšanu.
Rekursīvas zvanu, vai nu iet uz pa kreisi vai pa labi mezglā, bet vairāk
un ka koka īss.
>> Saka, jūs vēlaties, lai veiktu operāciju katru mezglu bināro koku.
Kā jūs varētu iet par to?
Nu, jūs varētu uzrakstīt rekursīvo funkcija, kas veic darbību
mātes mezglā un padara rekursīvo zvanu uz to pašu funkciju,
kas iet pa kreisi un Tiesības bērnu mezgliem.
Piemēram, šī funkcija, foo, ka maina konkrētā mezgla vērtību un
visiem saviem bērniem pret 1.
Bāze gadījums null mezglu cēloņiem darbība, lai atgrieztos, norādot
ka tajā nav mezgli kreisi šajā sub-tree.
>> Let 's staigāt pa to.
Pirmais no vecākiem ir 13.
Mēs mainīt vērtību 1, un tad zvana Mūsu uzdevums pa kreisi, kā arī
kā labi.
Funkcija, foo, sauc pa kreisi sub-tree, pirmkārt, tāpēc kreisā mezgls
tiks atkal 1 un foo būs izsaukt uz attiecīgās mezglā bērniem,
vispirms pa kreisi un tad pa labi, un tā tālāk, un tā tālāk.
Un pateikt viņiem, ka filiāles nav vairāk bērnu, lai pats process
turpināsies pareizos bērniem līdz brīdim, kad viss koks ir mezgli
nodot līdz 1.
>> Kā jūs varat redzēt, jums ir ne tikai tikai vienu rekursīvas zvans.
Tikpat daudz, cik saņems darba darīts.
Ko darīt, ja jums bija koku, kur katra mezgls bija trīs bērni,
Pa kreisi, vidū un pa labi?
Kā jūs rediģēt foo?
Nu, vienkārši.
Vienkārši pievienot citu rekursīvas zvanu un iet pa vidu mezglā rādītājs.
>> Rekursija ir ļoti spēcīgs, un nav min elegant, bet tas var būt
sarežģīts jēdziens sākumā, tāpēc pacientu un veikt savu laiku.
Sāciet ar pamata lietu.
Tas parasti ir visvieglāk noteikt, un tad jūs varat strādāt
atpakaļ no turienes.
Jūs zināt, jums ir nepieciešams, lai sasniegtu savu bāzes scenārijs, lai varenība
sniegt jums dažus padomus.
Mēģināt izteikt vienu konkrētu lietu noteikumi citos gadījumos, vai sub-kopas.
>> Paldies, skatoties šo īso.
Vismaz, tagad jūs varat saprast jokus, kā šis.
Mans vārds ir Zamyla, un tas ir CS50.
>> Veikt šo funkciju, hi, neesošu funkciju, kas notiek
int, n, kā ieejas.
Bāzes scenārijs ir pirmajā vietā.
Ja n ir mazāks par 0, print "Bye" un atgriešanās.