[MUZIKO Ludante] 

DOUG LLOYD: Vi probable pensas ke kodo estas nur uzita por plenumi taskon. Vi skribas ĝin. Ĝi faras iun. Tio estas sufiĉe multe ĝin. 

Vi kompili ĝin. Vi kuras la programon. Vi estas bona iri. 

Sed, kredu aŭ ne, se vi kodigi por longa tempo, vi efektive povus veni vidi kodo kiel iu kiu estas bela. Ĝi solvas problemon en tre interesa maniero, aŭ ekzistas nur io vere neta pri la vojo ĝi rigardas. Vi povus esti ridante ĉe mi, sed ĝi estas vera. Kaj rikuro estas maniero por ia akiri tiun ideon de bela, eleganta aspekto kodon. Ĝi solvas problemojn en manieroj kiuj estas interesa, facila por bildigi, kaj surprize mallonga. 

La vojo rekursio verkoj estas, rekursia funkcio estas difinita kiel funkcio kiu nomas sin kiel parto de lia ekzekuto. Kiuj povus simili iom stranga, kaj ni vidos iomete pri kiel tio funkcias en momento. Sed denove, ĉi tiuj rekursiaj proceduroj estas tuj estos tiel eleganta ĉar ili tuj solvi tiun problemon sen havante ĉiujn tiujn aliajn funkciojn aŭ tiuj longaj bukloj. Vi vidos ke tiuj rekursiaj proceduroj tuj serĉos tiel mallonga. Kaj ili vere intencas fari via kodo aspektas multe pli bela. 

Mi donos al vi ekzemplon de tiu por vidi kiel rekursia proceduro povus esti difinita. Do se vi estas familiara kun ĉi de math klaso multaj jaroj, Estas io nomata la faktoriala funkcio, kiu estas kutime signifita kiel ekkrion punkto, kiu estas difinita super ĉiuj pozitivaj entjeroj. Kaj la vojon ke n faktorialo kalkuliĝas Estas vi multiplikas ĉiujn la nombroj malpli ol aŭ egala al n together-- ĉiuj entjeroj malpli ol aŭ egala al n kune. 

Do 5 faktorialo estas 5 fojoj 4 fojoj 3 fojojn 2 fojoj 1. Kaj 4 faktorialo estas 4 fojoj 3 fojojn 2 fojoj 1 kaj tiel plu. Vi ricevas la ideon. 

Kiel programistoj, ni ne uzi n, ekkrio punkto. Do ni difini la faktorialo funkcion kiel fakto de n. Kaj ni uzos faktorialo krei rekursia solvo al problemo. Kaj mi kredas ke vi povus trovi ke ĝi estas multe pli vide vokante ol la ripeta versio de tiu, kiu ni ankaŭ rigardu en momento. 

Do tie estas paro de facts-- vortludo intended-- pri factorial-- la faktorialo funkcio. La faktorialo de 1, kiel mi diris, estas 1. La faktorialo de 2 estas 2 fojoj 1. La faktorialo de 3 estas 3 tempoj 2 fojoj 1, kaj tiel plu. Ni parolis pri 4 kaj 5 jam. 

Sed rigardante tiun, ne tiu vera? Ne faktorialon 2 ĵus 2 fojoj la faktorialo de 1? Mi volas diri, la faktorialo de 1 estas 1. Do kial ni ne povas simple diri ke, ekde faktorialon 2 estas 2 fojoj 1, ĝi estas vere nur 2 fojojn la faktorialo de 1? 

Kaj tiam etendante ke ideo, ne estas la faktorialo de 3 nur 3 fojojn la faktorialon 2? Kaj la faktorialo de 4 estas 4 fojoj la faktorialo de 3, kaj tiel plu? Fakte, la faktorialo de iu nombro povas nur esprimus se ni ia de porti ĉi ekstere forever. Ni povas ia ĝeneraligi la faktorialo problemo ŝajnas al n tempoj la faktorialo de n minus 1. Ĝi estas n fojoj la produkto de ĉiuj nombroj malpli ol mi. 

Ĉi tiu ideo, tiu ĝeneraligo de la problemo, nin permesas rikure difini la faktorialo funkcio. Kiam vi difinas funkcion rekursie, ekzistas du aĵojn kiuj bezonas esti parto de tio. Vi bezonas havi iu nomita baza kazo, kiu, kiam vi deĉenigi ĝin, ĉesos la rekursia procezo. 

