[Mūzikas atskaņošanai] 

Doug LLOYD: Jūs droši vien domājat, ka kods tiek izmantots tikai, lai izpildītu uzdevumu. Jūs rakstīt to ārā. Tas nav kaut kas. Tas ir diezgan daudz to. 

Jūs sastādīt to. Jūs palaist programmu. Jūs esat labi iet. 

Bet ticiet vai nē, ja jūs kods uz ilgu laiku, jūs tiešām varētu nākt, lai redzētu kodu, kā kaut ko, kas ir skaists. Tas atrisina problēmu ļoti interesants veids, vai tur ir tikai kaut kas patiešām veikls par to, kā tas izskatās. Jūs varētu smieties uz mani, bet tā ir taisnība. Un rekursijas ir viens no veidiem lai veida iegūt šo ideju no skaista, eleganta izskata kods. Tas atrisina problēmas, tādā veidā, ka ir interesanti, viegli iztēloties, un pārsteidzoši īss. 

The Way rekursijas darbi ir, rekursīvs funkcijas tiek definēta kā funkciju, kas aicina pati kā daļu no tās izpildes. Tas varētu likties mazliet dīvaini, un mēs redzēsim mazliet par to, kā tas darbojas brīdi. Bet atkal, tie rekursīvas procedūras būs tik elegants jo viņi dodas lai atrisinātu šo problēmu bez kam ir visas šīs citas funkcijas vai šie ilgi cilpas. Jūs redzēsiet, ka šie rekursīvas procedūras ir gatavojas izskatās tik īss. Un viņi tiešām gatavojas darīt Jūsu kods izskatīsies daudz skaistāku. 

Es došu jums piemēru Tas lai redzētu, kā rekursīvs procedūra var definēt. Tātad, ja jūs esat iepazinušies ar šo no matemātikas klasē pirms daudziem gadiem, tur ir kaut kas sauc factorial funkcija, kas parasti ir apzīmēts kā izsaukuma zīmi, kas definē pār visiem pozitīviem veseliem skaitļiem. Un tā, ka n factorial aprēķina tiek jūs reizināt visu skaitļi mazāk nekā vai vienāds ar n together-- visi veseli skaitļi mazāk nekā vai vienāds ar n kopā. 

Tātad 5 factorial ir 5 reizes 4 reizes 3 reizes 2 reizes 1. Un 4 factorial ir 4 reizes 3 reizes 2 reizes 1 un tā tālāk. Jūs saņemsiet ideja. 

Kā programmētāji, mums nav izmantot N, izsaukuma zīmi. Tātad mēs definēt faktoriālu funkcija kā faktu n. Un mēs izmantosim faktoriālu, lai izveidotu rekursīvs risinājums problēmai. Un es domāju, ka jūs varētu atrast ka tas ir daudz vairāk vizuāli pievilcīgs nekā iteratīvs versija par šo, kas mēs arī to apskatīt brīdi. 

Tātad, šeit ir pāris facts-- pun intended-- par factorial-- faktoriāls funkcija. No 1. factorial, kā jau teicu, ir 1. No 2. factorial ir 2 reizes 1. No 3. factorial ir 3 reizes 2 reizes 1, un tā tālāk. Mēs runājām par 4. un 5. jau. 

Bet skatoties uz to, nav taisnība? Vai nav faktoriālu 2 vienkārši 2 reizes faktoriālu 1? Es domāju, faktoriālu 1 ir 1. Tātad, kāpēc mēs nevaram vienkārši teikt, ka, kopš faktoriālu no 2 ir 2 reizes 1, tas patiešām ir tikai 2 reizes faktoriālu 1? 

Un tad paplašinot šo ideju, nav faktoriālu 3 tikai 3 reizes faktoriālu 2? Un faktoriālu 4 ir 4 reizes faktoriālu 3, un tā tālāk? Faktiski, faktoriālu Jebkuras skaits var vienkārši izsaka ja mēs laipns no veikt šo out uz visiem laikiem. Mēs varam veida vispārināt faktoriālu problēma kā tas ir n reizes factorial n mīnus 1. Tas ir n reizes produkts visi skaitļi mazāk nekā man. 

Šī ideja, šis vispārināšana problēmas, ļauj rekursīvi definēt Faktoru funkciju. Kad jūs definētu funkciju rekursīvi, tur ir divas lietas, kas ir nepieciešams, lai būtu daļa no tā. Jums ir nepieciešams, lai būtu kaut ko sauc bāze gadījums, kas, kad jūs izraisīt to, pārtrauks rekursīvas procesu. 

