[Muzikos grojimo] 

Doug LLOYD: JÅ«s tikriausiai manote, kad kodas tik naudojamas atlikti uÅ¾duotÄ¯. JÅ«s raÅ¡ote jÄ¯. Ji kaÅ¾kÄ. Tai gana daug. 

JÅ«s kaupia jÄ. Paleidus programÄ. JÅ«s esate gera eiti. 

Bet tiki jis ar ne, jei JÅ«s kodas ilgÄ laikÄ, jÅ«s iÅ¡ tikrÅ³jÅ³ gali ateiti pamatyti kodas, kaip kaÅ¾kas, kad yra graÅ¾i. Tai iÅ¡sprendÅ¾ia problemÄ Ä¯ labai Ä¯domus bÅ«das, ar ten tiesiog kaÅ¾kas tikrai tvarkingas apie tai, kaip jis atrodo. Jums gali bÅ«ti juokiasi ne man, bet tai tiesa. Ir rekursija yra vienas iÅ¡ bÅ«dÅ³ rÅ«Å¡iuoti gauti Å¡iÄ idÄjÄ iÅ¡ graÅ¾us, elegantiÅ¡kas atrodanÄius kodÄ. Tai iÅ¡sprendÅ¾ia problemas tokiu bÅ«du, kad yra Ä¯domus, lengva Ä¯sivaizduoti, ir stebÄtinai trumpas. 

Beje Rekursija darbai yra, grÄ¯Å¾tamojo funkcija yra apibrÄÅ¾iamas kaip funkcija, kad reikalauja pati kaip jos vykdymo. Tai gali atrodyti Å¡iek tiek keista, ir mes pamatyti Å¡iek tiek apie, kaip tai veikia iÅ¡kart. Bet vÄl, tai Rekurentiniai procedÅ«ros bus tokia elegantiÅ¡ka nes jie ketina iÅ¡sprÄsti Å¡iÄ problemÄ, be turintys visas Å¡ias ir kitas funkcijas ar Å¡ie ilgi kilpas. Pamatysite, kad tai rekursywny procedÅ«ros ketiname ieÅ¡koti toks trumpas. Ir jie tikrai ketina padaryti JÅ«sÅ³ kodas atrodo daug graÅ¾esnÄ. 

AÅ¡ duosiu jums pavyzdÄ¯ tai pamatyti, kaip rekursywny procedÅ«ra gali bÅ«ti nustatyta. Taigi, jei esate susipaÅ¾inÄ su Å¡iuo iÅ¡ matematikos klasÄs, prieÅ¡ daugelÄ¯ metÅ³, Yra kaÅ¾kas, vadinamas faktorialinis funkcija, kuri paprastai Å¾ymimas kaip Å¡auktukas, kuris yra apibrÄÅ¾iamas per visi teigiami sveikieji skaiÄiai. Ir taip, kad n faktorialas yra apskaiÄiuojamas yra padauginti visus numeriai maÅ¾iau nei arba lygus n together-- visi sveikieji maÅ¾iau nei arba lygus n kartu. 

Taigi 5 faktorialas yra 5 kartus 4 kartus 3 kartus 2 kartus 1. Ir 4 faktorialas yra 4 kartus 3 kartus 2 kartus 1 ir pan. JÅ«s gaunate idÄja. 

Kaip programuotojai, mes do not naudoti N, Å¡auktukas. Taigi mes apibrÄÅ¾ti faktorialas funkcija taip sakant n. Ir mes naudosime faktorialas sukurti rekursywny sprendimas problema. Ir manau, kad jÅ«s galite rasti kad tai daug labiau vizualiai patrauklus nei kartotinis versija tai, kuris mes taip pat paÅ¾velgti Ä¯ Å¡iuo metu. 

