[Music kucheza] 

DOUG LLOYD: Pengine kufikiri kwamba kanuni ni tu kutumika kwa kukamilisha kazi. Kuandika ni nje. Ni haina kitu. Hiyo ni pretty kiasi. 

Wewe kukusanya yake. Wewe kuendesha programu. Wewe ni vizuri kwenda. 

Lakini amini au, kama wewe kanuni kwa muda mrefu, wewe kweli ili kuja kuona kanuni kama kitu ambacho ni nzuri. Ni kutatua tatizo katika njia ya kuvutia sana, au kuna tu kitu kweli nadhifu kuhusu njia inaonekana. Unaweza kuwa akicheka saa yangu, lakini ni kweli. Na kujirudia ni njia mojawapo kwa namna ya kupata wazo hili ya nzuri, kifahari-kuangalia kanuni. Ni kutatua matatizo kwa njia ambazo ni ya kuvutia, rahisi taswira, na kushangaza mfupi. 

Kazi njia kujirudia ni, kazi ya kujirudia inaelezwa kama kazi kwamba wito yenyewe kama sehemu ya utekelezaji wake. Hiyo inaweza kuonekana kidogo ajabu, na tutaweza kuona kidogo kuhusu jinsi hii matendo katika wakati huu. Lakini tena, hizi taratibu kujirudia ni kwenda kuwa hivyo kifahari kwa sababu wao wanaenda kutatua tatizo hili bila kuwa kazi hizi zote nyingine au hizi mizunguko ya muda mrefu. Utaona kwamba hizi kujirudia taratibu ni kwenda kuangalia hivyo kwa muda mfupi. Na kwa kweli ni kwenda kufanya kanuni yako kuangalia mengi nzuri zaidi. 

Mimi nitakupa mfano ya hii kuona jinsi utaratibu kujirudia inaweza kuelezwa. Hivyo kama wewe ni ukoo na hii kutoka hesabu darasani miaka mingi iliyopita, kuna kitu kinachoitwa factorial kazi, ambayo ni kawaida ulionyehsa kama mshangao uhakika, ambayo inaelezwa zaidi ya integers yote mazuri. Na kwa njia hiyo n factorial ni mahesabu ni wewe kuzidisha yote ya nambari chini ya au sawa na n together-- integers zote chini ya au sawa na n pamoja. 

Hivyo 5 factorial ni mara 5 Mara 4 mara 3 2 mara 1. Na 4 factorial ni mara 4 Mara 3 2 mara 1 na kadhalika. Unaweza kupata wazo. 

Kama programmers, hatufanyi kutumia n, mshangao uhakika. Hivyo tutaweza kufafanua factorial kazi kama ukweli wa n. Na tutaweza kutumia factorial kujenga ufumbuzi kujirudia kwa tatizo hilo. Na nadhani unaweza kupata kuwa ni mengi zaidi kuibua rufaa ya iterative toleo la hii, ambayo tutaweza pia tuangalie katika wakati huu. 

Hivyo hapa ni michache ya facts-- pun intended-- kuhusu factorial-- factorial kazi. Factorial ya 1, kama nilivyosema, ni 1. Factorial ya 2 ni 2 mara 1. Factorial ya 3 ni 3 mara 2 mara 1, na kadhalika. Kuongelea 4 na 5 tayari. 

Lakini kuangalia hii, ni hii si kweli? Si factorial ya 2 tu 2 mara factorial ya 1? I mean, factorial ya 1 ni 1. Hivyo kwa nini hatuwezi tu kusema kwamba, tangu factorial ya 2 ni 2 mara 1, ni kweli tu mara 2 factorial ya 1? 

Na kisha kupanua wazo hilo, si factorial ya 3 tu mara 3 factorial ya 2? Na factorial ya 4 ni mara 4 factorial ya 3, na kadhalika? Kwa kweli, factorial ya idadi yoyote unaweza tu kuwa walionyesha kama sisi aina ya kubeba huu milele nje. Tunaweza aina ya kujumlisha Tatizo factorial kama ni n mara factorial ya n bala 1. Ni mara n bidhaa za namba zote chini ya mimi. 

Wazo hili, hii generalization ya tatizo, inaruhusu sisi recursively kufafanua kazi factorial. Wakati kufafanua kazi recursively, kuna mambo mawili ambayo yanahitaji kuwa sehemu yake. Unahitaji kuwa na kitu kinachoitwa kesi ya msingi, ambayo, wakati wewe kusababisha yake, kuacha mchakato kujirudia. 

