Doug LLOYD: Ja esat redzējis video par recursion,
viss process varētu būt likās mazliet maģisks.
Kā tas darbojas?
Kā funkcijas zina, ka viņi jāgaida un gaidīt citu vērtību
atgriezties no citas funkcijas piezvanīt, lai iegūtu rezultātu mēs gribam?
>> Nu, iemesls tas darbojas, ir tāpēc, ka par kaut ko sauc par zvanu kaudze.
Kad jūs zvanu funkciju, tad Sistēma atceļ telpu atmiņā
šai funkcijai darīt savu darbu.
Un mēs aicinām šos gabalos atmiņas ka tiek atvēlēti katrai funkcijai
zvanīt kaudze rāmi vai funkcija rāmi.
Un, kā jūs varētu gaidīt, šie kaudze rāmji
dzīvo uz skursteņa daļu atmiņas.
>> Vairāk nekā vienu funkciju kaudze rāmis var pastāvēt atmiņā kādā noteiktā laikā.
Ja galvenais aicina funkciju pārvietot, un pārvietot aicina virzienu,
visi trīs funkcijas ir atvērtas rāmji.
Bet tie nav visi ir aktīvas rāmji.
Šie rāmji ir izkārtoti skursteni.
Un rāmis no zvanījis
funkcija ir vienmēr uz augšējās.
Un ka vienmēr ir aktīvs rāmis.
Tur ir tikai tiešām kādreiz viens funkcija, kas ir aktīva laikā.
Tas ir viens virs skursteņa.
>> Kad funkcija prasa cits funkcija, tā veida preses pauzi.
Tā veida ir aizturēts, gaida.
Un vēl kaudze rāmis ir uzstājām uz kaudze uz augšu no tā.
Un tas kļūst aktīvs rāmis.
Un rāmis nekavējoties Turpmāk tai ir jāgaida
līdz tas ir atkal aktīvs rāmis pirms tā var atsākt darbu.
Ja funkcija ir pilnīgs un tas ir darīts,
tā rāmis ir popped off kaudzīti.
Tas ir terminoloģija.
Un rāmis nekavējoties zem tā, kā es tikko teicu,
kļūst par jauno aktīvo rāmis.
>> Un, ja tas prasa citu funkciju, tas notiek, lai apturētu vēlreiz.
Ka jauna funkcija ir kaudze rāmis uzstājām uz augšu kaudze.
Tas būs darīt savu darbu.
Tas varētu pop atpakaļ off.
Un citas funkcijas Turpmāk tas var atsākt no jauna.
>> So iesim cauri šis atkal meklē pie ideju Faktoriāla funkcijas
ka mēs definēts rekursijas video, lai redzētu
tieši tā, kā burvju aiz šī rekursīvs process notiek.
Tātad šis ir mūsu visu failu, vai ne?
Mēs definēti divi functions-- galvenais un fakts.
Un, kā mēs varētu gaidīt, jebkurš C programma ir gatavojas
sākt pirmajā rindā galvenais.
>> Tātad, mēs izveidot jaunu kaudze rāmis galvenais.
Un tas notiek, lai sāktu darboties.
Galvenie zvani printf.
Un printf gatavojas izdrukāt faktoriālu 5.
Nu, tas nav zināms kāda factorial 5 ir,
un tāpēc šis aicinājums ir jau Atkarībā no citu funkciju zvanu.
Tātad galvenais gatavojas pauze turpat.
Es esmu gonna atstāt tās bultiņa pa labi tur, krāsu
tas tādā pašā krāsā kā kaudze rāmis labajā pusē,
norādīt, ka galvenais gatavojas iesaldēt šeit, kamēr faktoriālu no 5 sauc.
>> Tātad faktoriālu no 5 sauc.
Un tas notiek, lai sāktu pie ļoti sākot no faktoriālo funkciju.
Tā uzdod jautājumu man vienāds ar 1?
Ir 5 vienāds ar 1?
Nu, nē.
Tātad tas notiek, lai iet uz leju, lai cits daļa, atgriešanās n reizes
factorial n mīnus 1.
Nu, OK.
>> Tāpēc tagad, faktoriālu 5 ir Atkarībā no citu zvanu
uz Faktoriāls, iet in 4 kā parametru.
Un tā faktoriālu 5 rāmis, ka sarkanā rāmī,
gatavojas iesaldēt turpat tajā rindā es esmu norādījis
un gaidīt faktoriālu 4 līdz beigām kas tas ir jādara tā, lai pēc tam to
var kļūt aktīvās kadra vēlreiz.
>> Tātad faktoriālu 4 sākas sākums faktori.
Ir 4 vienāds ar 1?
Nē, tā tas būs darīt to pašu.
Tas notiek, lai iet uz leju cits filiāli.
Tas notiek, lai saņemtu to, ka koda rindu.
Labi, es esmu gatavojas atgriezties četras reizes.
Ak, faktoriālu no 3-- tik faktoriālu 4 atkarīgs faktoriālu 3 apdari.
>> Un tā tas ir nepieciešams, lai izsauktu faktoriālu 3.
Un tas ir gonna iet cauri pats process vēlreiz.
Tas sākas ar, izpaužas šeit.
Faktoriāls gada 3. atkarīgs par faktoriālu 1.
Tātad factorial 2 sākas, izpaužas šeit.
Tas ir atkarīgs no faktoriālu 1.
Faktoriāls no 1 sākas.
>> LABI.
Tāpēc tagad mēs esam nonākuši kaut kur interesanti, vai ne?
Tātad tagad, 1 ir vienāds ar 1.
Un tā mēs atgriežamies 1.
Šajā brīdī, mēs atgriežamies.
Funkcija ir darīts.
Tā ir rīcība is-- tur nekas cits, lai to darīt,
un tā kaudze rāmis faktoriālu no 1 pops off.
Tas ir pabeigts.
Tas atgriezās 1.
Un tagad, faktoriālu 2, kas uzreiz bija rāmis zem tā
kaudze, kļūst aktīvs rāmis.
>> Un tas var uzņemt tieši tur, kur tas tika pārtraukts.
Tas ir bijis gaida faktoriālo no 1 līdz pabeigt savu darbu.
Tā tagad ir pabeigta.
Un tāpēc šeit mēs esam.
>> Faktoriāls gada 1. atgriezās vērtību 1.
Tātad faktoriālu no 2 var teiksim atgriezties 2 reizes 1.
Tās darbs tagad ir paveikts.
Tas atgriezās no 2 līdz Faktoriāls 3, kas gaidīja to.
Faktoriāls 3. tagad top rāmis, aktīvā rāmis kaudze.
Un tā tas saka, OK, labi, es eju lai atgrieztos 3 reizes 2, kas ir 6.
Un es esmu gatavojas sniegt, ka vērtējam atpakaļ faktoriālo
4, kas gaidīja mani.
Esmu pabeidzis.
Faktoriāls gada 3. pops off kaudze, un factorial 4. tagad ir aktīvs rāmis.
>> 4 saka, OK, es esmu gatavojas atgriezties 4 reizes faktoriālu 3, kas bija seši.
Tas bija par vērtību, faktoriālu no 3 atgriezās.
Un tā 4 reizes 6 ir 24.
Un es esmu gatavojas iet ka atpakaļ uz Faktoriāls
5, kas gaidīja mani.
Faktoriāls 5. tagad ir aktīvs rāmis.
Tas notiek, lai atgrieztos 5 reizes faktoriālu no 4-- 5 reizes 24 vai 120--
un dot šo vērtību atpakaļ uz galveno, kas ir
gaidīja ļoti pacietīgi priekšlikums ilgu laiku apakšā krāvuma.
>> Tas ir, ja tas viss sākās.
Tas padarīja šo aicinājumu.
Vairāki rāmji pārņēma augšpusē.
Tagad ir atpakaļ uz augšu kaudze.
Tas ir aktīvs rāmis.
Tātad galvenais ieguva vērtību 120 atpakaļ no faktoriālu 5.
Tas ir bijis gaida izdrukāt šo vērtību.
Un tad tas ir darīts.
Nav vairāk rindiņas kodu galvenajā.
Tātad galvenais ir rāmis pops off kaudze, un mēs esam darījuši.
>> Un tas, kā rekursijas darbi.
Tas ir kā kaudze rāmji strādāt.
Šie funkcija zvani kas noticis iepriekš
ir tikai uz pauzes, gaidot par turpmākiem uzaicinājumiem
lai pabeigtu, lai viņi varētu kļūt par aktīvo rāmis un pabeigt to, ko viņi ir jādara.
>> Es esmu Doug Lloyd.
Tas ir CS50.