Taigi Äia yra pora facts-- kalambÅ«ras intended-- apie factorial-- faktorialas funkcija. 1 faktorialas, kaip sakiau, yra 1. 2 faktorialas yra 2 kartus 1. 3 faktorialas yra 3 kartÅ³ 2 kartus 1, ir taip toliau. Mes kalbÄjome apie 4 ir 5 jau. 

Bet Å¾iÅ«ri Å¡Ä¯, nÄra tai tiesa? Ar ne faktorialas 2 tik 2 kartus 1 faktorialas? AÅ¡ turiu galvoje, 1 faktorialas yra 1. Taigi kodÄl mes negalime tiesiog pasakyti, kad nuo faktorialas 2 yra 2 kartus 1 tai tikrai tik 2 kartus 1 faktorialas? 

Ir tada iÅ¡plÄsti Å¡iÄ idÄjÄ, nÄra 3 faktorialas tik 3 kartus 2 faktorialas? Ir iÅ¡ 4 faktorialas yra 4 kartus 3, ir taip toliau faktorialas? TiesÄ sakant, faktorinÄ bet skaiÄius gali tik bÅ«ti iÅ¡reikÅ¡tas jei mes natÅ«ra perkÄlimÅ³ tai iÅ¡ amÅ¾inai. Mes galime rÅ«Å¡ies apibendrinti Faktorialaus problema kaip tai n kartÅ³ faktorialas n minus 1. Tai n kartÅ³ iÅ¡ produkto visi numeriai maÅ¾iau nei mane. 

Å i idÄja, Å¡i apibendrinimas problemos, leidÅ¾ia mums rekursyviai apibrÄÅ¾ti faktorialas funkcijÄ. Kai apibrÄÅ¾ti funkcijÄ rekursyviai, ten du dalykai, kurie turi bÅ«ti jos dalimi. Jums reikia turÄti kaÅ¾kÄ vadinama bazinÄ¯ scenarijÅ³, kuris, kai jÅ«s sukelti jÄ, nustos rekursinÄ¯ procesÄ. 

PrieÅ¡ingu atveju, funkcija, kuri ragina itself-- kaip galima imagine-- gali tÄstis amÅ¾inai. Funkcija ragina funkcijÄ vadina funkcija skambuÄius funkcija iÅ¡kvieÄia funkcijÄ. Jei jÅ«s neturite bÅ«das jÄ¯ sustabdyti, savo programÄ bus veiksmingai Ä¯strigo ne begalinis ciklas. Tai bus katastrofos, galÅ³ gale, nes jis bus paleisti iÅ¡ atminties. Bet tai Å¡alia taÅ¡ko. 

Mums reikia turÄti kokÄ¯ nors kitÄ bÅ«dÄ, kaip sustabdyti dalykÅ³ Be mÅ«sÅ³ programos kritimo, nes programa, kuri avarijos yra tikriausiai ne graÅ¾us ar elegantiÅ¡ka. Ir taip mes vadiname tai bazinÄ¯ scenarijÅ³. Tai yra paprastas sprendimas Ä¯ problemÄ, kuri nutraukia grÄ¯Å¾tamojo proceso pasikartojimui. Taigi, kad viena dalis rekursywny funkcija. 

Antroji dalis yra grÄ¯Å¾tamojo atveju. Ir tai yra, kai rekursinio bus iÅ¡ tikrÅ³jÅ³ vyksta. Tai yra, kur funkcija skambinti pati. 

Jis nebus skambinti pati tiksliai tas pats, kaip jis buvo vadinamas. Jis bus Å¡iek tiek variacijos kad daro problemÄ, tai bando iÅ¡sprÄsti smulkutis Å¡iek tiek maÅ¾esnis. Bet tai paprastai praeina spardytis iÅ¡sprÄsti tirpalo urmu Ä¯ kitÄ skambutÄ¯ Å¾emyn linija. 

Kuris iÅ¡ Å¡iÅ³ iÅ¡vaizda kaip bazine Äia? Kuris iÅ¡ Å¡iÅ³ atrodo kaip PaprasÄiausias sprendimas yra problema? Mes turime Factorial krÅ«va, ir galÄtume toliau vyksta on-- 6, 7, 8, 9, 10 ir pan. 