Vinginevyo, kazi kwamba wito itself-- kama unaweza imagine-- inaweza kuendelea milele. Kazi wito kazi wito wito kazi kazi wito kazi. Kama huna njia na kuacha ni, mpango wako Itakuwa ufanisi kukwama katika kitanzi usio. Itakuwa ajali hatimaye, kwa sababu kutakuwa na kukimbia nje ya kumbukumbu. Lakini hiyo ni kando ya uhakika. 

Tunahitaji kuwa na njia nyingine kuacha mambo badala ya mpango wetu mshindo, kwa sababu mpango huo shambulio ni pengine si nzuri au kifahari. Na hivyo sisi wito huu kesi ya msingi. Hii ni ufumbuzi rahisi tatizo ambalo haachi mchakato kujirudia kutoka kutokea. Hivyo hiyo ni sehemu moja ya kazi ya kujirudia. 

Sehemu ya pili ni kesi ya kujirudia. Na hii ni mahali ambapo kujirudia kwa kweli kuchukua nafasi. Hii ni pale ambapo kazi itakuwa kujiita. 

Itakuwa si kujiita katika hasa njia ile ile ilikuwa inaitwa. Ni utakuwa tofauti kidogo kwamba inafanya tatizo ni kujaribu kutatua teeny kidogo kidogo. Lakini kwa ujumla hupita mume ya kutatua wingi wa ufumbuzi mwito tofauti chini ya mstari. 

Ni yupi kati ya hawa inaonekana kama kesi ya msingi hapa? Ambayo moja ya inaonekana hawa kama rahisi ufumbuzi wa tatizo? Tuna kundi la factorials, na tunaweza kuendelea kwenda on-- 6, 7, 8, 9, 10, na kadhalika. 

Lakini moja ya inaonekana hawa kama kesi nzuri ya kuwa kesi ya msingi. Ni ufumbuzi rahisi sana. Hatuna kufanya kitu chochote maalum. 

Factorial ya 1 ni 1 tu. Hatuna kufanya lolote kuzidisha wakati wote. Inaonekana kama kama tunakwenda kujaribu na kutatua tatizo hili, na sisi haja ya kuacha kujirudia mahali fulani, sisi pengine wanataka kuacha ni wakati sisi kupata 1. Hatutaki kuacha kabla ya hapo. 

Hivyo kama sisi ni kufafanua kazi yetu factorial, hapa ni mifupa kwa jinsi sisi anaweza kufanya hivyo. Tunahitaji kuziba katika wale wawili things-- kesi ya msingi na kesi ya kujirudia. Nini kesi ya msingi? Kama n ni sawa na 1, kurudi 1-- hiyo ni Tatizo kweli rahisi kutatua. 

Factorial ya 1 ni 1. Siyo 1 mara chochote. Ni tu 1. Ni ukweli rahisi sana. Na hivyo ambayo inaweza kuwa msingi wetu kesi. Kama sisi kupata kupita 1 katika hii kazi, tutaweza tu kurudi 1. 

Nini kujirudia kesi pengine kuangalia kama? Kwa kila idadi vingine badala 1, nini mfano? Naam, kama sisi ni kuchukua factorial ya n, ni mara n factorial ya n bala 1. 

Kama sisi ni kuchukua factorial ya 3, ni mara 3 factorial ya 3 bala 1, au 2. Na hivyo kama sisi siyo kuangalia saa 1, vinginevyo Mara kurudi n factorial ya n bala 1. Ni pretty moja kwa moja. 

Na kwa ajili ya kuwa na kidogo safi na zaidi ya kifahari kificho, kujua kwamba kama tuna single-mstari loops au moja-line matawi masharti, tunaweza kujikwamua yote ya braces curly inayowazunguka. Ili tuweze kuimarisha huu kwa hili. Hii ina sawa utendaji kama hii. 

Mimi tu kuchukua mbali curly inakabiliwa na, kwa sababu kuna mstari mmoja tu ndani ya matawi hayo masharti. Basi hizi kuishi identically. Kama n ni sawa na 1, kurudi 1. Vinginevyo kurudi mara n factorial ya n bala 1. Hivyo sisi ni kufanya tatizo ndogo. Kama n kuanza nje kama 5, tunakwenda kurudi mara 5 factorial ya 4. Na tutaweza kuona katika dakika tunapozungumza kuhusu wito stack-- katika video nyingine ambapo sisi majadiliano juu piga stack-- tutaweza kujifunza kuhusu nini hasa mchakato huu kazi. 

Lakini wakati factorial ya 5 inasema kurudi mara 5 factorial ya 4, na 4 ni kwenda kusema, OK, vizuri, kurudi Mara 4 factorial ya 3. Na kama unaweza kuona, tuko aina ya inakaribia 1. Sisi ni kupata karibu na karibu na kwamba kesi ya msingi. 