Pretējā gadījumā funkcija, kas prasa itself-- kā jūs varētu imagine-- varētu iet uz visiem laikiem. Funkcija izsauc funkciju aicina Funkcija zvanus funkcija izsauc funkciju. Ja jums nav veids lai to apturētu, savu programmu faktiski būs iestrēdzis pie bezgalīgu cilpu. Tas būs crash galā, jo tas būs beigušies atmiņas. Bet tas ir blakus punktu. 

Mums ir nepieciešams, lai ir kāda cita veids, kā apturēt lietas, turklāt mūsu programmas crashing, jo programma, kas avārijām ir iespējams, nav skaisti vai elegants. Un tā mēs dēvējam bāzes gadījums. Tas ir vienkāršs risinājums uz problēmu, kas aptur rekursīvas process rašanos. Tā ka ir viena daļa no rekursīvs funkciju. 

Otrā daļa ir rekursīvs gadījums. Un tas ir, ja rekursijas tiešām notiks. Tas ir, ja funkcija aicinās sevi. 

Tas nebūs zvanīt sevi tieši tāpat to sauca. Tas būs neliela variācija kas padara šo problēmu tas ir mēģinot atrisināt maziņš mazliet mazāka. Bet tas parasti iet buks atrisināt lielāko daļu no risinājuma uz citu zvanu nosaka līniju. 

Kurš no šiem izskatās tāpat bāzes gadījums? Kura no šīm izskatās Vienkāršākais risinājums problēmai? Mums ir ķekars faktoriālu, un mēs varētu turpināt iet on-- 6, 7, 8, 9, 10, un tā tālāk. 

Bet viens no šiem izskatās laba lieta būt bāzes gadījums. Tas ir ļoti vienkāršs risinājums. Mums nav kaut kas īpašs jādara. 

No 1 factorial ir tikai 1. Mums nav jādara kādu pavairošana vispār. Šķiet, tāpat kā tad, ja mēs ejam lai mēģinātu atrisināt šo problēmu, un mums ir nepieciešams, lai apturētu rekursijas kaut kur, mēs, iespējams, vēlas, lai apturētu tā, kad mēs nokļūt līdz 1. Mēs nevēlamies apstāties pirms tam. 

Tātad, ja mēs esam definējot Mūsu factorial funkcija, šeit ir karkass kā mēs varētu darīt. Mums ir nepieciešams, lai kontaktdakšu šiem diviem things-- bāzes modeli, un rekursīvas lieta. Kas ir bāzes lieta? Ja n ir vienāds ar 1, atgriezties 1-- tas ir ļoti vienkāršs problēmu atrisināt. 

No 1 faktoriāls ir 1. Tas nav 1 reizes neko. Tas ir tikai 1. Tas ir ļoti vienkārši fakts. Un tā, kas var būt mūsu bāze gadījums. Ja mēs pagājis 1 par šo funkcija, mēs vienkārši atgriezties 1. 

Kas ir rekursīvas gadījums, iespējams, izskatās? Par katru citu numuru Bez tam 1., kāda ir modelis? Nu, ja mēs esam ņemot faktoriālu n, ir pienācis n reizes faktoriālu n mīnus 1. 

Ja mēs esam ņemot faktoriālu 3, tas ir 3 reizes faktoriālu 3 mīnus 1, vai 2. Un tāpēc, ja mēs neesam apskatot 1, pretējā gadījumā atgriešanās n reizes factorial n mīnus 1. Tas ir diezgan vienkārši. 

Un labad kam nedaudz tīrāku un vairāk elegants kods, zina, ka, ja mums ir viena līnija cilpas vai single-line nosacītie filiāles, mēs varam atbrīvoties no visa cirtaini bikšturi ap tiem. Tātad, mēs varam nostiprināt šo to. Tas ir tieši tāds pats funkcionalitāti, kā šis. 

Es esmu tikai atņemot cirtaini breketes, jo tur ir tikai viena līnija iekšpusē šiem nosacītas filiālēm. Tātad šie izturēties vienādi. Ja n ir vienāds ar 1, atgriezties 1. Pretējā atgriezties n reizes faktoriālu n mīnus 1. Tātad mēs nesam mazāku problēmu. Ja n uzsāk veikt kā 5, mēs ejam, lai atgriezt 5 reizes faktoriālu 4. Un mēs redzēsim pēc brīža, kad mēs runājam par zvanu stack-- citā video ja mēs runājam par zvaniet stack-- mēs mācīties par to, kāpēc tieši šis process darbojas. 