TaÄiau vienas iÅ¡ Å¡iÅ³ iÅ¡vaizda geras pavyzdys bÅ«tÅ³ bazinÄ¯ scenarijÅ³. Tai labai paprastas sprendimas. Neturime nieko ypatingo. 

1 faktorialas yra tik 1. Neturime daryti bet daugyba ne visiems. Atrodo, kad jei mes ketiname pabandyti ir iÅ¡sprÄsti Å¡iÄ problemÄ, ir mes turime sustabdyti Rekursija kaÅ¾kur, mes tikriausiai norite sustabdyti tai kai mes gauti iki 1. Mes nenorime sustoti prieÅ¡ tai. 

Taigi, jei mes apibrÄÅ¾ti MÅ«sÅ³ faktorialas funkcija, Äia uÅ¾ skeletas kaip mes galime tai padaryti. Mums reikia prijungti Å¡iÅ³ dviejÅ³ Quake bazinÄ¯ scenarijÅ³ ir grÄ¯Å¾tamojo atveju. Kas bazinÄ¯ scenarijÅ³? Jei n yra lygus 1, grÄ¯Å¾ti 1-- tai tikrai paprasta problemÄ iÅ¡sprÄsti. 

1 faktorialas yra 1. Tai ne 1 kartÅ³ nieko. Tai tik 1. Tai labai paprasta faktas. Ir taip, kad gali bÅ«ti mÅ«sÅ³ bazinÄ¯ scenarijÅ³. Jei mes gauti iÅ¡laikÄ 1 Ä¯ tai funkcija, mes tiesiog return 1. 

Koks grÄ¯Å¾tamojo atvejis greiÄiausiai atrodys? DÄl visÅ³ kitÅ³ skaiÄiÅ³ Be to 1, koks modelis? Na, jei mes atsiÅ¾velgti iÅ¡ n faktorialas, Tai n kartÅ³ iÅ¡ n faktorialas atÄmus 1. 

Jei mes radote faktorialas 3, tai 3 kartus 3 minus 1 faktorialas, arba 2. Ir todÄl, jei mes ne Å¾iÅ«ri 1, prieÅ¡ingu atveju grÄÅ¾a n kartÅ³ faktorialas n minus 1. Tai gana paprasta. 

Ir dÄl turintys Å¡iek tiek labui Å¡varesnis ir labiau elegantiÅ¡kas kodas, Å¾ino, kad jei mes turime viena linija kilpÅ³ arba vieno linija sÄlyginÄs filialai, galime atsikratyti visas garbanotas petneÅ¡os aplink juos. Taigi, mes galime sujungti tai tai. Tai lygiai tas pats funkcionalumas kaip Å¡is. 

AÅ¡ tiesiog neatimtÅ³ garbanotas petneÅ¡os, nes ten tik viena eilutÄ viduje tÅ³ sÄlyginiÅ³ Å¡akÅ³. Taigi jie elgiasi vienodai. Jei n yra lygus 1, grÄÅ¾inti 1. PrieÅ¡ingu atveju grÄ¯Å¾ti n kartÅ³ iÅ¡ n minus 1 faktorialas. Taigi mes darome problemÄ maÅ¾esnis. Jei n prasideda kaip 5, mes ketiname grÄ¯Å¾ti 5 kartus 4 faktorialas. Ir mes pamatysime per minutÄ, kai mes kalbame apie skambuÄius stack-- kitoje vaizdo kur mes kalbame apie skambinti stack-- mes iÅ¡mokti apie tai, kodÄl bÅ«tent Å¡is procesas veikia. 

TaÄiau, nors faktorialas 5 sako grÄ¯Å¾ti 5 kartus faktorialas 4 ir 4 ketina pasakyti, gerai, gerai, grÄÅ¾inimo 4 kartus 3 faktorialas. Ir, kaip matote, mes RÅ«Å¡iuoti artÄja 1 d. Mes vis arÄiau ir priartinti prie pagrindo atveju. 

