[Muzika] 

DOUG Lloyd: Ju ndoshta mendoni se Kodi është përdorur vetëm për të kryer një detyrë. Ju shkruani atë. Ajo bën diçka. Kjo është shumë e shumë ajo. 

Ju përpiloni atë. Ju drejtuar programin. Ju jeni të mirë për të shkuar. 

Por besoni apo jo, nëse ju kodit për një kohë të gjatë, ju në fakt mund të vijnë për të parë Kodi si diçka që është e bukur. Kjo zgjidh një problem në një mënyrë shumë interesante, apo ka vetëm diçka të vërtetë i zoti në lidhje me mënyrën se si duket. Ju mund të jetë duke qeshur në mua, por është e vërtetë. Dhe Recursion është një mënyrë për të lloj të merrni këtë ide e bukur, elegante-looking kod. Ajo zgjidh problemet në mënyra që janë interesante, të lehtë për të kujtoj, dhe çuditërisht të shkurtër. 

Punimet mënyrë recursion është, një funksion gjithkund rekursive është përcaktuar si një funksion që e quan vetë si pjesë e ekzekutimin e tij. Kjo mund të duket pak e çuditshme, dhe ne do të shohim pak se si kjo punon në një moment. Por përsëri, këto Procedurat janë gjithkund rekursive do të jetë aq elegante sepse ata do për të zgjidhur këtë problem pa që të gjitha këto funksione të tjera ose këto sythe të gjata. Ju do të shihni se këto rekursive Procedurat do të duken aq të shkurtër. Dhe ata me të vërtetë janë duke shkuar për të bërë Kodi tuaj duken shumë më të bukur. 

Unë do të ju jap një shembull e kjo për të parë se si një procedurë rekursive mund të përcaktohet. Pra, nëse ju jeni të njohur me këtë nga klasa matematikë shumë vite më parë, Ka diçka të quajtur funksionin faktorial, e cila është zakonisht shënohet si një pikë thirrje, e cila është përcaktuar mbi të gjitha integers pozitiv. Dhe mënyra se n faktorial llogaritet po ju shumohen gjithë numrat më pak se ose e barabartë me together-- n të gjitha integers më pak se ose e barabartë me n bashku. 

Pra 5 faktorial është 5 herë 4 herë 3 herë 2 herë 1. Dhe 4 faktorial është 4 herë 3 herë 2 herë 1 dhe kështu me radhë. Ju merrni ide. 

Si programuesit, ne nuk e bëjmë përdorin N, pikë thirrje. Pra, ne do të definojnë faktorial funksionojnë si fakt i n. Dhe ne do të përdorim faktorial për të krijuar një zgjidhje rekursive për një problem. Dhe unë mendoj se ju mund të gjeni se kjo është një shumë më me sy tërheqës se përsëritës version i kësaj, që ne gjithashtu do të marrë një sy në në një moment. 

Pra, këtu janë disa pun facts-- intended-- për factorial-- funksioni faktorial. Faktorial i 1, siç thashë, është 1. Faktorial i 2 është 2 herë 1. Faktorial i 3 është 3 herë 2 herë 1, dhe kështu me radhë. Ne biseduam në lidhje me 4 dhe 5 tashmë. 

Por duke kërkuar në këtë, nuk është kjo e vërtetë? A nuk faktorial i 2 vetëm 2 herë faktoriale e 1? Unë do të thotë, faktorial i 1 është 1. Pra, pse nuk mund të them vetëm se, pasi faktorial i 2 është 2 herë 1, kjo është me të vërtetë vetëm 2 herë faktorial i 1? 

Dhe pastaj zgjeruar këtë ide, nuk është faktorial i 3 vetëm 3 herë faktoriale e 2? Dhe faktorial i 4 është 4 herë faktorial i 3, dhe kështu me radhë? Në fakt, faktorial e çdo numër mund vetëm të shprehet nëse ne lloj e kryer këtë përgjithmonë. Ne mund të lloj të përgjithësoj problemi faktorial pasi ajo është n herë e faktorial i n minus 1. Është n herë produkt i të gjithë numrat më pak se unë. 

Kjo ide, kjo përgjithësimi i problemit, na lejon të Recursively përcaktojë funksionin faktorial. Kur ju përcaktoni një funksion Recursively, ka dy gjëra që duhet të jetë një pjesë e saj. Ju duhet të keni diçka që quhet një rasti bazë, e cila, kur ju shkaktojnë atë, do të ndalojë procesin gjithkund rekursive. 