Alie, funkcio kiu nomas itself-- kiel vi povus imagine-- povus daŭrigi eterne. Funkcio vokas la funkcion vokas la funkcio alvokoj la funkcio vokas la funkcio. Se vi ne havas vojon halti ĝin, via programo estos efike senmoviĝita ĉe senfina ciklo. Ĝi kraŝos eventuale, ĉar ĝi devos kuri el memoro. Sed tio estas apud la punkto. 

Ni bezonas havi alian rimedon por haltigi aferoj krom nia programo plorkriado, ĉar programo kiu kraŝas estas probable ne bela aŭ eleganta. Kaj do ni nomas tion la baza kazo. Simpla solvo al problemo kiu detenas la rekursia procezo de okazanta. Do jen unu parto de rekursia funkcio. 

La dua parto estas la rekursiaj kazo. Kaj tio estas kie la rikuro efektive okazos. Tio estas kie la funkcio nomos sin. 

Ĝi ne nomas sin en akurate sammaniere oni nomis. Ĝi estos malgranda varianto kiu faras la problemo estas provante solvi teeny iom pli malgranda. Sed ĝenerale pasas la cervo solvi la plejparton de la solvo al malsama alvoko malsupren la linio. 

Kiu el tiuj rigardoj kiel la baza kazo tie? Kiu el tiuj rigardoj kiel la simpla solvo al problemo? Ni havas faskon de faktorialoj, kaj ni povus daŭrigi irante on-- 6, 7, 8, 9, 10, kaj tiel plu. 

Sed unu el tiuj aspektas kiel bona kazo kiel la baza kazo. Ĝi estas tre simpla solvo. Ni ne devas fari ion specialan. 

La faktorialo de 1 estas nur 1. Ni ne devas fari ajnan multipliko ajn. Ĝi ŝajnas kiel se ni iras provi kaj solvi tiun problemon, kaj ni devas halti la rekursio ie, ni probable volas halti ĝi kiam ni atingos 1. Ni ne volas halti antaŭ tiu. 

Do se ni difini nia faktoriala funkcio, jen skeleto por kiel ni povus fari tion. Ni devas ŝtopi en tiuj du things-- la baza kazo kaj la rekursiaj kazo. Kio estas la bazo kazo? Se n estas egala al 1, revenu 1-- tio vere simplan problemon solvi. 

La faktorialo de 1 estas 1. Ĝi estas ne 1 fojojn nenion. Estas nur 1. Ĝi estas tre facila fakto. Kaj tial povas esti nia bazo kazo. Se ni get pasis 1 en tiun funkcio, ni simple reveni 1. 

Kio estas la rekursiaj kazo probable aspektas? Por ĉiu alia nombro krom 1, kio estas la mastro? Nu, se ni prenas la faktorialo de n, ĝi estas n fojoj la faktorialo de n minus 1. 

Se ni prenas la faktorialo de 3, ĝi estas 3 fojoj la faktorialo de 3 minus 1, aŭ 2. Kaj do se ni ne rigardante 1, alie reveno n tempoj la faktorialo de n minus 1. Ĝi estas bela simpla. 

Kaj pro havi iomete purigisto kaj pli eleganta kodo, scii ke se ni havas unu-linio cikloj unuop-linio kondiĉaj branĉoj, Ni povas forigi ĉiujn de la krispa krampoj ĉirkaŭ ili. Do ni povas firmigi tion ĉi. Tio havas ekzakte la saman funcionalidad kiel ĉi. 

Mi simple forprenus la krispa krampoj, ĉar estas nur unu linio ene de tiuj kondiĉitaj branĉoj. Do tiuj kondutas idente. Se n estas egala al 1, 1 reveni. Alie reveni n fojoj la faktorialo de n minus 1. Do ni estas farante la problemo malgranda. Se n komencas kiel 5, ni tuj reveni 5 fojoj la faktorialo de 4. Kaj ni vidos post minuto, kiam ni parolas pri la alvoko stack-- en alia video kie ni parolos pri la voki stack-- ni lernos pri kial ĝuste tiu procezo funkcias. 