Ir kai mes paspauskite pagrindÄ, visi ankstesniÅ³ funkcijÅ³ turi atsakyti jie ieÅ¡ko. FaktorinÄ 2 kalbÄjo grÄÅ¾Ä 2 kartus 1 faktorialas. Na, faktorinÄ iÅ¡ 1 grÄÅ¾a 1 d. Taigi uÅ¾ faktorialas skambutis 2 gali grÄÅ¾inti 2 kartus 1 ir duoti, kad atgal Ä¯ Faktorialas 3, kuri yra laukia, kad rezultatas. 

Ir tada jis gali apskaiÄiuoti jos rezultatas, 3 kartus 2 6, ir duoti jÄ¯ atgal Ä¯ faktorialas 4. Ir vÄl, mes turime Vaizdo skambuÄiÅ³ kamino kur tai yra pavaizduotas Å¡iek tiek daugiau nei tai, kÄ aÅ¡ sakau dabar. Bet tai jis. Vien tai yra, kad sprendimas SkaiÄiuojant skaiÄiaus faktorialas. 

Tai tik keturias eilutes kodo. Tai gana kietas, tiesa? Tai tipo seksualus. 

Taigi, apskritai, bet ne visada, rekursywny funkcija gali pakeisti kilpa ne rekursywny funkcija. Taigi Äia, side by side, yra iteracinis versija Faktorialaus funkcija. Abu Å¡ie SkaiÄiuoti lygiai tas pats dalykas. 

Jie abu apskaiÄiuoti n faktorialas. KairÄje versija naudoja rekursija tai padaryti. DeÅ¡inÄje versija naudoja iteracijos tai padaryti. 

Ir praneÅ¡imas, turime pripaÅ¾inti kintamasis sveikas produktas. Ir tada mes kilpa. Tol, kol n yra didesnis uÅ¾ 0, mes iÅ¡laikyti padauginus n produktÄ ir maÅ¾ÄjanÄio n iki mes galime apskaiÄiuoti produktÄ. Taigi, Å¡ie du funkcijos, vÄl, padaryti lygiai tÄ patÄ¯. TaÄiau jie neturi daryti lygiai taip pat. 

Dabar, tai yra Ä¯manoma, kad turi daugiau nei vienÄ bazÄ atveju arba daugiau nei vienÄ rekursywny atveju, priklausomai nuo kÄ jÅ«sÅ³ funkcija bando daryti. JÅ«s nebÅ«tinai tik " vienÄ bazinÄ¯ scenarijÅ³ arba vieno rekursywny atveju. Taigi AN kaÅ¾kÄ pavyzdys su keliais baziniais atvejais gali bÅ«ti this-- FibonaÄio skaiÄius, seka. 

JÅ«s galite prisiminti iÅ¡ pradiniÅ³ mokyklÅ³ dienÅ³ kad FibonaÄio seka apibrÄÅ¾ta kaip this-- pirmasis elementas yra 0. Antrasis elementas yra 1. Abu jie yra tiesiog pagal apibrÄÅ¾imÄ. 

Tada kiekvienas kitas elementas apibrÄÅ¾iamas kaip n minus 1 ir n minus 2 suma. Taigi treÄiÄjÄ¯ elementÄ BÅ«tÅ³ 0 ir 1 yra 1. Ir tada ketvirtas elementas bÅ«tÅ³ antra elementas, 1, plius treÄiasis elementas, 1. Ir tai bÅ«tÅ³ 2. Ir taip toliau, ir taip toliau. 

Taigi Å¡iuo atveju, mes turime dvi bazines bylas. Jei n yra lygus 1, grÄÅ¾inti 0. Jei n yra lygus 2, grÄÅ¾inti 1. PrieÅ¡ingu atveju, grÄ¯Å¾ti Fibonacci n atÄmus 1 plius FibonaÄio n Â± 2. 

