DOUG LLOYD: Kapag kayo ay nakakita ang video sa recursion,
maaaring mayroon ang buong proseso tila isang maliit na bit nakapagtataka.
Paano ito gumagana?
Paano ko malalaman kung ang mga function na ang mga ito kailangang maghintay at maghintay para sa isa pang halaga
upang bumalik mula sa isang iba't ibang mga pag-andar tumawag upang makuha ang mga resulta na gusto natin?
>> Well, ang dahilan na ito ay gumagawa ay dahil ng isang bagay na kilala bilang ang stack ng tawag.
Kapag tumawag ka ng isang function, ang nagtatakda ng sistema tabi espasyo sa memory
para sa na function na gawin ang trabaho nito.
At ang tawag namin sa mga tipak ng memorya na ay ina-magtabi para sa bawat pag-andar
tumawag sa isang stack frame o isang function frame.
At bilang maaari mong asahan, mga frames stack
nakatira sa stack bahagi ng memorya.
>> Higit sa isang function na stack frame maaaring umiiral sa memory sa isang ibinigay na oras.
Kung pangunahing tawag ng isang function ilipat, at ilipat tawag direksyon,
lahat ng tatlong mga pag-andar na may bukas na mga frame.
Ngunit hindi lahat sila ay may aktibong frames.
Ang mga frame ay nakaayos sa isang stack.
At ang mga frame mula sa pinakahuling tinawagan
function na ay palaging sa tuktok ng stack.
At iyon ay palaging ang aktibong frame.
Mayroon lamang talagang kailanman isa function na ay aktibo sa isang pagkakataon.
Ito ang isa sa itaas ng stack.
>> Kapag ang isang function ng mga tawag sa isa pang function, ito uri ng mga pagpindot pause.
Ito ang uri ng ay naka-hold, naghihintay.
At isa pang stack frame ay itinutulak papunta sa stack sa tuktok ng mga ito.
At iyon ay magiging mga aktibong frame.
At ang mga frame agad sa ibaba na kinakailangan nito upang maghintay
hanggang sa ito ay muli ang mga aktibong frame bago ito ay maaaring ipagpatuloy ang kanyang trabaho.
Kapag ang isang function ay kumpleto at tapos na ito,
frame nito ay pop-off ang stack.
Iyan ay ang terminolohiya.
At ang mga frame agad sa ibaba nito, tulad ng sinabi ko lang,
nagiging bagong mga aktibong frame.
>> At kung ito tawag ng isa pang function, ito ay pagpunta sa i-pause muli.
Ay stack frame na bagong pag-andar ng hunhon papunta sa tuktok ng stack.
Makikita ito gawin ang trabaho nito.
Maaaring pop-back off.
At ang iba pang mga function ibaba maaari itong ipagpatuloy muli.
>> Kaya sabihin pumunta sa pamamagitan na ito muli, naghahanap sa ideya ng factorial na function
na natukoy namin sa recursion video upang makita
eksakto kung paano ang mga magic sa likod na ito recursive proseso ay nagaganap.
Kaya ito ay ang aming buong file, i-right?
Aming natukoy dalawang functions-- pangunahing at katotohanan.
At bilang maaari naming asahan, anumang programa C ay pagpunta
upang simulan sa unang linya ng main.
>> Kaya gumawa kami ng isang bagong stack frame para sa main.
At ito ay pagpunta upang magsimulang tumakbo.
Main tawag printf.
At printf ay pagpunta sa i-print ang factorial 5.
Well, ito ay hindi alam kung ano ang factorial ng 5 ay,
at iba ang tawag na ito ay ginagamit na depende sa isa pang pag-andar ng tawag.
Kaya pangunahing ay pagpunta sa i-pause ang may karapatan.
Ako gonna iwanan nito palaso doon, kulay
ito ang parehong kulay bilang ang stack frame sa kanan,
upang ipahiwatig na pangunahing ay pagpunta upang i-freeze dito habang factorial 5 ay tinatawag na.
>> Kaya factorial 5 ay tinatawag na.
At ito ay pagpunta sa simulan sa pinakadulo simula ng factorial function.
Ito nagtatanong ang tanong ay kasing-halaga ko sa 1?
Ay 5 katumbas ng 1?
Hindi.
Kaya ito ay pagpunta upang lumusong sa ang ibang tao ng bahagi, return n ulit
factorial ng n minus 1.
Well, OK.
>> Kaya ngayon, factorial ng 5 ay depende sa isa pang tawag
sa factorial, pagpasa sa 4 na bilang ng mga parameter.
At upang ang mga factorial ng 5 frame, na red frame,
ay pagpunta sa i-freeze ang may karapatan sa na linya Isinaad ko
at hintayin ang factorial ng 4 upang matapos kung ano ang kinakailangan nito upang gawin ito na pagkatapos na ito
ay maaaring maging muli ang mga aktibong frame.
>> Kaya factorial ng 4 ay nagsisimula sa simula ng factorial.
Ay 4 na katumbas ng 1?
Hindi, kaya ito ay pagpunta sa gawin ang parehong bagay.
Ito ay pagpunta sa pumunta down ang ibang tao na branch.
Ito ay pagpunta upang makakuha ng sa na linya ng code.
OK, ako pagpunta upang bumalik sa apat na beses.
Oh, factorial ng 3-- kaya factorial ng 4 ay depende sa factorial ng 3 pagtatapos.
>> At kaya kailangan nito upang tumawag factorial ng 3.
At na gonna pumunta sa pamamagitan ng muli ang parehong proseso.
Nagsisimula ito sa pamamagitan, ay makakakuha dito.
Factorial ng 3 depende on factorial ng 1.
Kaya factorial ng 2 nagsisimula, nakakakuha dito.
Ito ay depende sa factorial ng 1.
Factorial ng 1 magsisimula.
>> SIGE.
Kaya ngayon, kami ay pagkuha sa tabi-tabi na interesante, di ba?
Kaya ngayon, 1 ay katumbas ng 1.
At kaya bumalik kami 1.
Sa puntong ito, kami ay bumabalik.
Ang function na ay tapos na.
Ito ay ang pag-uugali is-- mayroong wala nang iba pa para sa mga ito upang gawin,
at sa gayon ang stack frame para sa factorial ng 1 nagpa-pop off.
Ito ay tapos na.
Ibinalik It 1.
At ngayon, factorial ng 2, kung saan ay agad-agad ang mga frame sa ibaba nito
sa stack, nagiging aktibo frame.
>> At ito ay maaaring kunin nang eksakto kung saan ito huminto.
Ito ay nai-naghihintay para sa isang factorial ng 1 upang tapusin ang trabaho nito.
Ito ay tapos na ngayon.
At kaya dito tayo.
>> Factorial ng 1 ibabalik ang halaga ng 1.
Kaya factorial ng 2 lata sabihin nating ibalik 2 beses 1.
Ang trabaho ay tapos na ngayon.
Ito ay bumalik sa 2 hanggang factorial ng 3, na kung saan ay naghihintay para sa mga ito.
Factorial ng 3 ay ang frame tuktok ngayon, ang aktibong frame sa stack.
At kaya ang sinasabi nito, OK, well, ako pagpunta upang bumalik sa 3 beses sa 2, na kung saan ay 6.
At ako pagpunta upang bigyan na Pinahahalagahan pabalik sa factorial
ng 4, na kung saan ay naghihintay para sa akin.
Tapos na ako.
Factorial ng 3 nagpa-pop-off ang stack, at factorial ng 4 ay ang aktibong frame ngayon.
>> 4 sabi, OK, ako pagpunta upang bumalik sa 4 na beses ang factorial ng 3, na kung saan ay anim na.
Iyon ay may halaga na factorial ng 3 ibabalik.
At kaya 4 na beses 6 ay 24.
At ako pagpunta sa pumasa na bumalik sa factorial
5, na kung saan ay naghihintay para sa akin.
Factorial 5 ay ang aktibong frame ngayon.
Ito ay pagpunta upang bumalik 5 beses factorial ng 4-- 5 beses 24, o 120--
at bigyan ng halaga na bumalik sa pangunahing, na may
naghihintay napaka matiyagang para sa isang mahabang panahon sa ilalim ng stack.
>> Ito ay kung saan ito nagsimula.
Ito ay ginawa ang tawag na ito.
Ilang frames kinuha higit sa itaas.
Ito ngayon ay bumalik sa tuktok ng stack.
Ito ay ang aktibong frame.
Kaya pangunahing nakuha ang halaga ng 120 pabalik mula factorial 5.
Ito ay nai-naghihintay na i-print out ang halaga.
At pagkatapos ay tapos na ito.
Walang higit pang mga linya ng code sa main.
Kaya nagpa-pop frame main ni off stack, at tapos na kami.
>> At na kung paano gumagana recursion.
Iyon ay kung paano gumagana stack frame.
Ang mga tawag sa function na na nangyari dati
ay lamang sa i-pause, naghihintay para sa kasunod na mga tawag
upang matapos upang sila ay maaaring maging ang mga aktibong frame at tapusin ang kung ano ang kailangan nilang gawin.
>> Ako Doug Lloyd.
Ito ay CS50.