Sed dum faktorialo de 5 Diras reveni 5 fojojn faktorialo de 4, kaj 4 tuj diri, OK, nu, reveno 4 fojoj la faktorialo de 3. Kaj kiel vi povas vidi, ni estas ia alproksimiĝanta 1. Ni nun estas pli kaj pli proksima al tiu bazo kazo. 

Kaj iam ni batis la baza kazo, ĉiuj la antaŭaj funkcioj havas la respondon ili serĉis. Faktorialon 2 estis diranta reveno 2 fojoj la faktorialo de 1. Nu, faktorialo de 1 estas 1. Do la alvokon por faktorialo de 2 povas reveni 2 fojoj 1, kaj donu ke reen al faktorialon 3, rezervate ke rezulto. 

Kaj tiam ĝi povas kalkuli lia rezulto, 3 fojojn 2 estas 6, kaj donu al faktorialon 4. Kaj cetere, ni havas vídeo sur la alvoko pilo kie tio estas ilustrita iom pli ol kion mi diras nun. Sed tio estas ĝi. Tiu sole estas la solvo al kalkulanta la faktorialo de nombro. 

Ĝi estas nur kvar linioj de kodo. Tio estas sufiĉe malvarma, ĉu ne? Estas speco de sexy. 

Do ĝenerale, sed ne ĉiam, rekursia funkcio povas anstataŭi maŝo en ne-rekursia funkcio. Do tie, flanko ĉe flanko, estas la ripeta versio de la funkcio faktorialo. Ambaŭ tiuj kalkuli ĝuste la sama afero. 

Ili ambaŭ kalkuli la faktorialo de n. La versio sur la maldekstra uzas rekursio fari ĝin. La versio sur la dekstra uzas ripeto fari ĝin. 

Kaj rimarki, ni devas deklari ŝanĝiĝema entjero produkto. Kaj tiam ni buklo. Tiel longe kiel n estas pli granda ol 0, ni teni multiplikante ke produkto de n kaj decrementing n ĝis ni kalkulas la produkton. Do tiuj du funkcioj, denove, fari precize la sama afero. Sed ili ne faras ĝin en ĝuste la sama maniero. 

Nun, ĝi eblas havi pli ol unu bazo kazo aŭ pli ol unu rekursiaj kazo, depende sur kio via funkcio provas fari. Vi ne nepre limiĝas al sola bazo kazo aŭ sola rekursiaj kazo. Do ekzemplo de io kun multoblaj bazo kazoj povus esti this-- la Fibonaĉi-nombroj sekvenco. 

Vi eble memoras de elementa lernejo tagoj ke la Fibonaĉi sinsekvo estas difinita kiel this-- la unua elemento estas 0. La dua elemento estas 1. Ambaŭ tiuj estas nur per difino. 

Tiam ĉiu alia elemento estas difinita kiel sumo de n minus 1 kaj n minus 2. Do la tria ero estus 0 plus 1 estas 1. Kaj poste la kvara elemento estus la dua elemento, 1, plus la tria elemento, 1. Kaj ke estus 2. Kaj tiel plu kaj tiel plu. 

Do en ĉi tiu kazo, ni havas du bazo kazoj. Se n estas egala al 1, revenu 0. Se n estas egala al 2, revenu 1. Alie, redoni Fibonacci de n minus 1 plus Fibonacci de n minus 2. 

Do jen multoblaj bazo kazoj. Kio pri multoblaj rekursia kazoj? Nu, estas io nomata _Collatz_ konjekto. Mi ne intencis diri, vi scias, kio tio estas, ĉar ĝi estas fakte nia fina problemo por tiu aparta video. Kaj estas nia ekzerco labori pri kune. 

Do jen kion la _Collatz_ Konjekto is-- ĝi aplikas al ĉiu pozitiva entjero. Kaj ĝi spekulas ke ĝi estas ĉiam eblas reiri al 1 se vi sekvas ĉi tiujn paŝojn. Se n estas 1, ĉesi. Ni havas reen al 1 se n estas 1. 

Alie, iru tra tiu procezo denove sur n dividita per 2. Kaj vidu se vi povas reiri al 1. Alie, se n estas nepara, trairu tiu procezo denove sur 3n plus 1, aŭ 3 fojoj n plus 1. Do jen ni havas ununuran bazon kazo. Se n estas egala al 1, ĉesi. Ni ne faras plu rekursio. 

