[MUSIC nagpe-play] 

DOUG LLOYD: marahil sa tingin mo na code ay ginagamit lamang upang makamit ang isang gawain. Isulat mo ito. Ito ang isang bagay. Iyan ay medyo magkano ito. 

Sumulat ng libro mo ito. Patakbuhin mo ang program. Ikaw ay handa na upang patakbuhin. 

Ngunit naniniwala ito o hindi, kung mong code para sa isang mahabang panahon, ikaw ay tunay na maaaring dumating upang makita ang code bilang isang bagay na maganda. Ito malulutas nito ang isang problema sa isang napaka-kawili-wiling paraan, o mayroong lamang isang bagay na talagang malinis at maayos ang tungkol sa mga paraan na ito hitsura. Maaari kang maging tumatawa sa akin, ngunit ito ay totoo. At recursion ay isang paraan na uri ng makakuha ng ideya na ito ng maganda, eleganteng-naghahanap code. Ito malulutas nito ang problema sa mga paraan na ay kawili-wili, ang pag-visualize, at nakakagulat na short. 

Ang mga gawa na paraan recursion ay, ang isang recursive function ay tinukoy bilang isang function na ang tawag ang sarili bilang bahagi ng pagpapatupad nito. Na maaaring mukhang isang maliit na kakaiba, at kami na makita ang isang maliit na piraso tungkol sa kung paano ito gumagana sa isang sandali. Subalit muli, ang mga ito recursive pamamaraan ay magiging kaya eleganteng dahil sila ay pagpunta upang malutas ang problemang ito nang walang pagkakaroon ng lahat ng mga iba pang mga function o mga long loop. Makikita mo na ang mga recursive mga pamamaraan ay pagpunta sa hitsura para sa mga maikling. At sila ay talagang ay pagpunta sa gumawa Mas mukhang maganda ang isang pulutong ng iyong code. 

Bibigyan kita ng isang halimbawa ng mga ito upang makita kung paano maaaring tinukoy ng isang recursive procedure. Kaya't kung ikaw ay pamilyar sa mga ito mula sa matematika klase sa maraming mga taon na ang nakaraan, mayroong isang bagay na tinatawag na ang factorial function, na kung saan ay karaniwang naitala bilang isang exclamation point, na ay tinukoy sa lahat ng positibong integer. At ang paraan na n factorial ay kinakalkula ay mong paramihin ang lahat ng ang mga numero ng mas mababa sa o patas sa n together-- lahat ng mga integer na mas mababa sa o patas sa n magkasama. 

Kaya 5 factorial ay 5 beses 4 na beses sa 3 beses sa 2 beses 1. And 4 factorial ay 4 na beses 3 beses sa 2 beses sa 1 at iba pa. Makukuha mo ang mga ideya. 

Bilang programmers, ay hindi kami gumamit n, exclamation point. Kaya makikita namin tukuyin ang mga factorial function bilang katunayan ng n. At gagamitin namin factorial na lumikha isang recursive solusyon sa isang problema. At sa tingin ko na maaari mong mahanap na ito ay isang pulutong mas biswal akit kaysa sa umuulit bersyon ng mga ito, na kung saan gagamitin din namin ang isang tumingin sa ilang mga sandali. 

Kaya narito ang isang pares ng mga facts-- pun intended-- tungkol factorial-- ang factorial function. Ang factorial ng 1, tulad ng sinabi ko, ay 1. Ang factorial ng 2 ay 2 beses 1. Ang factorial ng 3 ay 3 beses 2 beses 1, at iba pa. Usapan natin ang tungkol sa 4 at 5 na. 

Ngunit pagtingin sa mga ito, ay hindi totoo? Ay hindi factorial ng 2 lang 2 beses ang factorial ng 1? Ibig kong sabihin, ang factorial ng 1 ay 1. Kaya bakit hindi maaaring sabihin lang namin na, dahil factorial ng 2 ay 2 beses sa 1, ito ay talagang 2 beses lang ang factorial ng 1? 

