ZAMYLA: Upang maunawaan recursion, dapat mo Nauunawaan unang recursion. Ang pagkakaroon ng recursion sa programa disenyo paraan na ikaw ay may self-referential kahulugan. Recursive mga istraktura ng data, halimbawa, ang mga istraktura ng data na isama ang kanilang mga sarili sa kanilang mga kahulugan. Ngunit ngayon, kami ay pagpunta upang tumutok sa recursive function. 

Isipin na mga pag-andar tumagal ng input, argumento, at nagbabalik ng halaga bilang kanilang output kinakatawan ng ito diagram dito. Susubukan naming isipin ang kahon sa bilang ng katawan ng ang pag-andar, na naglalaman ng mga hanay ng mga tagubilin na bigyang-kahulugan ang input at magbigay ng isang output. Pagkuha ng isang mas malapitan naming tingnan sa loob ng katawan ng ang function ay maaaring magbunyag ng mga tawag sa iba pang mga function pati na rin. Sagutan ang simpleng function, foo, na tumatagal ng isang solong string na ito bilang input at mga kopya kung gaano karaming mga titik na string ay may. Ang function na strlen, para sa haba string, ay tinatawag na, na ang output ay kinakailangan para sa mga tawag sa printf. 

Ngayon, kung bakit ang isang recursive function na espesyal ay tumutulong ito sa mga tawag mismo. Maaari naming kumatawan ito recursive tumawag sa orange na arrow looping bumalik sa sarili nito. Ngunit execute mismo muli habilin lamang gumawa ng isa pang recursive tawag, at isa at isa pa. Ngunit recursive function Hindi maaaring walang katapusan. Ang mga ito ay upang wakasan sa paano pa man, o ang iyong programa ay tatakbo nang permanente. 

Kaya kailangan namin upang makahanap ng isang paraan upang masira sa labas ng recursive tawag. Tinatawag namin ito ang batayang kaso. Kapag ang kundisyon base kaso ay nakilala, ang function ay nagbalik ng hindi ginagawang isa pang recursive tawag. Dalhin ito function, hi, isang walang bisa function na na tumatagal ng isang int n bilang input. Ang unang base kaso ay. Kung n ay mas mababa sa zero, i-print at hindi importanteng bagay bumalik Para sa lahat ng iba pang mga kaso, ang function na ay i-print hi at isakatuparan ang recursive tawag. Ang isa pang tawag sa pagpapaandar na hi may isang decremented halaga ng pag-input. 

Ngayon, kahit na i-print namin hi, ang function na ay hindi wakasan hanggang namin bumalik uri nito pagbalik, kung sakaling walang bisa ito. Kaya para sa bawat n bukod sa base ng kaso, ito function na hi ay magbabalik hi ng n minus 1. Dahil ito function na ay walang bisa bagaman, namin hindi tahasang type balik dito. Susubukan naming lamang maisagawa ang pag-andar. Kaya sa pagtawag hi (3) ay i-print at hi isakatuparan hi (2) na executes hi (1) isa na executes hi (0), kung saan ang kondisyon base kaso ay natugunan. Kaya hi (0) prints hindi importanteng bagay at babalik. 

OK. Kaya ngayon na naiintindihan namin ang mga pangunahing kaalaman sa recursive function, na kailangan nila hindi bababa sa isang base ng kaso pati na rin ang isang recursive tawag, ni lumipat sa isang ipaalam mas makabuluhang halimbawa. Ang isa na hindi nagbabalik lamang walang silbi ang kahit na ano. 

Hayaan ang kumuha ng isang pagtingin sa mga factorial ginamit operasyon pinakakaraniwang sa bagay na maaaring mangyari kalkulasyon. Factorial ng n ay ang produkto ng bawat positibong integer na mas mababa sa at pantay-pantay sa n. Kaya factorial limang 5 beses 4 na beses 3 beses 2 beses 1 upang bigyan 120. Apat na factorial ay 4 na beses 3 beses 2 beses 1 upang bigyan ang 24. At sa parehong panuntunan Nalalapat sa anumang positibong integer. 