Përndryshe, një funksion që e quan vetvetiu më si ju mund të imagine-- mund të vazhdojë përgjithmonë. Funksioni i quan funksionin thërret thirrjet funksion funksioni quan funksionin. Nëse ju nuk keni një mënyrë për ta ndaluar atë, programin tuaj do të mbërthyer në mënyrë efektive në një lak të pafund. Ajo do të rrëzimit përfundimisht, për shkak se ajo do të dalë jashtë kujtesës. Por kjo është jashtë diskutimit. 

Ne duhet të kemi disa rrugë të tjera për të ndaluar gjëra përveç crashing tonë të programit, sepse një program që punon është i ndoshta jo i bukur apo elegante. Dhe kështu që ne e quajmë këtë rast bazë. Kjo është një zgjidhje e thjeshtë një problem i cili ndalon procesi rekursive nga ndodhin. Pra, kjo është një pjesë e një funksion gjithkund rekursive. 

Pjesa e dytë është rasti rekursive. Dhe ky është vendi ku recursion në fakt do të zhvillohet. Ky është vendi ku Funksioni do të thërrasë vetë. 

Kjo nuk do të thërrasë veten pikërisht në në të njëjtën mënyrë ajo u quajt. Ajo do të jetë një ndryshim të vogël që e bën problemin kjo është duke u përpjekur për të zgjidhur pak vockël i vogël. Por ajo në përgjithësi kalon dollar e zgjidhjes pjesa më e madhe e zgjidhjes në një telefonatë tjetër poshtë vijës. 

Cila nga këto duket si rastin bazë këtu? Cili prej këtyre duket si Zgjidhja më e thjeshtë për një problem? Ne kemi një bandë e factorials, dhe ne mund të vazhdojë do on-- 6, 7, 8, 9, 10, dhe kështu me radhë. 

Por një prej këtyre duket si një rast i mirë që të jetë rasti bazë. Kjo është një zgjidhje shumë e thjeshtë. Ne nuk duhet të bëjmë ndonjë gjë të veçantë. 

Faktorial i 1 është vetëm 1. Ne nuk duhet të bëjmë ndonjë shumëzimin në të gjitha. Duket si në qoftë se ne jemi duke shkuar për të provoni dhe zgjidhur këtë problem, dhe ne kemi nevojë për të ndaluar Recursion diku, ne ndoshta dëshironi të ndaluar ajo kur ne të merrni për 1. Ne nuk duam të ndalet para se. 

Pra, nëse ne jemi duke përcaktuar Funksioni ynë faktorial, këtu është një skelet për se si ne mund të bëjmë atë. Ne duhet të plug në ato dy things-- rasti bazë dhe rasti rekursive. Çfarë është rasti bazë? Nëse n është e barabartë me 1, që është kthyer 1-- një problem të vërtetë të thjeshtë për të zgjidhur. 

Faktorial i 1 është 1. Kjo nuk është 1 herë çdo gjë. Është vetëm 1. Është një fakt shumë e lehtë. Dhe kështu që mund të jetë rasti ynë bazë. Në qoftë se ne të merrni kaluar 1 në këtë funksion, ne do të kthehen vetëm 1. 

Çfarë është gjithkund rekursive Rasti ndoshta duken si? Për çdo numër tjetër përveç 1, çfarë është model? E pra, në qoftë se ne jemi duke marrë faktorial i N, ajo është herë n faktorial i n minus 1. 

Nëse ne jemi duke marrë faktorial i 3, kjo është 3 herë faktorial i 3 minus 1, ose 2. Dhe kështu që në qoftë se ne nuk jemi duke kërkuar në 1, ndryshe Kthimi n herë e faktorial i n minus 1. Është shumë i thjeshtë. 

Dhe për hir të pasurit pak pastër dhe kodin më elegante, e di se në qoftë se ne kemi sythe vetme-line apo vetme-line degët kushtëzuara, ne mund të shpëtoj nga të gjitha të formatimin e teksteve kaçurrel rreth tyre. Pra, ne mund të konsoliduar këtë për këtë. Kjo ka të njëjtë Funksionalitetin si kjo. 

Unë jam vetëm duke larguar kaçurrel formatimin e teksteve, sepse ka vetëm një linjë brenda këtyre degëve të kushtëzuara. Pra, këto sillen njëlloj. Nëse n është e barabartë me 1, kthehen 1. Përndryshe kthehen herë n faktorial i n minus 1. Pra, ne jemi duke e bërë problem më i vogël. Nëse n fillon si 5, ne jemi duke shkuar për kthimin 5 herë faktoriale e 4. Dhe ne do të shohim në një minutë kur flasim rreth stack-- thirrjes në një tjetër video ku ne flasim për quajmë stack-- ne do të mësoni se pse pikërisht ky proces funksionon. 