Bet, kamēr factorial 5 saka atgriezties 5 reizes factorial no 4, un 4 gatavojas teikt, OK, labi, atgriešanās 4 reizes faktoriālu 3. Un, kā jūs varat redzēt, mēs esam kārtot tuvojas 1. Mēs esam nonākuši tuvāk un tuvāk šo gadījumu. 

Un, kad mēs hit bāzes lietu, visu iepriekšējo funkciju ir atbilde viņi meklē. Faktoriāls 2. teica atgriešanos 2 reizes faktoriālu 1. Nu, faktoriālu no 1 atdevi 1. Tātad aicinājums faktoriālo 2. var atgriezt 2 reizes 1, un dod, ka atpakaļ uz faktoriālu 3, kas gaida šo rezultātu. 

Un tad to var aprēķināt tās rezultāts, 3 reizes 2 ir 6, un dot to atpakaļ uz faktoriālu 4. Un atkal, mums ir video par zvanu kaudze ja tas ir ilustrēts nedaudz vairāk nekā tas, ko es saku tagad. Bet tas ir tā. Tas vien ir risinājums Aprēķinot skaitļa faktoriālu. 

Tas ir tikai četras rindiņas kodu. Tas ir diezgan cool, vai ne? Tas ir sava veida sexy. 

Tā vispār, bet ne vienmēr, rekursīvs funkcijas var aizstāt cilpu kādā non-rekursīvas funkcijas. Tātad šeit, blakus, ir iteratīvs versija faktoriālo funkciju. Abas šīs Aprēķināt tieši tas pats. 

Viņi abi aprēķināt faktoriālu n. Version pa kreisi izmanto Rekursija, lai to izdarītu. Version labajā pusē izmanto atkārtojuma, lai to izdarītu. 

Un paziņojums, mums ir jādeklarē mainīgs vesels skaitlis produkts. Un tad mēs cilpa. Tik ilgi, kamēr n ir lielāks par 0, mēs glabāt reizinot šo produktu ar n un decrementing N līdz mēs aprēķināt produktu. Tātad šīs divas funkcijas, atkal, darīt tieši to pašu. Bet tie nav darīt to tieši tāpat. 

Tagad, tas ir iespējams, lai ir vairāk nekā vienas bāzes gadījums vai vairāk nekā viens rekursīvs gadījumā, atkarībā par ko jūsu funkcija mēģina darīt. Jūs ne vienmēr ir tikai tikai uz vienu gadījumu, vai viena rekursīva lieta. Tātad piemērs kaut ar vairākām bāzes gadījumos varētu būt this-- Fibonači skaitļi secība. 

Jūs varbūt atceraties no pamatskolas dienas ka Fibonači secība ir definēts tāpat this-- pirmais elements ir 0. Otrais elements ir 1. Abi no tiem ir vienkārši pēc definīcijas. 

Tad katru otro elements ir definēts kā n mīnus 1 un n mīnus 2 summu. Tātad trešā elementa Būtu 0 plus 1 ir 1. Un tad ceturtais elements būtu otrais elements, 1, plus trešais elements, 1. Un tas būtu 2. Un tā tālāk, un tā tālāk. 

Tātad šajā gadījumā, mums ir divas bāzes lietas. Ja n ir vienāds ar 1, atgriezties 0. Ja n ir vienāds ar 2, atgriezties 1. Pretējā gadījumā atgriešanās Fibonacci n mīnus 1 plus Fibonači n mīnus 2. 

Tā ka ir vairākas bāzes gadījumus. Kas par vairākiem rekursīvs gadījumos? Nu, tur ir kaut kas sauc Collatz minējums. Es neesmu gatavojas teikt, jūs zināt, kas tas ir, jo tas ir tiešām mūsu gala problēma šo konkrēto video. Un tas ir mūsu uzdevums strādāt kopā. 

Tātad, šeit ir tas, ko Collatz minējums is-- tas attiecas uz katram pozitīvam skaitlim. Un tā lēš, ka tas ir vienmēr ir iespējams saņemt atpakaļ ar 1, ja jūs izpildiet šīs darbības. Ja n ir 1, apturēt. Mēs esam ieguvuši atpakaļ uz 1, ja n ir 1. 

Pretējā gadījumā, iet caur šo process atkal n dalot ar 2. Un redzēt, ja jūs varat saņemt atpakaļ 1. Pretējā gadījumā, ja n ir nepāra, iet cauri šis process atkal 3N plus 1, vai 3 reizes n plus 1. Tātad šeit mums ir vienota bāze lietu. Ja n ir vienāds ar 1, apturēt. Mēs nedarām nevienu vairāk Rekursija. 