Na mara moja sisi hit kesi ya msingi, yote ya kazi ya awali jibu walikuwa wanatafuta. Factorial ya 2 alikuwa akisema kurudi 2 mara factorial ya 1. Naam, factorial ya 1 anarudi 1. Hivyo wito kwa factorial ya 2 wanaweza kurudi mara 2 kwa 1, na kutoa kwamba nyuma ya factorial ya 3, ambayo ni kusubiri kwa kuwa matokeo. 

Na kisha unaweza mahesabu matokeo yake, mara 3 2 ni 6, na kuwapa nyuma kwa factorial ya 4. Na tena, tuna video juu ya wito mkusanyiko ambapo hii ni mfano kidogo zaidi ya nini mimi kusema hivi sasa. Lakini hii ni yake. Hii peke yake ni ufumbuzi wa kuhesabu factorial ya idadi. 

Ni mistari minne tu ya kificho. Hiyo ni pretty baridi, sawa? Ni aina ya sexy. 

Hivyo kwa ujumla, lakini si siku zote, kazi ya kujirudia anaweza kuchukua nafasi kitanzi katika yasiyo ya kujirudia kazi. Hivyo hapa, bega kwa bega, ni iterative toleo la kazi factorial. Wote hawa mahesabu hasa kitu kimoja. 

Wote wawili mahesabu factorial ya n. Toleo la upande wa kushoto anatumia kujirudia kwa kufanya hivyo. Toleo la juu ya haki anatumia iteration ya kufanya hivyo. 

Na taarifa, tuna kutangaza kutofautiana integer bidhaa. Na kisha sisi kitanzi. Hivyo muda mrefu kama n ni kubwa kuliko 0, sisi kuweka kuzidisha kuwa bidhaa hiyo na N na decrementing n mpaka sisi mahesabu ya bidhaa. Hivyo kazi hizi mbili, tena, kufanya hasa kitu kimoja. Lakini hawana kufanya hivyo katika hasa kwa njia hiyo. 

Sasa, inawezekana kwa kuwa na msingi zaidi ya moja kesi au zaidi ya moja kujirudia kesi, kulingana juu ya nini kazi yako ni kujaribu kufanya. Wewe ni si lazima tu mdogo kwa kesi moja ya msingi au kujirudia moja kesi. Hivyo mfano wa kitu na kesi nyingi msingi Haya inaweza kuwa Fibonacci idadi mlolongo. 

Unaweza kukumbuka kutoka msingi siku shule kwamba mlolongo Fibonacci inaelezwa kama hii kitu cha kwanza ni 0. Kipengele cha pili ni 1. Wote wale ni tu kwa ufafanuzi. 

Kisha kila kipengele nyingine inaelezwa kama jumla ya n bala 1 na n bala 2. Hivyo kipengele cha tatu itakuwa 0 pamoja na 1 ni 1. Na kisha kipengele cha nne itakuwa kipengele cha pili, 1, pamoja na kipengele cha tatu, 1. Na kwamba itakuwa 2. Na kadhalika na kadhalika. 

Hivyo katika kesi hii, tuna kesi mbili msingi. Kama n ni sawa na 1, kurudi 0. Kama n ni sawa na 2, kurudi 1. Vinginevyo, kurudi Fibonacci wa n bala 1 pamoja Fibonacci wa n bala 2. 

Hivyo hiyo ni kesi nyingi msingi. Je kuhusu kesi nyingi kujirudia? Naam, kuna kitu aitwaye dhana Collatz. Mimi si kwenda kusema, unajua nini, yaani, kwa sababu ni kweli mwisho wetu Tatizo kwa video hii tu. Na ni zoezi wetu kufanya kazi ya pamoja. 

Hivyo hapa ni nini Collatz dhana is-- inatumika kwa kila sifuri. Na speculates kwamba ni kila mara inawezekana kupata nyuma kwa 1 kama wewe kufuata hatua hizi. Kama n ni 1, kuacha. Sisi tumepewa nyuma 1 ikiwa n ni 1. 

Vinginevyo, kwenda kwa njia hii mchakato tena juu ya n kugawanywa na 2. Na kuona kama unaweza kupata nyuma 1. Vinginevyo, kama n ni isiyo ya kawaida, kupitia mchakato huu tena juu ya 3n pamoja na 1, au mara 3 n pamoja na 1. Hivyo hapa tuna moja kesi ya msingi. Kama n ni sawa na 1, kuacha. Sisi siyo kufanya kujirudia tena. 

Lakini tuna kesi mbili kujirudia. Kama n ni hata, tunafanya kujirudia moja kesi, wito n kugawanywa na 2. Kama n ni isiyo ya kawaida, sisi kufanya mbalimbali kujirudia kesi juu mara 3 n pamoja na 1. 

