[SKAN MŪZIKA]
DAGS LOIDS: Jūs droši vien domājat, ka kods tiek izmantots tikai
uzdevuma veikšanai.
Jūs to izrakstāt.
Tas kaut ko dara.
Tas ir gandrīz viss.
Jūs to kompilējat.
Jūs palaižat programmu.
Jūs esat gatavi.
Bet ticiet vai ne, ja kodējat ilgu laiku, jūs praktiski varētu
uztvert kodu kā kaut ko skaistu.
Tas atrisina problēmu ļoti interesantā veidā, vai arī tās izskatā ir
kaut kas patiešām glīts.
Jūs varat smieties par mani, bet tā ir taisnība.
Un rekursija ir viens no veidiem, kā saprast ideju par skaistu,
elegantu kodu.
Tā atrisina problēmas interesantā, viegli vizualizējamā un
pārsteidzoši īsā veidā.
Rekursijas darbības veids ir tāds, ka rekursīvā funkcija tiek
definēta kā funkcija, kas sevi izsauc kā daļu no tās izpildes.
Tas varētu šķist nedaudz dīvaini, bet pēc brīža mēs redzēsim, kā tas
darbojas.
Bet atkal šīs rekursīvās procedūras būs tik elegantas, jo tās
atrisinās šo problēmu, neizmantojot pārējās funkcijas vai šīs garas
cilpas.
Jūs redzēsiet, ka šīs rekursīvās procedūras izskatīsies tik īsas.
Un tās patiešām padarīs jūsu kodu daudz skaistāku.
Es parādīšu jums piemēru, lai redzētu, kā var definēt rekursīvo
procedūru.
Tātad, no matemātikas stundām pirms daudziem gadiem jūs zināt, ka ir
kaut kas tāds, ko sauc par faktoriālu funkciju, ko parasti apzīmē kā
izsaukuma zīmi, kas ir attiecināma uz visiem pozitīvajiem veseliem
skaitļiem.
Un veids, kā tiek aprēķināts n faktoriāls, ir reizināt kopā visus
skaitļus, kas ir mazāki vai vienādi ar n, — visus veselos skaitļus,
kas ir mazāki vai vienādi ar n.
Tātad skaitļa 5 faktoriāls ir 5 reiz 4 reiz 3 reiz 2 reiz 1.
Un skaitļa 4 faktoriāls ir 4 reiz 3 reize2 reiz 1, un tā tālāk.
Jūs saprotat domu.
Kā programmētāji mēs neizmantojam n un izsaukuma zīmi.
Tātad faktoriāla funkciju definēsim kā n faktu.
Un mēs izmantosim faktoriālu, lai izveidotu problēmas rekursīvu
risinājumu.
Un es domāju, ka jūs piekritīsiet, ka tas ir daudz vizuāli
pievilcīgāks nekā tā iteratīvā versija, kuru mēs arī pēc brīža
apskatīsim.
Tātad, šeit ir daži fakti — runa ir par faktoriālu — faktoriālu
funkciju.
Skaitļa 1 faktoriāls, kā jau teicu, ir 1.
Skaitļa 2 faktoriāls ir 2 reiz 1.
Skaitļa 3 faktoriāls ir 3 reiz 2 reiz 1, utt.
Mēs jau runājām par 4 un 5.
Bet paskatoties uz šo, vai tā nav taisnība?
Vai skaitļa 2 faktoriāls 2 nav tikai 2 reiz 1?
Tas ir, skaitļa 1 faktoriāls ir 1.
Tātad, kāpēc mēs nevaram tā vienkārši pateikt, jo 2 faktoriāls ir 2
reiz 1, tas tiešām ir tikai 2 reizes vairāk nekā 1?
Un tad, paplašinot šo ideju, vai 3 faktoriāls nav tikai 3 reizes
lielāks nekā skaitļa 2 faktoriāls?
Un skaitļa 4 faktoriāls ir 4 reizes lielāks par faktoriālu no 3 un tā
tālāk?
Faktiski jebkura skaitļa faktoriālu var vienkārši izteikt, ja mēs to
izpildām tā mūžīgi.
Mēs varam vispārināt faktoriālu problēmu, jo tā ir n reizes lielāka
par n faktoriālu mīnus 1.
Tas ir visu skaitļu, kas ir mazāki par mani, reizinājums n reizes.
Šī ideja, šis problēmas vispārinājums, ļauj mums rekursīvi definēt
faktoriālu funkciju.
Ja funkciju definējat rekursīvi, tai ir jābūt divām lietām.
Jums ir nepieciešams kaut kas, ko sauc par bāzes bloku, kas,
aktivizējoties, aptur rekursīvo procesu.
Pretējā gadījumā funkcija, kas izsauc sevi — kā jūs varētu iedomāties
— varētu turpināties mūžīgi.
Funkcija izsauc funkciju, izsauc funkciju, izsauc funkciju, izsauc
funkciju.
Ja jums nav iespējas to apturēt, jūsu programma faktiski būs
iestrēgusi bezgalīgā cilpā.
Tā galu galā avarēs, jo tai pietrūks atmiņas.
Bet ne par to ir runa.
Mums ir nepieciešams kāds cits veids, kā apturēt programmu bez
avārijas, jo programma, kas avarē, visticamāk nav skaista un
eleganta.
Un tāpēc mēs to saucam par bāzes bloku.
Šis ir vienkāršs problēmas risinājums, kas aptur rekursīvo procesu.
Tātad tā ir viena no rekursīvās funkcijas daļām.
Otrā daļa ir rekursīvais bloks.
Un šeit faktiski notiks rekursija.
Šeit funkcija izsauks sevi.
Tā nesauks sevi tieši tādā pašā veidā, kā to sauca.
Te būs neliela variācija, kas padara problēmu, ko tā mēģina
atrisināt, nedaudz mazāku.
Taču risinājuma atbildības lielākā daļa parasti tiek pārnesta uz
nākamo zvanu.
Kurš no šiem šeit izskatās kā bāzes bloks?
Kurš no šiem šķiet vienkāršākais problēmas risinājums?
Mums ir daudz faktoriālu, un mēs varētu turpināt — 6, 7, 8, 9, 10 utt.
Bet viens no tiem izskatās kā labs gadījums, lai to izmantotu kā
bāzes bloku.
Tas ir ļoti vienkāršs risinājums.
Mums nav jādara nekas īpašs.
Skaitļa 1 faktoriāls ir tikai 1.
Mums vispār nav jādara nekāda reizināšana.
Šķiet, ja mēs mēģināsim atrisināt šo problēmu un mums kaut kur ir
jāpārtrauc rekursija, mēs, iespējams, vēlēsimies to apturēt pie 1.
Mēs nevēlamies apstāties pirms tam.
Tātad, ja mēs definējam savu faktoriālu funkciju, tad šeit ir
skelets, kā mēs to varētu izdarīt.
Mums ir jāpievieno šīs divas lietas — bāzes bloku un rekursīvo bloku.
Kas ir bāzes bloks?
Ja n ir vienāds ar 1, atgrieziet 1 — tā ir patiešām vienkārša
problēma, ko risināt.
Skaitļa 1 faktoriāls ir 1.
Tas nav 1 reiz jebkas.
Tas ir tikai 1.
Tas ir ļoti vienkāršs fakts.
Un tas varētu būt mūsu bāzes bloks.
Ja šai funkcijai nodosim 1, tad mēs atgriezīsim tikai 1.
Kā tad izskatās rekursīvais bloks?
Kāda ir shēma citiem skaitļiem, izņemot skaitli 1?
Ja mēs ņemam n faktoriālu, tas ir n reiz n mīnus 1 faktoriāls.
Ja mēs izmantojam skaitļa 3 faktoriālu, tas ir 3 reiz 3 mīnus 1
faktoriāls. Tātad, ja mēs neskatāmies uz 1, tad atgriežam n reiz n
mīnus 1 faktoriāls.
Tas ir diezgan vienkārši.
Un, lai kods būtu nedaudz tīrāks un elegantāks, ziniet, ka, ja mums
ir vienas rindiņas cilpas vai vienas rindas nosacītais zarojums, mēs
varam atbrīvoties no visām figūriekavām tiem apkārt.
Tātad mēs varam to apvienot ar šo.
Tam ir tieši tāda pati funkcionalitāte kā šim.
Es tikai noņemu figūriekavas, jo šajos nosacītajos zarojumos ir tikai
viena līnija.
Tātad šie uzvedas identiski.
Ja n ir vienāds ar 1, atgriež 1.
Pretējā gadījumā atgriež n reiz n mīnus 1 faktoriāls.
Tā mēs padarām problēmu mazāku.
Ja n sākas ar 5, mēs atgriezīsim skaitļa 4 faktoriāls reiz 5.
Un pēc minūtes mēs redzēsim, kad runāsim par zvanu steku — citā
videoklipā, kurā mēs runājam par zvanu steku - mēs uzzināsim, kāpēc
tieši šis process darbojas.
Bet, lai gan skaitļā 5 faktoriāls saka, ka tiek atgriezts 5 reiz
skaitļa 4 faktoriāls, un 4 teiks — labi, labi, atgriež skaitļa 3
faktoriāls reiz 4.
Un, kā redzat, mēs tuvojamies 1.
Mēs esam arvien tuvāk un tuvāk šim bāzes blokam.
Kad esam nokļuvuši pie bāzes bloka, visām iepriekšējām funkcijām
parādās atbilde, ko tās meklēja.
Skaitļa 2 faktoriāls teica atgriezt 2 reiz skaitļa 1 faktoriāls.
Skaitļa 1 faktoriāls atgriež 1.
Tātad skaitļa 2 faktoriāla izsaukums var atgriezt 2 reiz 1 un atdot
to skaitļa 3 faktoriālam, kas gaida šo rezultātu.
Un tad tas var aprēķināt rezultātu, 3 reiz 2 ir 6, un atdot to
skaitļa 4 faktoriālam.
Un atkal, mums ir video par zvanu steku, kur tas ir ilustrēts nedaudz
vairāk nekā es stāstu šobrīd.
Bet tas ir viss.
Tas vien ir risinājums skaitļa faktoriāla aprēķināšanai.
Tās ir tikai četras koda rindiņas.
Tas ir diezgan forši, vai ne?
Tas ir seksīgi.
Tātad kopumā, bet ne vienmēr, rekursīvā funkcija var aizstāt cilpu
nerekursīvajā funkcijā.
Tātad šeit blakus ir faktoriāla funkcijas iteratīvā versija.
Tie abi aprēķina tieši to pašu.
Tie abi aprēķina n faktoriālu.
Kreisajā pusē esošā versija izmanto rekursiju, lai to izdarītu.
Labajā pusē esošā versija izmanto iterāciju, lai to izdarītu.
Un ievērojiet, mums ir jādeklarē mainīgais kā vesela skaitļa
reizinājums.
Un tad mums ir cilpa.
Kamēr n ir lielāks par 0, mēs turpinām reizināt ar n un samazinām n,
līdz mēs aprēķinām reizinājumu.
Tātad šīs divas funkcijas atkal veic tieši to pašu.
Bet tās nedara to vienādā veidā.
Tagad ir iespējams izmantot vairāk nekā vienu bāzes bloku, vai vairāk
nekā vienu rekursīvo bloku, atkarībā no tā, ko jūsu funkcija mēģina
darīt.
Jums ne vienmēr ir tikai viens bāzes bloks vai viens rekursīvais
bloks.
Tātad piemērs tam, kam ir vairāki bāzes bloki, varētu būt šis —
Fibonači skaitļu virkne.
Jūs atceraties no pamatskolas laikiem, ka Fibonači virkne ir definēta
šādi — pirmais elements ir 0.
Otrais elements ir 1.
Abi šie ir tikai pēc definīcijas.
Tad katrs nākamais elements tiek definēts kā n mīnus 1 un n mīnus 2
summa.
Tātad trešais elements būtu 0 plus 1 ir 1.
Un tad ceturtais elements būtu otrais elements 1 un 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 divi bāzes bloki.
Ja n ir vienāds ar 1, atgriež 0.
Ja n ir vienāds ar 2, atgriež 1.
Pretējā gadījumā atgriež Fibonači no n mīnus 1, plus Fibonači no n
mīnus 2.
Tātad tie ir vairāki bāzes bloki.
Kā ar vairākiem rekursīvajiem blokiem?
Nu, ir kaut kas, ko sauc par Kolata minējumu.
Es neteikšu, ka jūs zināt, kas tas ir, jo īstenībā tas ir mūsu
pēdējais uzdevums šajā konkrētajā videoklipā.
Un tas ir mūsu uzdevums, pie kā strādāsim kopā.
Tātad, lūk, kas ir Kolata minējums — tas attiecas uz jebkuru pozitīvu
veselu skaitli.
Un tas liek domāt, ka vienmēr ir iespējams atgriezties pie 1, ja
veicat šīs darbības.
Ja n ir 1, apstājieties.
Mēs esam atgriezušies pie 1, ja n ir 1.
Pretējā gadījumā atkārtojiet šo procesu, kad n dalīts ar 2.
Un pārbaudiet, vai varat atgriezties pie 1.
Pretējā gadījumā, ja n ir nepāra skaitlis, atkārtojiet šo procesu
vēlreiz ar 3n plus 1 vai 3 reiz n plus 1.
Tātad šeit mums ir viens bāzes bloks.
Ja n ir vienāds ar 1, apstājieties.
Mēs vairs neveicam rekursiju.
Bet mums ir divi rekursīvie bloki.
Ja n ir pāra skaitlis, mēs veicam vienu rekursīvo bloku, izsaucot n
dalītu ar 2.
Ja n ir nepāra skaitlis, mēs veicam citu rekursīvo bloku 3 reiz n
plus 1.
Un tāpēc šī videoklipa mērķis ir nesteigties, nopauzēt video un
mēģināt uzrakstīt šo Kolata rekursīvo funkciju, kur jūs ievadāt
vērtību n, un tā aprēķina, cik soļu nepieciešams, lai nokļūtu līdz 1,
ja sākat no n un veicat iepriekš norādītās darbības.
Ja n ir 1, tas aizņem 0 soļus.
Pretējā gadījumā tas prasīs vienu soli plus daudz soļu, vai nu n
dalīts ar 2, ja n ir pāra skaitlis, vai 3n plus 1, ja n ir nepāra
skaitlis.
Tagad šeit uz ekrāna rādīšu dažus piemērus , dažus testa gadījumus,
lai redzētu, kas ir šie dažādie Kolata skaitļi, kā arī ilustrāciju
darbībām, kas jāveic, lai jūs varat redzēt šo procesu darbībā.
Tātad, ja n ir vienāds ar 1, Kolata skaitlis n ir 0.
Jums nekas nav jādara, lai atgrieztos pie 1.
Jūs jau tur esat.
Ja n ir 2, ir nepieciešams viens solis, lai nokļūtu līdz 1.
Jūs sākat ar 2.
Nu, 2 nav vienāds ar 1.
Tātad tas būs viens solis plus neatkarīgi no tā, cik daudz soļu tas
veic, n dalīts ar 2.
2 dalīts ar 2 ir 1.
Tātad tas aizņem vienu soli plus neatkarīgi no tā, cik daudz soļu tas
prasa līdz 1.
1 veic nulli soļus.
Attiecībā uz 3, kā redzat, ir jāveic vairākas darbības.
Jūs ejat no 3.
Un tad jūs dodaties uz 10, 5, 16, 8, 4, 2, 1.
Lai atgrieztos pie 1, ir jāveic septiņi soļi.
Un, kā redzat, šeit ir daži citi testa gadījumi, lai pārbaudītu savu
programmu.
Tāpēc vēlreiz apturiet video.
Un es tagad atgriezīšos pie faktiskā procesa, kas ir šis minējums.
Skatieties, vai varat saprast, kā definēt n Kolata skaitli, lai tas
aprēķinātu, cik soļu nepieciešams, lai nokļūtu līdz 1.
Tāpēc cerams, ka esat apturējuši video un negaidāt, kad es jums
sniegšu atbildi.
Bet, ja jūs gaidāt, tad šeit ir atbilde jebkurā gadījumā.
Tātad šeit ir iespējama Kolata funkcijas definīcija.
Mūsu bāzes bloks — ja n ir vienāds ar 1, mēs atgriežam 0.
Nav jāveic nekādas darbības, lai atgrieztos pie 1.
Pretējā gadījumā mums ir divi rekursīvie bloki — viens pāra skaitļiem
un otrs nepāra skaitļiem.
Pāra skaitļu pārbaudes veids ir pārbaudīt, vai n mod 2 ir vienāds ar
0.
Tas būtībā atkal ir jautājums, ja atceraties, kas ir mod - ja es dalu
n ar 2, vai nav atlikuma?
Tas būtu pāra skaitlis.
Tātad, ja n mod 2 ir vienāds ar 0, tiek pārbaudīts, vai tas ir pāra
skaitlis.
Ja tā, es vēlos atgriezt 1, jo tas noteikti aizņem vienu soli plus
jebkura skaitļa Kolata skaitlis, dalīts uz pusi.
Pretējā gadījumā es vēlos atgriezt 1 plus Kolata skaitlis no 3 reiz n
plus 1.
Tas bija otrs rekursīvais solis, ko varējām veikt, lai aprēķinātu
Kolata skaitli — soļu skaits, kas nepieciešams, lai atgrieztos pie 1,
ņemot vērā skaitli.
Tāpēc cerams, ka šis piemērs sniedza jums nelielu priekšstatu par
rekursīvajām procedūrām .
Es ceru, ka jūs domājat, ka kods ir nedaudz skaistāks, ja tas tiek
ieviests elegantā, rekursīvā veidā.
Bet pat ja nedomājiet, rekursija tomēr ir patiešām spēcīgs
instruments.
Tāpēc tas noteikti ir kaut kas tāds, ko vajadzētu saprast, jo,
izmantojot rekursiju, varēsiet veidot patiešām foršas programmas,
kuras citādi būtu sarežģīti uzrakstītas, ja izmantojat cilpas un
iterāciju.
Es esmu Dags Loids.
Šis ir CS50.