[Daqq tal-mużika] 

Doug LLOYD: You probabbilment jaħsbu li kodiċi hija biss użati biex iwettaq ħidma. Inti tikteb out. Hija ma xi ħaġa. Li pretty ħafna dan. 

Inti josservawha. Inti tmexxi l-programm. Int tajba biex tmur. 

Iżda jemmnu jew le, jekk inti kodiċi għal żmien twil, inti fil-fatt tista 'tigi biex tara kodiċi bħala xi ħaġa li l-beautiful. Jsolvi problema fil mod interessanti ħafna, jew hemm biss xi ħaġa verament pulita dwar il-mod jidher. Inti jista 'jkun laughing fil lili, imma huwa veru. U recursion huwa mod wieħed li tip ta tinkiseb din l-idea ta 'sbieħ, kodiċi eleganti li tħares. Jsolvi problemi b'modi li huma interessanti, faċli biex wieħed jivviżwalizza, u sorprendentement qasir. 

Ix-xogħlijiet mod recursion huwa, funzjoni jirrikorri hija definita bħala funzjoni li s-sejħiet ruħha bħala parti mill-eżekuzzjoni tiegħu. Li jista 'jidher ftit stramba, u aħna ser tara ftit dwar kif taħdem din fil-mument. Iżda għal darb'oħra, dawn proċeduri rikursivi huma se jkun hekk eleganti għaliex dawn qed tmur biex issolvi din il-problema mingħajr dawn kollha li jkollhom funzjonijiet oħra jew dawn loops twal. Int ser ikollok tara li dawn rikursivi proċeduri huma ser tfittex tant qasir. U huma verament huma ser jagħmlu kodiċi tiegħek ħarsa ħafna aktar sbieħ. 

I ser jagħtuk eżempju ta 'dan biex tara kif jista 'jiġi definit proċedura rikursivi. Mela jekk int familjari ma 'dan mill-klassi matematika ħafna snin ilu, Hemm xi ħaġa imsejjaħ il- funzjoni fatturi, li normalment murija bħala punt exclamation, li hija definita fuq interi pożittivi. U l-mod li n fattorjali hija kkalkulata huwa inti immoltiplika kollha in-numri ta 'inqas minn jew ugwali għal n together-- l-interi inqas minn jew ugwali għal n flimkien. 

Allura 5 fattorjali hija 5 darbiet 4 darbiet 3 darbiet 2 darbiet 1. U 4 fattorjali huwa 4 darbiet 3 darbiet 2 darbiet 1 u l-bqija. Ikollok l-idea. 

Kif programmaturi, aħna ma użu n, punt exclamation. Allura aħna ser jiddefinixxu l-fattorjali funzjoni bħala fatt ta 'n. U aħna ser tuża fattorjali biex joħolqu soluzzjoni rikursivi għal problema. U naħseb li inti tista 'ssib li huwa ħafna aktar viżwalment attraenti mill-iterattiv verżjoni ta 'dan, li aħna ser wkoll tagħti ħarsa lejn fil-mument. 

Allura hawnhekk huma koppja ta pun facts-- intended-- dwar factorial-- l funzjoni fattorjali. Il fattorjali ta '1, kif għidt, huwa 1. Il fattorjali ta '2 huwa ta' 2 darbiet 1. Il fattorjali ta '3 huwa 3 ħinijiet 2 darbiet 1, u l-bqija. Aħna tkellimna dwar 4 u 5 diġà. 

Iżda tħares lejn dan, mhuwiex dan veru? Mhuwiex fattorjali tat-2 biss 2 darbiet il fattorjali ta 1? I mean, il fattorjali ta '1 hija l-1. Allura għaliex ma nistgħu biss jgħidu li, peress fattorjali ta '2 huwa 2 darbiet 1, huwa verament biss 2 darbiet l fattorjali ta 1? 