Na hivyo lengo kwa video hii ni kuchukua pili, pause video, na kujaribu na kuandika hii kazi ya kujirudia Collatz ambapo kupita katika thamani n, na ni mahesabu ya hatua wangapi ni inachukua kupata 1 kama wewe kuanza kutoka n na wewe kufuata hatua hizo hadi hapo juu. Kama n ni 1, inachukua hatua 0. Vinginevyo, ni kwenda kuchukua hatua moja pamoja na hata hivyo hatua nyingi inachukua juu ya n ama kugawanywa na 2 kama n ni hata, au 3n pamoja na 1 kama n ni isiyo ya kawaida. 

Sasa, nimekuwa kuweka juu ya screen hapa michache ya mtihani mambo kwa ajili yenu, michache ya kesi ya vipimo kwa ajili yenu, ili kuona nini hawa mbalimbali idadi Collatz ni, na pia mfano ya hatua ambazo haja ya kuwa wamekwenda kupitia hivyo unaweza aina ya kuona mchakato huu katika hatua. Hivyo kama n ni sawa na 1, Collatz ya n ni 0. Huna kufanya chochote kupata nyuma 1. Wewe ni tayari pale. 

Kama n ni 2, inachukua hatua moja ya kupata 1. Unaweza kuanza kwa 2. Naam, 2 si sawa na 1. Hivyo ni kwenda kuwa hatua moja pamoja na hata hivyo wengi hatua hiyo inachukua n kugawanywa na 2. 

2 kugawanywa na 2 ni 1. Hivyo inachukua hatua moja pamoja na hata hivyo hatua nyingi inachukua kwa 1. 1 inachukua hatua sifuri. 

Kwa 3, kama unaweza kuona, kuna hatua chache kabisa kushiriki. Wewe kwenda kutoka 3. Na kisha kwenda kwa 10, 5, 16, 8, 4, 2, 1. Inachukua hatua saba kupata nyuma 1. Na kama unaweza kuona, kuna wanandoa wengine kesi mtihani hapa mtihani nje mpango wako. Hivyo tena, pause video. Na nitakwenda kuruka nyuma sasa kwa nini mchakato halisi ni hapa, nini dhana hii ni. 

Kuona kama unaweza kufikiri jinsi ya kufafanua Collatz ya n hivyo kwamba mahesabu ya jinsi wengi hatua inachukua kupata kwa 1. Hivyo hopefully, una paused video na wewe si tu kusubiri kwa ajili yangu kukupa jibu hapa. Lakini kama wewe ni, vizuri, hapa ni jibu hata hivyo. 

Hivyo hapa ni ufafanuzi iwezekanavyo ya kazi Collatz. Msingi wetu case-- ikiwa n ni sawa na 1, sisi kurudi 0. Haina kuchukua yoyote hatua ya kupata nyuma 1. 

Vinginevyo, tuna mbili kujirudia cases-- moja kwa idadi hata na kimoja cha isiyo ya kawaida. Njia ya mimi mtihani kwa idadi hata ni kuangalia kama n Mod 2 sawa na 0. Hii ni kimsingi, tena, kuuliza swali, kama unakumbuka kile mod is-- kama mimi mgawanyiko n na 2 ni hakuna salio? Hiyo itakuwa hata idadi. 

Na hivyo kama n Mod 2 sawa na 0 ni kupima ni hii hata idadi. Kama ni hivyo, nataka kurudi 1, kwa sababu hii ni dhahiri kuchukua hatua moja pamoja na Collatz ya chochote idadi ni nusu ya mimi. Vinginevyo, nataka kurudi 1 pamoja na Collatz ya mara 3 n pamoja na 1. Hiyo ilikuwa ni mwingine hatua kujirudia kwamba sisi inaweza kuchukua kwa mahesabu Collatz-- idadi ya hatua inachukua kupata nyuma kwa 1 kutokana na idadi. Hivyo hopefully, mfano huu aliwapa kidogo ya ladha ya taratibu kujirudia. Hopefully, unafikiri kificho ni kidogo nzuri zaidi kama zinatekelezwa katika kifahari, kujirudia njia. Lakini hata kama si, kujirudia ni kweli zana yenye nguvu hata hivyo. Na hivyo ni dhahiri kitu kupata kichwa yako karibu, kwa sababu wewe utakuwa na uwezo wa kujenga mipango pretty baridi kwa kutumia recursion kwamba ili vinginevyo kuwa ngumu kuandika kama unatumia mizunguko na iteration. Mimi nina Doug Lloyd. Hii ni CS50.