Kaya kung paano maaari naming magsulat ng isang recursive function na kinakalkula ang factorial ng isang numero? Well, kailangan nating kilalanin ang parehong base kaso at ang recursive tawag. Ang recursive tawag ay ang parehong para sa lahat ng mga kaso maliban sa ang batayang kaso, na nangangahulugan na kakailanganin naming makahanap ng isang pattern na ay magbibigay sa amin ang aming ninanais na resulta. 

Para sa halimbawang ito, tingnan kung paano 5 factorial ay nagsasangkot ng pag-multiply 4 sa pamamagitan ng 3 sa pamamagitan ng 2 sa pamamagitan ng 1 At na napaka-parehong pagpaparami ay nakita dito, ang kahulugan ng 4 factorial. Kaya nakita namin na 5 factorial ay lamang 5 beses 4 factorial. Ngayon ay ilapat ang pattern na ito 4 na factorial pati na rin? Oo. Nakita namin na 4 factorial ay naglalaman ng pagpaparami 3 beses 2 beses 1, ang napaka parehong kahulugan bilang 3 factorial. Kaya 4 factorial ay katumbas ng 4 na beses 3 factorial, at iba pa at iba pa ang aming pattern sticks hanggang 1 factorial, na sa pamamagitan ng kahulugan ay katumbas ng 1. 

Walang iba pang positibong iniwan integer. Kaya mayroon kaming mga pattern para sa ang aming recursive tawag. n factorial ay katumbas ng n beses ang factorial ng n minus 1. At ang aming base kaso? Iyon makikita lamang maging sa aming kahulugan ng 1 factorial. 

Kaya ngayon maaari naming magpatuloy sa pagsusulat code para sa mga function. Para sa mga base ng kaso, kakailanganin naming ang kondisyon n katumbas ay katumbas ng 1, kung saan babalik kami 1. Pagkatapos ay gumagalaw papunta sa recursive tawag, babalik kami n beses ang factorial ng n minus 1. 

Ngayon Subukan natin ito ang aming ipaalam. Subukan ni factorial 4 Hayaan. Alinsunod sa aming function na ito ay katumbas ng 4 na beses factorial (3). Factorial (3) ay katumbas ng 3 beses factorial (2). Factorial (2) ay katumbas ng 2 beses factorial (1), na nagbabalik 1. Factorial (2) ay nagbabalik ngayon 2 beses 1, 2. Factorial (3) ay maaari na ngayong magbalik 3 beses 2, 6. At sa wakas, factorial (4) Ibinabalik ng 4 na beses 6, 24. 

Kung ikaw ay nakakaranas ng anumang paghihirap may recursive tawag, magpanggap na ang function ay gumagana na. Ano ang ibig sabihin ko sa pamamagitan ng ito ay na dapat mong pinagkakatiwalaan ang iyong recursive tawag upang bumalik ang tamang halaga. Halimbawa, kung alam ko na factorial (5) ay katumbas ng 5 beses factorial (4), ako pagpunta sa pinagkakatiwalaan na factorial (4) ay magbibigay sa akin 24. Isipin ito bilang isang variable, kung ikaw pita, bilang kung tinukoy mo na factorial (4). Kaya para sa anumang mga factorial (n), ito ay ang produkto ng n at ang nakaraang factorial. At ito nakaraang factorial ay nakuha sa pamamagitan ng pagtawag factorial ng n minus 1. 

Ngayon, tingnan kung maaari mong ipatupad ang recursive function na ang iyong sarili. Mag-load up ang iyong mga terminal, o run.cs50.net, at magsulat ng isang function sum na kumukuha ng isang integer n at nagbabalik ang kabuuan ng lahat ng mga magkakasunod na positibo integer mula sa n 1. Na naisulat ko ang sums ng ilang mga halaga upang makatulong sa iyo na ang aming. Una, malaman kung ang kondisyon base kaso. Pagkatapos, tumingin sa sum (5). Maaari mong ipahayag ito sa tuntunin ng isa pang sum? Ngayon, kung ano ang tungkol sa sum (4)? Paano mo maaaring ipahayag sum (4) sa mga tuntunin ng isa pang sum? 