Bet mums ir divas rekursīvs gadījumi. Ja n ir pat, mēs darīt vienu rekursīvas gadījumā, aicinot n dalot ar 2. Ja n ir nepāra, mēs cits rekursīvo gadījums 3 reizes n plus 1. 

Un tā mērķis šai video ir ņemt otro, apturētu video, un mēģināt rakstīt šo rekursīvas funkcijas Collatz kur jums iet ar vērtību n, un tā aprēķina, cik daudz pasākumiem, ko tā nepieciešams, lai nokļūtu līdz 1, ja jūs sākat no n un jūs izpildiet šos soļus augšas. Ja n ir 1, tas aizņem 0 soļus. Pretējā gadījumā, tas notiek, lai veikt vienu soli plus tomēr daudzi soļi tā veic vai nu n dalīts ar 2, ja n ir pat, vai 3n plus 1 ja n ir nepāra. 

Tagad, es esmu likts uz ekrāna šeit pāris testa lietas jums, pāris testos gadījumu jums, lai redzētu ko šie dažādie Collatz skaitļi ir, un arī ilustrācija par pasākumiem, kas nepieciešams gājusi cauri, lai jūs varētu kārtot redzēt šo procesu darbībā. Tātad, ja n ir vienāds ar 1, Collatz no n ir 0. Jums nav jādara kaut kas, lai saņemtu atpakaļ uz 1. Tu esi jau tur. 

Ja n ir 2, tas aizņem viens solis, lai nokļūtu līdz 1. Tu sāc ar 2. Nu, 2 nav vienāds ar 1. Tātad tas būs viens solis plus tomēr daudzi pasākumiem, ko tā uzņemas n dalot ar 2. 

2 dalīts ar 2 ir 1. Tātad tas aizņem vienu soli plus tomēr daudzi soļi, kas nepieciešams, lai 1. 1. ņem nulle soļus. 

3, kā jūs varat redzēt, tur ir iesaistīts diezgan dažus soļus. Jums iet no 3. Un tad doties uz 10, 5, 16, 8, 4, 2, 1. Tas aizņem septiņus soļus, lai saņemtu atpakaļ uz 1. Un, kā jūs varat redzēt, tur ir pāris citas pārbaudes gadījumos šeit izmēģināt savu programmu. Tātad vēlreiz, apturētu video. Un es iešu lēkt atpakaļ tagad ko faktiskais process ir šeit, ko šis minējums ir. 

Skat, ja jūs varat izdomāt Kā noteikt Collatz n lai tā aprēķina, cik daudz soļi, kas nepieciešams, lai nokļūtu līdz 1. Tik cerams, jums ir apturēta video un jums ir ne tikai gaida mani sniegt jums atbildi šeit. Bet, ja jums ir, labi, Lūk atbilde vienalga. 

Tātad, šeit ir iespējams definīcija no Collatz funkciju. Mūsu bāze case-- ja n ir vienāds ar 1, mēs atgrieztos 0. Tas neņem jebkurš soļi, lai saņemtu atpakaļ uz 1. 

Pretējā gadījumā mums ir divas rekursīvas cases-- viena pāra numuri un viens nepāra. Kā es tests pāra numuru ir pārbaudīt, vai n mod 2 ir vienāds ar 0. Tas ir galvenokārt, atkal, uzdodot jautājumu, Ja jūs atceraties, ko mod is-- ja es dalīt n ar 2 tur nav atlikums? Tas būtu pāra skaitlis. 

Un tāpēc, ja n mod 2 ir vienāds ar 0 ir testēšana ir šī pāra skaits. Ja tā, es vēlos atgriezties 1, jo tas noteikti ņemot vienu soli plus Collatz par kāds numurs ir puse no manis. Citādi, es vēlos atgriezties 1 plus Collatz par 3 reizes n plus 1. Ka bija otra rekursīvo solis, ka mēs varētu veikt, lai aprēķinātu Collatz-- vairākus pasākumus tas nepieciešams, lai saņemtu atpakaļ 1 piešķir numuru. Tātad, cerams, šis piemērs tev mazliet par garšu rekursīvs procedūru. Cerams, ka jūs domājat, ka kods ir nedaudz vairāk skaisti, ja īstenos elegantā, rekursīvas veidā. Bet pat tad, ja tā nav, rekursijas ir tiešām spēcīgs instruments tomēr. Un tā tas noteikti ir kaut lai saņemtu savu galvu apkārt, jo jūs varēsiet radīt pretty cool programmas, izmantojot Rekursija kas citādi varētu būt sarežģīti uzrakstīt ja jūs izmantojat cilpas un atkārtojuma. Es esmu Doug Lloyd. Tas ir CS50.