Por, ndërsa faktorial i 5 thotë kthehen 5 herë faktorial i 4, dhe 4 do të thotë, OK, mirë, kthimi 4 herë faktoriale e 3. Dhe si ju mund të shihni, ne jemi lloj i afrohet 1. Ne jemi duke iu afruar dhe më afër me atë rastin bazë. 

Dhe një herë ne goditi rastin bazë, të gjithë nga funksionet e mëparshme kanë përgjigjen ata po kërkoni. Faktorial i 2 thoshte kthim 2 herë faktoriale e 1. E pra, faktorial e 1 kthimit 1. Pra, thirrja për faktorial e 2 mund të kthehen 2 herë 1, dhe jap atë përsëri në faktorial të 3, e cila është duke pritur për atë rezultat. 

Dhe atëherë ajo mund të llogarisë rezultat e tij, 3 herë 2 është 6, dhe të japë atë përsëri në faktoriale e 4. Dhe përsëri, ne kemi një Video në thirrje rafte ku kjo është e ilustruar pak më shumë se ajo që unë jam duke thënë se të drejtë tani. Por kjo është ajo. Kjo vetëm është zgjidhje për llogaritjen e faktorial e një numri. 

Është vetëm katër rreshta të kodit. Kjo është pretty cool, e drejtë? Kjo është lloj i sexy. 

Pra në përgjithësi, por jo gjithmonë, një funksion gjithkund rekursive mund të zëvendësojë një lak në një jo-funksion gjithkund rekursive. Kështu që këtu, krah për krah, është përsëritës Versioni i funksionit faktorial. Të dyja këto Llogarit saktësisht e njëjta gjë. 

Ata të dy llogaritur faktoriale e n. Versioni në të majtë përdor recursion për të bërë atë. Versioni në të djathtë përdor përsëritje për të bërë atë. 

Dhe vini re, ne duhet të deklarojnë një variabël një produkt numër të plotë. Dhe pastaj ne lak. Aq sa n është më i madh se 0, ne mbajtur shumëzuar se produkti me n dhe decrementing n deri ne llogarisim produktin. Pra, këto dy funksione, përsëri, bëjnë pikërisht të njëjtën gjë. Por ata nuk e bëjmë atë në saktësisht në të njëjtën mënyrë. 

Tani, është e mundur të kanë më shumë se një bazë rast ose me teper se nje rast gjithkund rekursive, në varësi në çfarë funksioni juaj është duke u përpjekur për të bërë. Ju nuk janë domosdo të kufizuara vetëm për të një rast i vetëm bazë ose një rekursive vetme rast. Pra, një shembull i diçkaje me raste të shumta bazë mund të jetë this-- Fibonacci rend numër. 

Ju mund të kujtojnë nga ditë shkolle fillore se Fibonacci sequence është përcaktuar si this-- elementi i parë është 0. Elementi i dytë është 1. Të dyja këto janë vetëm sipas definicionit. 

Atëherë çdo element tjetër është përcaktuar si shuma n minus 1 dhe n minus 2. Pra, elementi i tretë do të jetë 0 plus 1 është 1. Dhe pastaj elementi i katërt do të jetë elementi i dytë, 1, plus elementi i tretë, 1. Dhe kjo do të jetë 2. Dhe kështu me radhë e kështu me radhë. 

Pra, në këtë rast, ne kemi dy raste bazë. Nëse n është e barabartë me 1, kthehen 0. Nëse n është e barabartë me 2, kthehen 1. Përndryshe, kthimin Fibonacci të n minus 1 plus Fibonacci i n minus 2. 

Pra, kjo është raste të shumta bazë. Po në lidhje me raste të shumta gjithkund rekursive? E pra, ka diçka quajtur hamendje Collatz. Unë nuk jam duke shkuar për të thënë, ju e dini se çka është, sepse kjo është në fakt finale ynë Problemi për këtë video të veçantë. Dhe kjo është ushtrim ynë për të punuar së bashku. 

Kështu që këtu është ajo që Collatz hamendje is-- kjo vlen për çdo numër i plotë pozitiv. Dhe kjo spekulon se kjo është gjithmonë e mundur për të marrë përsëri për 1 nëse ju do të ndiqni këto hapa. Nëse n është 1, të ndaluar. Ne kemi marrë përsëri në 1 nëse n është 1. 

Përndryshe, kalojnë nëpër këtë Procesi përsëri në n ndarë nga 2. Dhe shihni nëse ju mund të merrni përsëri në 1. Përndryshe, nëse n është i rastësishëm, të shkojnë nëpër ky proces përsëri në 3N plus 1, ose 3 herë n plus 1. Pra, këtu ne kemi një rast të vetëm bazë. Nëse n është e barabartë me 1, të ndaluar. Ne nuk jemi duke bërë ndonjë recursion më shumë. 