Taigi, kad kelis bazinius atvejus. KÄ apie keliÅ³ rekursyviÅ³ atvejais? Na, kaÅ¾kas vadinamas Collatz spÄjimas. NesiruoÅ¡iu sakyti, jÅ«s Å¾inote, kas tai yra, nes tai tikrai mÅ«sÅ³ galutinis problema Å¡iuo konkreÄiu vaizdo. Ir tai mÅ«sÅ³ pratybos dirbti kartu. 

Taigi Äia kÄ Collatz spÄjimas is-- jis taikomas kiekvienÄ teigiamÄ sveikÄjÄ¯ skaiÄiÅ³. Ir tai spÄja, kad tai visada galima grÄ¯Å¾ti 1, jei atlikite Å¡iuos veiksmus. Jei n yra 1, sustabdyti. Mes turime grÄ¯Å¾ti Ä¯ 1, jei n yra 1. 

PrieÅ¡ingu atveju, eiti per tai procesas vÄl n padalytÄ iÅ¡ 2. Ir pamatyti, jei jÅ«s galite gauti atgal Ä¯ 1. PrieÅ¡ingu atveju, jei n yra nelyginis, eiti per Å¡is procesas vÄl 3N plius 1, arba 3 kartus n plius 1. Taigi Äia mes turime vienÄ bazinÄ¯ scenarijÅ³. Jei n yra lygus 1, sustabdyti. Mes nedarome, bet daugiau rekursija. 

Bet mes turime dvi rekursiniÅ³ atvejus. Jei n yra lygus, mes darome vienÄ rekursinÄ¯ atveju, ragindamas N padalytÄ iÅ¡ 2. Jei n yra nelyginis, mes skirtingi rekursywny byla dÄl 3 times n plius 1 d. 

Ir taip uÅ¾ Å¡Ä¯ video tikslas imtis sekundÄ, pristabdyti vaizdo Ä¯raÅ¡Ä, ir pabandyti ir raÅ¡au tai rekursywny funkcija Collatz kur praeiti vertÄs n ir jis apskaiÄiuoja, kiek Å¾ingsniÅ³ jÄ¯ mano, kad gauti 1, jei jums pradÄti iÅ¡ n ir atlikite Å¡iuos veiksmus iki virÅ¡aus. Jei n yra 1, tai uÅ¾ima 0 Å¾ingsnius. PrieÅ¡ingu atveju, jis ketina iÅ¡gerkite vienÄ Å¾ingsnÄ¯ plius taÄiau daug Å¾ingsniÅ³ jis pasiima arba n padalintas iÅ¡ 2, jei n yra lygus, ar 3n plius 1 jei n yra keista. 

Dabar, aÅ¡ supakuoti ekrane Äia BandiniÅ³ dalykÅ³ uÅ¾ jus pora, testÅ³ atvejais pora jums, norÄdami pamatyti, kÄ Å¡ie Ä¯vairÅ«s COLLATZ numeriai, ir taip pat iliustracija iÅ¡ Å¾ingsniÅ³, kad reikia iÅ¡gyveno todÄl jÅ«s galite rÅ«Å¡iuoti pamatyti Å¡Ä¯ procesÄ veiksmÅ³. Taigi, jei n yra lygus 1, Collatz n yra 0. JÅ«s neturite daryti nieko grÄ¯Å¾ti iki 1. JÅ«s jau esate ten. 

Jei n yra 2, tai uÅ¾ima vienas Å¾ingsnis gauti iki 1. JÅ«s pradedate su 2. Na, 2 yra ne lygus 1. Taigi, tai bus vienas Å¾ingsnis plius TaÄiau daugelis veiksmÅ³, kuriÅ³ ji Ä¯gauna N padalytÄ iÅ¡ 2. 

