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.