U mbagħad testendi dik l-idea, mhuwiex il-fattorjali ta 3 biss 3 darbiet il-fattorjali tat-2? U l-fattorjali ta '4 huwa 4 darbiet l fattorjali ta '3, u l-bqija? Fil-fatt, il-fattorjali ta 'kwalunkwe numru tista' sempliċement ikunu espressi jekk aħna xorta ta 'isir dan ix dejjem. Nistgħu tip ta 'jiġġeneralizza il-problema fattorjali kif huwa n drabi l- fattorjali ta 'n minus 1. Huwa n darbiet il-prodott ta ' il-numri inqas minn lili. 

Din l-idea, dan ġeneralizzazzjoni tal-problema, jippermetti li recursively jiddefinixxu l-funzjoni fattorjali. Meta inti tiddefinixxi funzjoni recursively, hemm żewġ affarijiet li jeħtieġ li tkun parti ta 'dan. Ikollok bżonn li jkollhom xi ħaġa imsejħa każ ta 'bażi, li, meta inti jikkawżaw dan, se iwaqqaf il-proċess rikursivi. 

Inkella, funzjoni li titlob itself-- kif inti tista imagine-- tista 'tmur fuq għal dejjem. Funzjoni jitlob il-funzjoni jitlob is-sejħiet funzjoni il-funzjoni jitlob l-funzjoni. Jekk inti ma jkollhom mod biex jitwaqqaf, program tiegħek ser tiġi mwaħħla b'mod effettiv fi loop infinita. Hija se tiġrifa eventwalment, għaliex dan ser jispiċċaw ta 'memorja. Iżda li ħdejn il-punt. 

Għandna bżonn li jkollhom xi mod ieħor biex tieqaf affarijiet minbarra jiġġarrfu programm tagħna, minħabba li programm li ġġarrfu hija probabbilment mhux sbieħ jew eleganti. U hekk aħna sejħa dan il-każ bażi. Din hija soluzzjoni sempliċi għal problema li jieqaf il-proċess rikursivi milli sseħħ. B'tali mod li parti waħda mill funzjoni jirrikorri. 

It-tieni parti huwa l-każ rikursivi. U dan huwa fejn l-recursion attwalment isseħħ. Dan huwa fejn l- funzjoni se sejħa nnifisha. 

Dan mhux se sejħa ruħha eżattament bl-istess mod ma kienet mitluba. Huwa ser jiġi varjazzjoni żgħira li jagħmel il-problema huwa jippruvaw isolvu xi ftit teeny iżgħar. Iżda huwa ġeneralment jgħaddi l-Buck li ssolvi l-massa tas-soluzzjoni għal sejħa differenti matul il-linja. 

Liema minn dawn jistenna bħall-każ bażi hawnhekk? Liema wieħed minn dawn jistenna bħall- eħfef soluzzjoni għal problema? Għandna mazz ta 'factorials, u nistgħu tkompli jmorru on-- 6, 7, 8, 9, 10, u l-bqija. 

Iżda wieħed minn dawn qisu każ tajjeb li jkun il-każ bażi. Huwa soluzzjoni sempliċi ħafna. Aħna ma jkollhom jagħmlu xi ħaġa speċjali. 

Il fattorjali ta '1 huwa biss 1. Aħna ma jkollhom jagħmlu xi multiplikazzjoni fil-livelli kollha. Jidher simili jekk aħna qed tmur li tipprova ssolvi din il-problema, u għandna bżonn li tieqaf il- recursion x'imkien, aħna probabbilment tixtieq li twaqqaf meta nikbru għal 1. Aħna ma rridux li tieqaf qabel dik. 

Allura jekk aħna qed tiddefinixxi funzjoni fattorjali tagħna, Heres iskeletru għall kif nistgħu nagħmlu dan. Għandna bżonn biex timla f'dawn iż-żewġ things-- il-każ bażi u l-każ rikursivi. X'hemm-każ bażi? Jekk n huwa ugwali għal 1, jirritorna 1-- li l- problema verament sempliċi biex isolvu. 