At pagkatapos ay pagpapalawak na ideya, ay hindi ang factorial ng 3 lamang 3 beses ang factorial ng 2? At ang factorial ng 4 ay 4 na beses ang factorial ng 3, at iba pa? Sa katunayan, ang factorial ng anumang numero Maaari lamang ipinahayag kung namin uri ng dalhin ito sa labas magpakailanman. Maaari namin uri ng tuntuning panlahat ang factorial problema bilang na ito ay n beses ang factorial ng n minus 1. Ito ay n beses ang produkto ng lahat ng mga numero na mas mababa kaysa sa akin. 

Ang ideya na ito, ito kalahatan ng problema, ay nagbibigay-daan sa amin upang recursively tukuyin ang mga factorial function. Kapag tinukoy mo ang isang function recursively, may dalawang bagay na kailangan na maging isang bahagi nito. Kailangan mong magkaroon ng isang bagay na tinatawag na isang base kaso, na kung saan, nang ma-trigger mo ito, titigil ang recursive proseso. 

Kung hindi man, ang isang function na ang tawag itself-- bilang maaari mong imagine-- maaaring pumunta sa magpakailanman. Function tawag function tawag ang function ng mga tawag ang function tawag ang function. Kung hindi ka magkaroon ng isang paraan upang itigil ito, ang iyong mga program epektibo ay natigil sa isang walang-katapusang loop. Ito ay pag-crash sa huli, dahil ito ay mauubusan ng memory. Ngunit na sa tabi ng point. 

Kailangan namin na magkaroon ng ilang mga iba pang mga paraan upang ihinto ang mga bagay-bagay maliban sa aming pag-crash na programa, dahil sa isang programa na nag-crash ay marahil ay hindi maganda o eleganteng. At kaya tawag namin ito ang base kaso. Ito ay isang simpleng solusyon sa isang problema na tumitigil ang recursive proseso mula sa nangyari. Kaya na ang isang bahagi ng isang recursive function. 

Ang ikalawang bahagi ay ang recursive kaso. At ito ay kung saan ang recursion ay tunay na magaganap. Ito ay kung saan ang function ay tumawag mismo. 

Hindi ito ay tumawag mismo sa eksakto sa parehong paraan na ito ay tinatawag na. Makikita ito ay isang bahagyang pagkakaiba-iba na gumagawa ng mga problemang ito ay nagsisikap na malutas ang isang maliit bit mas maliit. Ngunit ito ay karaniwang pumasa sa usang lalaki ng paglutas sa karamihan ng mga solusyon sa ibang call down ang linya. 

Alin sa mga ito na tingin tulad ng base kaso dito? Aling isa sa mga ito ay ganito ang hitsura ng pinakasimpleng solusyon sa isang problema? Kami ay may isang bungkos ng mga factorials, at maaari naming patuloy pagpunta on-- 6, 7, 8, 9, 10, at iba pa. 

Ngunit isa sa mga ito hitsura tulad ng isang mahusay na kaso na ang base kaso. Ito ay isang napaka-simpleng solusyon. Hindi natin kailangang gawin ang anumang bagay na espesyal. 

Ang factorial ng 1 ay 1 lang. Hindi natin kailangang gawin ang anumang pagpaparami sa lahat. Tila tulad ng kung kami ay pagpunta upang subukan at malutas ang problemang ito, at kailangan naming ihinto ang recursion sa isang lugar, marahil gusto nating huminto ito kapag kami makakuha ng hanggang 1. Hindi namin nais na huminto sa bago na. 

Kaya kung kami ay pagtukoy aming factorial function, narito ang isang balangkas para sa kung paano namin maaaring gawin iyon. Kailangan namin mag-plug ng mga dalawang bagay- ang base kaso at ang recursive kaso. Ano ang base kaso? Kung n ay katumbas ng 1, bumalik 1-- na isang tunay na simpleng problema sa paglutas. 

Ang factorial ng 1 ay 1. Ito ay hindi 1 beses kahit ano. Ito ay 1 lang. Ito ay isang napakadaling katotohanan. At sa gayon ay maaari maging ang aming base kaso. Kung kami makakuha ng lumipas 1 sa ito function, babalik kami 1 lang. 

