>> [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.