Il fattorjali ta '1 hija l-1. Mhuwiex 1 ħinijiet xejn. Huwa biss 1. Huwa fatt faċli ħafna. U hekk li jistgħu jiġu każ bażi tagħna. Jekk nikbru għadda 1 fis dan funzjoni, aħna ser biss jirritorna 1. 

X'hemm-rikursivi każ probabbilment look like? Għal kull numru ieħor minbarra 1, x'inhu l-mudell? Ukoll, jekk aħna qed tieħu l fattorjali ta 'n- Huwa drabi n l fattorjali ta n minus 1. 

Jekk aħna qed tieħu l fattorjali ta '3, huwa 3 darbiet il-fattorjali ta 3 minus 1, jew 2.. U hekk jekk aħna mhux qed tħares lejn 1, inkella ritorn n drabi l- fattorjali ta 'n minus 1. Huwa pjuttost sempliċi. 

U għall-finijiet ta 'wara ftit aktar nodfa u l-kodiċi aktar eleganti, jafu li jekk ikollna linji tal-linja waħda jew linja waħda fergħat kondizzjonali, nistgħu jeħles kollha ta 'l- braces kaboċċi madwarhom. Allura nistgħu jikkonsolida dan għal dan. Dan għandu eżattament l-istess funzjonalità kif dan. 

Jien biss tieħu l bogħod l-kaboċċi ċingi, għaliex hemm biss linja waħda ġewwa dawk il-fergħat kondizzjonali. Allura dawn jaġixxu b'mod identiku. Jekk n huwa ugwali għal 1, jirritornaw 1. Inkella ritorn drabi n l fattorjali ta 'n minus 1. Allura aħna qed jagħmlu l-problema iżgħar. Jekk n tibda bħala 5, aħna qed tmur biex ritorn 5 darbiet il-fattorjali ta '4. U aħna ser tara fil-minuta meta nitkellmu dwar il stack-- sejħa bil-vidjo ieħor fejn nitkellmu dwar il- sejħa stack-- aħna ser jitgħallmu dwar għaliex eżattament dan il-proċess tax-xogħlijiet. 

Iżda filwaqt li fattorjali tal-5 jgħid ritorn 5 darbiet fattorjali ta '4, u 4 se ngħid, OK, ukoll, ritorn 4 darbiet l fattorjali ta 3. U kif tista 'tara, aħna qed tip ta 'toqrob 1. Aħna jkollna eqreb u eqreb lejn dak każ bażi. 

U ladarba aħna laqat il-każ bażi, il-funzjonijiet kollha ta 'qabel l-risposta li kienu qed ifittxu. Fattorjali ta '2 kien qal ritorn 2 darbiet il fattorjali ta 1. Ukoll, fattorjali ta '1 prospetti 1. Allura l-sejħa għall-fattorjali tat-2 tista 'ritorn 2 darbiet 1, u tagħti lil dak lura lill fattorjali ta 3, li qed jistenna dan ir-riżultat. 

U allura tista 'tikkalkula riżultat tagħha, 3 darbiet 2 huwa 6, u jagħtu lura lill fattorjali ta '4. U għal darb'oħra, aħna għandna video fuq il-munzell sejħa fejn dan jidher ftit aktar minn dak li jien tgħid dritt issa. Iżda dan huwa minnu. Dan waħdu huwa s-soluzzjoni għall kalkolu tal-fattorjali ta 'numru. 

Huwa biss erba 'linji ta' kodiċi. Li pretty jibred, right? Huwa tip ta 'sexy. 

Allura b'mod ġenerali, iżda mhux dejjem, funzjoni jirrikorri tista 'tissostitwixxi loop fil- funzjoni mhux jirrikorri. Allura hawnhekk, ġenb ma 'ġenb, huwa l-iterattiv Verżjoni tal-funzjoni fattorjali. Kemm minn dawn Ikkalkula eżattament l-istess ħaġa. 

Huma t-tnejn tikkalkula l-fattorjali ta 'n. Il-verżjoni fuq ix-xellug użi recursion li tagħmel dan. Il-verżjoni fuq il-lemin użi iterazzjoni biex tagħmel dan. 