2, padalytÄ iÅ¡ 2 1. Taigi ji mano vienÄ Å¾ingsnÄ¯ plius taÄiau daug Å¾ingsniÅ³ uÅ¾trunka 1 d. 1 uÅ¾trunka nulÄ¯ veiksmus. 

3, kaip matote, yra nemaÅ¾ai etapus. Nueini iÅ¡ 3. Ir tada jÅ«s einate Ä¯ 10, 5, 16, 8, 4, 2, 1. Tai uÅ¾trunka septyniÅ³ Å¾ingsniÅ³ grÄ¯Å¾ti prie 1 d. Ir, kaip matote, ten pora kitÅ³ bandymÅ³ atvejus Äia iÅ¡bandyti savo programÄ. Taigi dar kartÄ, pristabdyti vaizdo Ä¯raÅ¡Ä. Ir aÅ¡ eisiu Å¡okti atgal dabar kas tikrasis procesas yra Äia kÄ tai hipotezÄ yra. 

Å½r jeigu jÅ«s galite iÅ¡siaiÅ¡kinti Kaip apibrÄÅ¾ti COLLATZ n taip, kad jis skaiÄiuoja, kiek Å¾ingsniai uÅ¾trunka gauti iki 1. Taigi tikiuosi, jÅ«s sustabdytas video o jÅ«s ne tik manÄs laukia kad turÄtumÄte atsakyti Äia. Bet jei jÅ«s esate, gerai, Å tai atsakymas vistiek. 

Taigi Äia galima apibrÄÅ¾imas iÅ¡ Collatz funkcija. MÅ«sÅ³ bazÄ case-- jei n yra lygus 1, mes grÄ¯Å¾ti 0. Ji neatsiÅ¾velgia Ä¯ bet Å¾ingsniÅ³ grÄ¯Å¾ti prie 1 d. 

PrieÅ¡ingu atveju, mes turime du rekursinÄ¯ cases-- vienas net numerius ir vienas keista. Kaip aÅ¡ iÅ¡bandyti net numerius yra patikrinti, ar n mod 2 yra lygus 0. Tai yra, iÅ¡ esmÄs, vÄl, klausia klausimÄ, Jei prisimenate kÄ mod is-- jei aÅ¡ skaldyk N iÅ¡ 2 ten nÄra likusi? Kad bÅ«tÅ³ lyginis skaiÄius. 

Ir todÄl, jei n mod 2 yra lygus 0 yra bandymai yra tai lyginis skaiÄius. Jei taip, aÅ¡ noriu grÄ¯Å¾ti 1, nes tai tikrai atsiÅ¾velgiant vienÄ Å¾ingsnÄ¯ plius COLLATZ dÄl kokia numeris yra pusÄ mane. PrieÅ¡ingu atveju, aÅ¡ noriu grÄ¯Å¾ti 1 plius Collatz 3 times n plius 1. Kad buvo kita rekursywny Å¾ingsnis, kad mes galÄtÅ³ apskaiÄiuoti Collatz-- Å¾ingsniÅ³ skaiÄiÅ³ ji mano, kad grÄ¯Å¾ti 1 suteikiamas numeris. Taigi tikiuosi, Å¡is pavyzdys padovanojo tau truputÄ¯ iÅ¡ rekursyviÅ³ procedÅ«rÅ³ skonÄ¯. TikimÄs, kad jÅ«s manote kodas yra tiek graÅ¾esnÄ jei bus Ä¯gyvendintos elegantiÅ¡kas, grÄ¯Å¾tamojo bÅ«du. Bet net jei ne, rekursija yra tikrai galingas Ä¯rankis vis. Ir taip tai tikrai kaÅ¾kas gauti savo galvÄ aplink, nes jÅ«s galÄsite sukurti pretty cool programas, naudojant rekursija kad prieÅ¡ingu atveju bÅ«tÅ³ sudÄtinga raÅ¡yti jei jÅ«s naudojate kilpos ir iteracijos. AÅ¡ Doug Lloyd. Tai CS50.