Por ne kemi dy raste gjithkund rekursive. Nëse n është edhe më, ne bëjmë një rekursive rast, duke e quajtur n ndarë nga 2. Nëse n është i rastësishëm, ne bëjmë një tjetër Rasti rekursive mbi 3 herë n plus 1. 

Dhe kështu qëllimi për këtë video është për të marrë një të dytë, pauzë video, dhe të përpiqen dhe të shkruaj kjo funksioni rekursiv Collatz ku ju të kalojë në një n vlerës, dhe ajo llogarit sa hapa ajo merr për të marrë me 1 nëse ju filloni nga n dhe ju do të ndiqni këto hapa lart. Nëse n është 1, merr 0 hapa. Përndryshe, ajo do të marrë një hap plus megjithatë shumë hapa ajo merr në të dyja n ndarë nga 2, nëse n është edhe më, ose 3N plus 1 nëse n është i rastësishëm. 

Tani, unë e kam vënë në ekran këtu disa gjëra test për ju, një çift i testeve rasteve për ju, për të parë çfarë këto shifra të ndryshme Collatz janë, dhe gjithashtu një ilustrim nga hapat që duhet të jetë zhdukur nëpër kështu që ju mund lloj e shohin këtë proces në veprim. Kështu që nëse n është e barabartë me 1, Collatz prej n eshte 0. Ju nuk keni për të bërë çdo gjë për të marrë përsëri në 1. Ju jeni tashmë atje. 

Nëse n është 2, merr një hap për të marrë në 1. Ju filloni me 2. Dhe, 2 nuk është e barabartë me 1. Pra, kjo do të jetë një hap plus megjithatë shumë hapat që merr n ndarë nga 2. 

2 ndarë nga 2 është 1. Pra, ajo merr një hap plus megjithatë shumë hapa ajo merr për 1. 1 merr zero hapa. 

Për 3, siç mund ta shihni, nuk ka mjaft disa hapa të përfshirë. Ju shkoni nga 3. Dhe pastaj ju shkoni në 10, 5, 16, 8, 4, 2, 1. Ajo merr shtatë hapa për të marrë përsëri në 1. Dhe si ju mund të shihni, ka një çift ​​raste të tjera provë këtu për të provuar programin tuaj. Pra, përsëri, pauzë video. Dhe unë do të shkoj hidhen përsëri tani për çfarë procesi aktual është këtu, ajo që kjo hamendje është. 

Shih nëse ju mund të kuptoj se si për të përcaktuar Collatz të n në mënyrë që ajo llogarit se sa shumë hapa që duhet për të marrë në 1. Kështu që shpresojmë se, ju keni ndaluar video dhe ju nuk jeni vetëm duke pritur për mua për të ju jap përgjigje këtu. Por nëse ju jeni, mirë, këtu është përgjigje gjithsesi. 

Kështu që këtu është një përkufizim i mundshëm e funksionit Collatz. Baza jonë case-- nëse n është barabarte me 1, ne kthim 0. Ajo nuk ka marrë ndonjë hapa për të marrë përsëri në 1. 

Përndryshe, ne kemi dy cases-- gjithkund rekursive një për edhe numrat dhe një për rastësishëm. Mënyrën se si unë testuar edhe për numrat është për të kontrolluar nëse n mod 2 është e barabartë me 0. Kjo është në thelb, përsëri, duke i kërkuar pyetjen, në qoftë se ju kujtohet is-- çfarë mod nëse unë ndani n nga 2 është atje ka mbetur? Kjo do të jetë një numër çift. 

Dhe kështu që nëse n mod 2 është e barabartë me 0 është Testimi është ky një numër edhe më. Nëse është kështu, unë dua të kthehen 1, sepse kjo është padyshim duke marrë një hap plus Collatz e çfarëdo numri është gjysma e mua. Përndryshe, unë dua të kthehen 1 plus Collatz e 3 herë n plus 1. Kjo ishte tjetri hap rekursive që ne mund të marrë për të llogaritur Collatz-- numrin e hapave ajo merr për të marrë përsëri për 1 jepet një numër. Kështu që shpresojmë se, ky shembull ju dha pak e një shije të procedurave gjithkund rekursive. Shpresojmë, ju mendoni se është një kod pak më të bukur në qoftë se zbatohet në një mënyrë elegante, gjithkund rekursive. Por edhe në qoftë se nuk, recursion është një mjet të vërtetë i fuqishëm megjithatë. Dhe kështu kjo është patjetër diçka për të marrë kokën tuaj rreth, sepse ju do të jetë në gjendje të krijojë Programet pretty cool përdorur recursion që përndryshe mund të jetë i ndërlikuar për të shkruar në qoftë se ju jeni duke përdorur sythe dhe përsëritje. Unë jam Doug Lloyd. Kjo është CS50.