U avviż, għandna biex jiddikjaraw a prodott sħiħ varjabbli. U allura aħna loop. Sakemm n hija akbar minn 0, aħna iżommu multiplikazzjoni dak il-prodott mill n u decrementing n sakemm aħna jikkalkulaw il-prodott. Allura dawn iż-żewġ funzjonijiet, għal darb'oħra, jagħmlu eżattament l-istess ħaġa. Iżda dawn ma tagħmel dan fil eżattament bl-istess mod. 

Issa, huwa possibbli li jkollhom il-bażi aktar minn wieħed każ jew iżjed minn wieħed każ rikursivi, jiddependi fuq liema funzjoni tiegħek qed tipprova tagħmel. Inti mhux neċessarjament limitati biss għall każ bażi waħda jew jirrikorri waħda każ. Allura eżempju ta 'xi ħaġa każijiet bażi multipli jista 'jkun this-- l Sekwenza numru Fibonacci. 

Inti tista 'tfakkar minn ġranet tal-iskola elementari li s-sekwenza Fibonacci huwa definit bħall this---ewwel element huwa ta '0. It-tieni element huwa 1. Kemm minn dawn huma biss skond id-definizzjoni. 

Imbagħad kull element ieħor huwa definit bħala s-somma ta 'n minus 1 u n tnaqqis ta' 2. Allura l-tielet element Ikun 0 plus 1 huwa 1. U allura l-raba element tkun it-tieni element, 1, flimkien mal-tielet element, 1. U li jkun 2. U hekk u hekk. 

Allura f'dan il-każ, għandna żewġ każijiet bażi. Jekk n huwa ugwali għal 1, jirritornaw 0. Jekk n huwa ugwali għal 2, ritorn 1. Inkella, ritorn Fibonacci ta n minus 1 plus Fibonacci ta n tnaqqis ta '2. 

Allura dak każijiet bażi multipli. What about każijiet rikursivi multipli? Ukoll, hemm xi ħaġa imsejjaħ il-konġettura Collatz. Jien mhux se ngħid, inti taf liema, jiġifieri, għaliex huwa attwalment finali tagħna problema għal dan il-video partikolari. U huwa eżerċizzju tagħna biex jaħdmu fuq flimkien. 

Allura hawnhekk huwa dak l- Collatz konġettura is-- dan japplika għal kull numru sħiħ pożittiv. U speculates li huwa dejjem possibbli li terġa 'lura għal 1 jekk inti ssegwi dawn il-passi. Jekk n huwa 1, stop. Imxejna marret lura għal 1 jekk n hija l-1. 

Inkella, jgħaddu din proċess mill-ġdid fuq n diviż bi 2. U ara jekk inti tista 'tikseb lura għal 1. Inkella, jekk n hu fard, jgħaddu dan il-proċess mill-ġdid fuq 3n flimkien ma '1, jew 3 darbiet n plus 1. Allura hawnhekk għandna każ bażi waħdanija. Jekk n huwa ugwali għal 1, stop. Aħna ma tagħmel kwalunkwe recursion aktar. 

Iżda għandna żewġ każijiet jirrikorri. Jekk n huwa saħansitra, nagħmlu rikursivi wieħed każ, li ssejjaħ n diviż bl 2. Jekk n hu fard, nagħmlu differenti każ rikursivi fuq 3 darbiet n flimkien 1. 

U għalhekk l-għan ta 'dan il-video huwa li tieħu t-tieni, nieqaf-video, u jippruvaw u tikteb din funzjoni jirrikorri Collatz fejn inti tgħaddi f'valur n, u huwa jikkalkula kemm passi li tieħu biex tikseb għal 1 jekk tibda minn n u inti ssegwi dawn il-passi up hawn fuq. Jekk n huwa 1, li tieħu 0 passi. Inkella, li għaddej biex tieħu pass wieħed plus madankollu ħafna passi meħuda fuq kull n diviż bl 2 jekk n hija saħansitra, jew 3n flimkien ma '1 jekk n hu fard. 