Ano ang recursive kaso malamang ganito ang hitsura? Para sa lahat ng iba pang numero bukod sa 1, ano ang pattern? Well, kung kami ay pagkuha ang factorial ng n, ito ay n beses ang factorial ng n minus 1. 

Kung kami ay ang pagkuha ng mga factorial ng 3, ito ay 3 beses ang factorial ng 3 minus 1, o 2. At kaya kung kami ay hindi naghahanap sa 1, kung hindi, return n beses ang factorial ng n minus 1. Ito ay medyo tapat. 

At para sa kapakanan ng pagkakaroon ng bahagyang mas malinis at mas eleganteng code, malaman na kung kami ay may single-line loops o single-line kondisyon sanga, maaari naming kumuha alisan ng lahat ng mga curly braces sa kanilang paligid. Kaya maaari naming pagsamahin ito sa mga ito. Ito ay eksakto ang parehong functionality bilang na ito. 

Tingin lang ako sa pagkuha ng malayo ang kulot braces, dahil mayroon lamang isang linya sa loob ng mga kondisyon sanga. Kaya ang mga ito kumilos na magkapareho. Kung n ay katumbas ng 1, bumalik 1. Kung hindi man bumalik n ulit ang factorial ng n minus 1. Kaya ginagawa namin ang problema mas maliit. Kung n nagsisimula bilang 5, kami ay pagpunta sa bumalik 5 beses ang factorial ng 4. At kami na makita sa isang minuto kapag ang usapan namin tungkol sa stack-- tawag sa isa pang video kung saan ang pinag-uusapan natin ang tumawag stack-- namin malaman tungkol sa kung bakit gumagana nang eksakto ang proseso na ito. 

Ngunit habang factorial 5 sabi bumalik 5 beses factorial ng 4, at 4 ay pagpunta sa sabihin, OK, well, return 4 na beses ang factorial ng 3. At tulad ng makikita mo, hindi namin uri ng papalapit 1. Kami ay nakakakuha ng mas malapit at mas malapit sa na base kaso. 

At sa sandaling pindutin namin ang base kaso, lahat ng mga nakaraang mga pag-andar magkakaroon ng sagot na kanilang hinahanap. Factorial ng 2 ay sinasabi return 2 beses ang factorial ng 1. Well, factorial ng 1 nagbabalik 1. Kaya ang tawag para sa factorial ng 2 makakabalik 2 beses sa 1, at bigyan na bumalik sa factorial ng 3, na kung saan ay naghihintay para sa resultang iyon. 

At pagkatapos ay maaari itong makalkula kanyang resulta, 3 beses 2 ay 6, at nagbibigay ng mga ito pabalik sa factorial ng 4. At muli, kami ay may isang video sa stack ng tawag kung saan ito ay may larawan ng isang maliit na higit sa kung ano ang sinasabi ko ngayon. Ngunit ito ay ito. Ito nag-iisa ay ang solusyon sa pagkalkula ng factorial ng isang numero. 

Ito ay linya lamang ang apat ng mga code. Iyan ay medyo cool, di ba? Ito ay uri ng sexy. 

Kaya sa pangkalahatan, ngunit hindi laging, isang recursive function maaaring palitan ng isang loop sa isang non-recursive function. Kaya dito, tabi-tabi, ay ang umuulit bersyon ng factorial function. Pareho sa mga ito ang Calculate eksakto ang parehong bagay. 

Sila ay parehong makalkula ang factorial ng n. Ang bersyon sa kaliwa ay gumagamit ng recursion na gawin ito. Ang bersyon sa kanan ay gumagamit ng pag-ulit upang gawin ito. 

At pansinin, mayroon kaming na idedeklara isang variable ng isang produkto ng integer. At pagkatapos naming loop. Hanggat n ay mas malaki kaysa sa 0, kami ay panatilihin ang pag-multiply na produkto sa pamamagitan n at decrementing n hanggang namin makalkula ang mga produkto. Kaya ang dalawang pag-andar, muli, gawin ang eksaktong parehong bagay. Subalit hindi nila gawin ito sa eksakto sa parehong paraan. 