Sed ni havas du rekursiaj kazoj. Se n estas para, ni faru unu rekursiaj kazo, nomante n dividita per 2. Se n estas nepara, ni faru alian rekursiaj kazo sur 3 fojoj n plus 1. 

Kaj tial la objektivo por ĉi tiu video estas preni duan, paŭzo la vídeo, kaj provi kaj skribi ĉi rekursia funkcio _Collatz_ kie pasas en valoro n, kaj ĝi kalkulas kiom da paŝoj li prenas akiri al 1, se vi komencas de n kaj vi sekvas tiujn paŝojn ĝis supre. Se n estas 1, ĝi prenas 0 paŝoj. Alie, ĝi tuj preni unu paŝon pli tamen multaj ŝtupoj prenas cxiuflanke n dividite per 2 se n estas para, aŭ 3n plus 1 se n estas nepara. 

Nu, mi jam metis supre sur la ekrano tie paro de testo por Vi kelkaj provoj kazoj por vin viziti kion tiuj diversaj _Collatz_ numeroj estas, kaj ankaŭ ilustraĵo de la paŝoj kiuj devas esti irinta tra tiel vi povas ia vidi ĉi procezon en ago. Do se n estas egala al 1, _Collatz_ de n estas 0. Vi ne devas fari ion reiri al 1. Vi jam tie. 

Se n estas 2, ĝi prenas unu paŝo por atingi 1. Vi komencas kun 2. Nu, 2 estas ne egala al 1. Do ĝi estas tuj estos unu paŝo plus tamen multaj paŝoj prenas sur n dividita per 2. 

2 dividita per 2 estas 1. Do ĝi prenas unu paŝon pli tamen multaj ŝtupoj prenas por 1. 1 prenas nulon paŝoj. 

Por 3, kiel vi povas vidi, ekzistas tre kelkajn paŝojn implikita. Vi iru el 3. Kaj poste vi iros al 10, 5, 16, 8, 4, 2, 1. Ĝi prenas sep ŝtupojn reiri al 1. Kaj kiel vi povas vidi, ke estas Paro aliaj testo kazoj tie testi vian programon. Do denove, paŭzo la vídeo. Kaj mi eniros salti reen nun al kion la efektiva procezo estas ĉi tie, kion tiu konjekto estas. 

Kontrolu cxu vi povas diveni kiel difini _Collatz_ de n tiel ke ĝi kalkulas kiom da paŝas ĝi prenas akiri al 1. Do espereble, vi paŭzis la video kaj vi ne nur atendis min doni al vi respondon ĉi tie. Sed se vi estas, nu, jen la respondo ĉiuokaze. 

Do jen ebla difino de la _Collatz_ funkcio. Nia bazo case-- se n estas egala al 1, ni revenos 0. Ĝi ne prenas ajnan paŝoj reiri al 1. 

Alie, ni havas du rekursiaj cases-- unu por numeroj kaj unu por nepara. La maniero mi testi pri numeroj estas kontroli se n mod 2 egalas 0. Tiu estas esence, denove, petante la demandon, se vi memoras kion mod is-- se mi dislimo n per 2 estas tie neniu cetero? Tio estus para nombro. 

Kaj do se n mod 2 egalas 0 estas testado estas ĉi para nombro. Se jes, mi volas reveni 1, ĉar tiu estas definitive prenante unu paŝon plie _Collatz_ de ajn nombro estas duono de mi. Alie, mi volas reveni 1 plus _Collatz_ de 3 fojoj n plus 1. Tio estis la alia rekursia paŝo kiun ni povus preni por kalkuli la Collatz-- la nombro de paŝoj ĝi prenas akiri reen al 1 donita nombro. Do espereble, tiu ekzemplo donis vi iomete de gusto de rekursiaj proceduroj. Espereble, vi pensas kodo estas iom pli bela se implementado en eleganta, rekursiaj vojo. Sed eĉ se ne, rekursio estas vere potenca ilo tamen. Kaj do ĝi estas definitive ion akiri vian kapon ĉirkaŭe, ĉar vi povos krei bela malvarmeta programojn uzante rekursio kiuj povus alie esti kompleksa skribi se vi uzas maŝojn kaj iteracio. Mi Doug Lloyd. Jen CS50.