DOUG Lloyd: Jos olet nähnyt video rekursio,
koko prosessi voi olla tuntui hieman maaginen.
Kuinka se toimii?
Miten toiminnot tietävät, että he täytyy odottaa ja odottaa toista arvo
palata eri toimintoa soittaa saadakseen tuloksen haluamme?
>> No, syy tämä toimii, koska jotain tunnetaan kutsupino.
Kun soitat toiminto, järjestelmä kumoaa muistitilaa
että toiminto tehdä työnsä.
Ja me kutsumme näitä paloina muistin ollaan varattu kunkin toiminnon
soittaa pinokehys tai toiminnon kehys.
Ja kuten arvata saattaa, nämä pino kehyksiä
elää pino osa muistia.
>> Useampia toimintoja pinokehys voi esiintyä muistiin tiettynä aikana.
Jos tärkein kutsuu funktiota liikkua, ja liikkua kehottaa suuntaan,
Kaikkien kolmen toiminnon on auki kehyksiä.
Mutta kaikki eivät ole aktiivisia kehyksiä.
Nämä kehykset on järjestetty pinoon.
Ja kehyksen viimeksi soittanut
toiminto on aina päällä pinon.
Ja että on aina aktiivinen kehys.
On vain todella koskaan yksi toiminto se aktiivinen kerrallaan.
Se on päällekkäin pinon.
>> Kun toiminto kutsuu toista toiminto, se tavallaan painaa tauko.
Se tavallaan on pidossa, odottamassa.
Ja toinen pinokehys työnnetään pinoon sen päälle.
Ja että tulee aktiivinen kehys.
Ja runko heti alla se tarvitsee odottaa
kunnes se on jälleen aktiivinen kehys ennen kuin se voi jatkaa työtään.
Kun toiminto on täydellinen ja se on tehty,
sen runko on piipahti pinosta.
Se on terminologiaa.
Ja runko heti sen alla, kuten juuri sanoin,
tulee uusi aktiivinen kehys.
>> Ja jos se kutsuu toisen toiminnon, se tulee keskeyttää uudelleen.
Tämä uusi toiminto n pinon kehys työnnetään päällimmäinen.
Se tulee tehdä työnsä.
Se voi pop takaisin pois.
Ja muut toiminto alla se voi jatkaa uudelleen.
>> Joten mennään läpi tätä uudelleen, etsivät klo ajatus factorial toiminto
että me määritelty rekursio videon nähdä
miten taika takana rekursiivinen prosessi on käynnissä.
Joten tämä on meidän koko tiedosto, eikö?
Me määritelty kaksi functions-- tärkein ja tosiasia.
Ja kuten voisi odottaa, kaikki C-ohjelma on menossa
alkamaan ensimmäisellä rivillä tärkein.
>> Joten luomme uuden pinon kehyksen tärkein.
Ja se tulee alkavat näkyä.
Tärkeimmät puhelut printf.
Ja printf on menossa tulostaa kertoma 5.
Hyvin, se ei tiedä mitä kertoma 5 on,
ja niin tämä puhelu on jo riippuen toisen toiminnon puhelu.
Joten tärkein aikoo keskeyttää oikeassa.
Aion jättää sen nuoli oikeassa, väri
se samanvärinen kuin pinokehys oikealla,
osoittamaan, että tärkein aikoo jäädyttää täällä taas kertoma 5 kutsutaan.
>> Joten kertoma 5 kutsutaan.
Ja se tulee aloittaa hyvin alussa kertoma toiminnon.
Se esittää kysymyksen olen yhtä suuri kuin 1?
On 5 yhtä suuri kuin 1?
No, ei.
Joten se tulee mennä alas muu osa, paluu n kertaa
kertoma n miinus 1.
No okei.
>> Joten nyt, kertoma 5 on riippuen toinen puhelu
ja Kertoma, kulkee 4 kuten parametri.
Ja niin kertoma 5 runko, että punainen kehys,
aikoo jäädyttää oikeassa tuohon linja olen ilmoittanut
ja odottaa kertoma 4 loppuun mitä se tarvitsee tehdä niin, että se
voi tulla aktiivisen kehyksen uudelleen.
>> Joten kertoma 4 alkaa klo alussa kertoma.
On 4 yhtä suuri kuin 1?
Ei, niin se tulee tehdä sama asia.
Se tulee alas muuta haara.
Se tulee päästä Koodirivin.
OK, aion palata neljä kertaa.
Voi, kertoma on 3-- niin faktoria 4 riippuu kertoma 3 viimeistely.
>> Ja niin se tarvitsee soittaa kertoma 3.
Ja joka on menossa läpi saman prosessin uudelleen.
Se alkaa kautta, tulee tänne.
Kertoma 3 riippuu on kertoman 1.
Joten kertoma 2 alkaa, tulee tänne.
Se riippuu kertoma 1.
Kertoman 1 alkaa.
>> OK.
Joten nyt, olemme pääsemässä jonnekin mielenkiintoinen, eikö?
Joten nyt, 1 on yhtä kuin 1.
Ja niin palaamme 1.
Tässä vaiheessa olemme palaamassa.
Toiminto on tehty.
Se käyttäytyminen is-- siellä mitään muuta sitä tehdä,
ja niin pino runko kertoma 1 irtoaa.
Se on valmis.
Se palautti 1.
Ja nyt, kertoma 2, joka oli kehys sen alapuolella
pinossa, tulee aktiivinen kehys.
>> Ja se voi poimia tarkalleen, mihin se jäi.
Se on odottanut factorial 1 loppuun työnsä.
Se on nyt valmis.
Ja niin tässä ollaan.
>> Kertoma 1 palasi arvo 1.
Joten kertoma 2 CAN vaikkapa palata 2 kertaa 1.
Sen työ on nyt tehty.
Se palasi 2 Factorial 3, joka odotti sitä.
Kertoma 3 on nyt yläkehyksen, aktiivinen kehys pinossa.
Ja niin se sanoo, OK, hyvin, aion palata 3 kertaa 2, joka on 6.
Ja aion antaa siitä, että arvostavat takaisin kertoma
4, joka on odottanut minua.
Minulle riitti.
Kertoma 3 irtoaa pinon, ja kertoma 4 on nyt aktiivinen kehys.
>> 4 sanoo, OK, aion palata 4 kertaa kertoma 3, mikä oli kuusi.
Se oli arvo kertoma 3 palasi.
Ja niin 4 kertaa 6 on 24.
Ja aion siirtää että takaisin Factorial
5, joka on odottanut minua.
Kertoma 5 on nyt aktiivinen kehys.
Se tulee palauttaa 5 kertaa kertoma on 4-- 5 kertaa 24, tai 120--
ja antaa siitä, että arvo Takaisin, joka on
odottanut erittäin kärsivällisesti Kauan alareunassa pinon.
>> Siellä se alkoi.
Se teki tämän puhelun.
Useat kehykset otti yläreunassa.
Nyt takaisin pinon.
Se on aktiivinen kehys.
Joten tärkein sai arvon 120 takaisin kertoma 5.
Se odottanut tulostaa että arvo.
Ja sitten se on tehty.
Ei ole enää riviä koodia tärkein.
Joten tärkein runko ponnahtaa pois pino, ja olemme tehneet.
>> Ja siitä rekursio toimii.
Näin pino kehyksiä toimivat.
Ne funktiokutsut joka tapahtui aiemmin
ovat juuri tauko, odottaa annettavasta puhelut
loppuun jotta he voivat tulla aktiivinen runko ja lopuksi mitä he tarvitsevat.
>> Olen Doug Lloyd.
Tämä on CS50.