Ngayon, ito ay posible na may higit sa isang base kaso o higit pa sa isang recursive kaso, depende sa kung ano ang iyong function na ay sinusubukan na gawin. Ay hindi kinakailangan mo lamang limitado sa isang solong base kaso o isang solong recursive case. Kaya ang isang halimbawa ng isang bagay may maramihang base kaso maaaring this-- ang Fibonacci number sequence. 

Maaari mong isipin ang mula sa elementarya araw ng paaralan na ang pagkakasunod-sunod Fibonacci ay tinukoy tulad this-- ang unang elemento ay 0. Ang pangalawang elemento ay 1. Pareho sa mga ito ay sa pamamagitan lamang ng kahulugan. 

Pagkatapos bawat iba pang mga elemento ay tinukoy bilang ang kabuuan ng n minus 1 at n minus 2. Kaya ang ikatlong elemento ay magiging 0 plus 1 ay 1. At pagkatapos ay ang ika-apat na elemento ay ang pangalawang elemento, 1, plus ang ikatlong elemento, 1. At iyon ay magiging 2. At iba pa at iba pa. 

Kaya sa kasong ito, kami ay may dalawang base kaso. Kung n ay katumbas ng 1, bumalik 0. Kung n ay katumbas ng 2, bumalik 1. Kung hindi, bumalik Fibonacci ng n minus 1 plus Fibonacci ng n minus 2. 

Kaya na ang maramihang mga base kaso. Ano ang tungkol sa maramihang recursive kaso? Well, may isang bagay tinatawag na ang Collatz haka-haka. Hindi ako pupunta sa mga sinasabi, alam mo kung ano na, dahil ito ay aktwal na ang aming huling Ang problema para sa partikular na video. At ito ay ang aming exercise upang magtulungan pa. 

Kaya narito ang kung ano ang Collatz haka-haka is-- ito ay sumasaklaw sa bawat positibong integer. At ito speculates na ito ay laging posible upang makabalik sa 1 kung susundin mo ang mga hakbang na ito. Kung n ay 1, itigil. Mayroon kaming bumalik sa 1 kung n ay 1. 

Kung hindi man, pumunta sa pamamagitan ng proseso muli sa n hinati sa 2. At makita kung maaari kang makakuha ng bumalik sa 1. Kung hindi man, kung n ay kakaiba, pumunta sa pamamagitan ng ang proseso na ito muli sa 3n plus 1, o 3 beses n plus 1. Kaya dito kami ay may isang solong base kaso. Kung n ay katumbas ng 1, itigil. Hindi kami gumagawa ng anumang mga mas recursion. 

Ngunit kami ay may dalawang recursive kaso. Kung n ay kahit na, ginagawa namin ang isa recursive kaso, pagtawag n hinati sa 2. Kung n ay kakaiba, gawin namin ang isang iba't ibang mga recursive kaso sa 3 beses n plus 1. 

At upang ang mga layunin para sa video na ito ay upang kumuha ng isang segundo, i-pause ang video, at subukan at isulat ito recursive function Collatz kung saan kayo na ipasa sa ang halaga ng n, at ito kinakalkula kung gaano karaming mga hakbang na ito kinakailangan upang makakuha ng sa 1 kung nagsimula ka mula n at susundin mo ang mga hakbang na ito up sa itaas. Kung n ay 1, ito ay tumatagal ng 0 na mga hakbang. Kung hindi man, ito ay pagpunta sa kumuha ng isang hakbang plus gayunpaman maraming mga hakbang na ito ay tumatagal sa alinman n hinati sa 2 kung n ay kahit na, o 3n plus 1 kung n ay kakaiba. 