Sa sandaling mayroon ka sum (5) at sum (4) ipinahayag sa mga tuntunin ng iba pang mga sums, tingnan ang kung maaari mong kilalanin ang isang pattern para sa sum (n). Kung hindi, subukan ang ilang iba pang mga numero ng at ipahayag ang kanilang sums sa mga tuntunin ng isa pang numero. Sa pamamagitan ng pagtukoy ng mga pattern para sa hiwalay numero, ikaw ay mahusay sa iyong paraan upang pagkikilala ng mga pattern para sa anumang n. 

Recursion ang isang talagang malakas na tool na, kaya siyempre hindi ito limitado sa mga function sa matematika. Recursion ay maaaring gamitin napaka-epektibo kapag pagharap sa mga puno halimbawa. Tingnan ang maikling sa mga puno para sa isang higit pang masinsinang pagsusuri, ngunit sa ngayon isipin na binary paghahanap puno, sa partikular, ay binubuo ng mga node, ang bawat isa may halaga at dalawang mga payo node. Karaniwan, ito ay kinakatawan ng mga node magulang pagkakaroon ng isang linya pagturo sa kaliwa bata node at isa sa kanan bata node. Ang istraktura ng isang binary paghahanap puno lends mismo na rin sa isang recursive paghahanap. Ang recursive tawag alinman sa mga pagpasa sa kaliwa o kanan na node, ngunit higit pa ng na sa tree maikli. 

Sabihin nating nais mong magsagawa ng operasyon sa bawat solong node sa isang binary tree. Paano maaari kang pumunta tungkol sa na? Well, maaari mong magsulat ng isang recursive function na gumaganap ang operasyon sa magulang na node at gumagawa ng isang recursive tumawag sa parehong pag-andar, pagpasa sa kaliwa at karapatan nodes bata. Halimbawa, ito function, foo, na nagbabago ang halaga ng isang ibinigay na node at lahat ng kanyang mga anak na 1. Ang batayang kaso ng isang null node sanhi ang pag-andar upang bumalik, na nagpapahiwatig na walang anumang mga nodes naiwan sa mga sub-puno na. 

Ni maglakad sa pamamagitan nito Hayaang. Ang unang magulang ay 13. Baguhin namin ang halaga sa 1, at pagkatapos ay tumawag sa ang aming pag-andar sa kaliwa pati na rin bilang sa kanan. Ang function, foo, ay tinatawag na sa kaliwa sub-puno unang, kaya kaliwa node ay reassigned sa 1 at foo habilin tawagin sa mga bata na node ni, unang kaliwa at pagkatapos ay ang karapatan, at iba pa at iba pa. At sabihin sa kanila na sangay walang anumang higit pang mga bata kaya ang parehong proseso ay patuloy para sa tamang mga bata hanggang sa node ang buong punong kahoy ay reassigned upang 1. 

Tulad ng iyong nakikita, hindi mo ay limitado sa isa lang recursive tawag. Tulad ng maraming mga bilang ay makakuha ng trabaho tapos na. Paano kung nagkaroon ka ng isang puno kung saan ang bawat na node ay may tatlong mga bata, Kaliwa, gitna, at tama? Paano mo ire-edit foo? Well, simple. Magdagdag lamang ng isa pang recursive tawag at pumasa sa gitna node pointer. 

Recursion ay napakalakas at hindi sa banggitin eleganteng, subalit maaari itong maging isang mahirap konsepto sa una, kaya maging pasyente at dalhin ang iyong oras. Magsimula sa base ng kaso. Ito ay karaniwang ang pinakamadaling upang kilalanin, at pagkatapos ay maaari kang magtrabaho paurong mula doon. Alam mo na kailangan mo upang maabot ang iyong base kaso, nang sa gayon ay maaaring magbibigay sa iyo ng ilang mga pahiwatig. Subukan upang ipahayag ang isang tiyak na kaso sa mga tuntunin ng iba pang mga kaso, o sa mga sub-set. 

Salamat para sa panonood ang maikling. Sa pinakadulo hindi bababa sa, ngayon ay maaari mo Nauunawaan joke na katulad nito. Ang pangalan ko ay Zamyla, at ito ay cs50. 

Dalhin ito function, hi, isang walang bisa function na tumatagal isang int, n, bilang input. Ang unang base kaso ay. Kung n Mas mababa sa 0, naka-print "Hindi importanteng bagay" at pagbalik.