Issa, stajt jitqiegħdu fuq l-iskrin hawn ftit testijiet affarijiet għalik, ftit każijiet testijiet għalik, biex tara dak dawn in-numri Collatz varji huma, u wkoll illustrazzjoni mill-passi li jeħtieġ li tkun marret permezz sabiex inti tista ' tip ta 'tara dan il-proċess fl-azzjoni. Mela jekk n hija ugwali għal 1, Collatz ta n huwa ta '0. Inti ma għandekx tagħmel xejn biex terġa 'lura għal 1. Inti diġà hemmhekk. 

Jekk n huwa 2, li tieħu pass wieħed biex jinkiseb l-1. Inti tibda bil 2. Ukoll, 2 mhuwiex ugwali għal 1. Allura li għaddej biex tkun pass plus madankollu ħafna passi li jieħu n diviż bi 2. 

2 diviża bi 2 huwa 1. Sabiex tieħu pass wieħed plus madankollu ħafna passi li jieħu għall-1. 1 jieħu passi żero. 

Għal 3, kif tistgħu taraw, hemm pjuttost ftit passi involuti. Inti tmur minn 3. U allura inti tmur 10, 5, 16, 8, 4, 2, 1. Huwa jieħu passi seba biex terġa 'lura għal 1. U kif tistgħu taraw, hemm koppja każijiet ta 'eżaminazzjoni oħra hawn biex tiġi ttestjata l-programm tiegħek. Għalhekk għal darb'oħra, nieqaf-video. U jien ser imorru jaqbżu lura issa li dak l-proċess attwali hija hawnhekk, dak li dan konġettura hu. 

Ara jekk inti tista 'figura kif għandu jkun definit Collatz ta n b'tali mod li jikkalkula kemm passi li hemm bżonn sabiex għal 1. Allura nisperaw, inti waqfa qasira tal-video u inti mhux biss stennija g ˙ alija li jtik l-risposta hawn. Imma jekk inti, tajjeb, hawn l-risposta xorta waħda. 

Allura hawnhekk definizzjoni possibbli tal-funzjoni Collatz. Bażi tagħna case-- jekk n hija ugwali għal 1, nerġgħu lura 0. Hija ma tieħu kwalunkwe passi biex terġa 'lura għal 1. 

Inkella, għandna żewġ cases-- rikursivi wieħed anke jekk għal numri u wieħed għall fard. Il-mod test I biex ikunu saħansitra numri huwa li jiċċekkja jekk n mod 2 ikun egwali għal 0. Dan huwa bażikament, għal darb'oħra, tistaqsi l-mistoqsija, jekk inti recall is-- dak mod jekk I iddividi n b'2 m'hemmx bqija? Dan ikun numru biż. 

U hekk jekk n mod 2 huwa daqs 0 hija ittestjar huwa dan anke numru. Jekk iva, I jridu jirritornaw 1, għaliex dan huwa definittivament tieħu pass wieħed plus Collatz ta tkun xi numru huwa nofs ta 'lili. Inkella, I jridu jirritornaw 1 flimkien Collatz ta '3 darbiet n plus 1. Dan kien l-ieħor pass rikursivi li aħna tista 'tieħu biex jiġi kkalkulat l- Collatz---numru ta 'passi li tieħu sabiex tikseb lura għal 1 mogħtija numru. Hekk nisperaw, dan l-eżempju ħadt ftit ta 'togħma ta' proċeduri rikursivi. Nisperaw, inti taħseb kodiċi hija ftit aktar sbieħ jekk ikunu implimentati fi, b'mod rikursivi eleganti. Iżda anke jekk le, recursion huwa għodda verament b'saħħtu xorta. U hekk huwa definittivament xi ħaġa li tikseb ras tiegħek madwar, għaliex inti ser tkun kapaċi joħolqu programmi pretty jibred li jużaw recursion li inkella jkun kumpless li tikteb jekk inti qed tuża loops u iterazzjoni. Jien Doug Lloyd. Dan huwa CS50.