Ngayon, na ilagay up ako sa screen dito isang pares ng mga pagsubok para sa iyo, isang pares ng mga kaso pagsusuri para sa iyo, upang makita kung ano ang mga iba't-ibang numero Collatz ay, at din ng isang paglalarawan ng halimbawa sa mga hakbang na kailangan ay wala na sa pamamagitan gayon ay maaari mo uri ng makita ang proseso na ito sa aksyon. Kaya kung n ay katumbas ng 1, Collatz ng n ay 0. Hindi mo na kailangang gawin anumang bagay upang makabalik sa 1. Ikaw ay naka-doon. 

Kung n ay 2, ito ay tumatagal ng isang hakbang upang makakuha ng 1. Magsisimula ka na may 2. Well, 2 ay hindi katumbas ng 1. Kaya ito ay magiging isang hakbang plus gayunpaman maraming mga hakbang na ito tumatagal sa n hinati sa 2. 

2 hinati sa 2 ay 1. Kaya ito ay tumatagal ng isang hakbang plus gayunpaman maraming mga hakbang na kailangan para sa 1. 1 ay dadalhin zero na mga hakbang. 

Para sa 3, tulad ng makikita mo, may kasangkot lubos ng ilang mga hakbang. Pumunta ka mula sa 3. At pagkatapos mong pumunta sa 10, 5, 16, 8, 4, 2, 1. Ito ay tumatagal ng pitong mga hakbang upang makabalik sa 1. At tulad ng makikita mo, may isang ilang iba pang mga kaso ng pagsubok dito upang subukan ang iyong mga programa. Kaya muli, i-pause ang video. At kukunin ko na pumunta lumipat pabalik ngayon upang kung ano ang aktwal na proseso ay dito, kung ano ang ito haka-haka ay. 

Tingnan kung maaari mong malaman kung kung paano matukoy Collatz ng n upang ito ay kinakalkula kung gaano karaming hakbang na aabutin upang makakuha ng 1. Kaya sana, ikaw ay naka-pause ang video at ikaw ay hindi lamang naghihintay para sa akin upang mabigyan ka ng sagot dito. Ngunit kung ikaw ay, well, narito pa rin ang sagot. 

Kaya dito ang isang posibleng kahulugan ng Collatz function. Ang aming base case-- kung n ay katumbas ng 1, bumalik kami 0. Ito ay hindi kumuha ng anumang mga hakbang na ito upang makakuha ng bumalik sa 1. 

Kung hindi man, kami ay may dalawang recursive cases-- isa para sa kahit na mga numero at ang isa ay para sa kakaiba. Ang paraan test ko para sa kahit na mga numero ay upang suriin kung n mod 2 ay katumbas ng 0. Ito ay isa lamang, muli, humihingi ng tanong, kung isipin mo kung ano ang mod is-- kung ako hatiin n pamamagitan ng 2 ay may walang nalalabing? Iyon ay magiging isang kahit na numero. 

At kaya kung n mod 2 ay katumbas ng 0 ay testing ay ito ng isang kahit na numero. Kung gayon, gusto kong bumalik 1, dahil ito ay siguradong pagkuha ng isang hakbang plus Collatz ng kahit anong numero ay kalahati ng sa akin. Kung hindi man, gusto kong bumalik 1 plus Collatz ng 3 beses n plus 1. Iyon ay ang iba pang mga recursive step na tayo maaaring tumagal ng upang makalkula ang Collatz-- ang bilang ng mga hakbang ito ay tumatagal upang makabalik sa 1 bibigyan ng isang numero. Kaya sana, halimbawa na ito nagbigay sa iyo ng isang maliit na piraso ng isang lasa ng recursive pamamaraan. Sana, sa tingin mo na code ay isang maliit na mas maganda kung ipinatupad sa isang eleganteng, recursive na paraan. Ngunit kahit na hindi, recursion ay isang talagang malakas na kasangkapan gayunman. At sa gayon ito ay talagang isang bagay upang makakuha ng inyong ulo sa paligid, dahil ikaw ay maaaring lumikha ng medyo cool programa gamit recursion na maaaring sa kabilang banda ay mahirap unawain na magsulat kung gumagamit ka ng mga loop at pag-ulit. Ako Doug Lloyd. Ito ay CS50.