[MIZIK jwe] 

Doug Lloyd: Ou pwobableman panse ke Kòd se jis itilize yo akonpli yon travay. Ou ekri li soti. Li fè sa yon bagay. Sa a bèl anpil li. 

Ou konpile li. Ou kouri pwogram nan. Ou se bon yo ale. 

Men, kwè li ou pa, si ou kòd pou yon tan long, ou aktyèlman ta ka vin wè Kòd kòm yon bagay sa a, se bèl. Li rezoud yon pwoblèm nan yon fason trè enteresan, oswa si gen nan jis yon bagay ki reyèlman pwòp sou wout la li sanble. Ou ka ri nan m ', men li la vre. Apre sa, se yon fason rkursyon sòt de jwenn ide sa a nan bèl, elegant-kap kòd. Li rezoud pwoblèm nan fason ki yo enteresan, fasil yo visualized, ak surprenante kout. 

Travay yo fason rkursyon se, yon fonksyon repetitif se defini kòm yon fonksyon ki rele tèt li kòm yon pati nan ekzekisyon li yo. Sa ta ka sanble yon ti kras etranj, epi nou pral wè yon ti jan sou ki jan sa a ap travay nan yon moman. Men, ankò, sa yo pwosedi repetitif yo ale yo dwe tèlman gwo bèl chato paske yo ap ale yo rezoud pwoblèm sa a san gen tout bagay sa yo lòt fonksyon oswa sa yo pasan lontan. Ou pral wè ke sa yo repetitif pwosedi yo ale nan gade konsa kout. Apre sa, yo reyèlman yo ale nan fè kòd ou a gade yon anpil plis bèl. 

Mwen pral ba w yon egzanp nan sa a yo wè ki jan yon pwosedi repetitif ka defini. Se konsa, si w ap abitye ak sa a nan klas matematik anpil ane de sa, gen nan yon bagay yo rele nan faktoryèl fonksyon, ki se nòmalman deziye kòm yon pwen esklamasyon, ki se defini sou tout nonm antye relatif pozitif. Apre sa, fason ke n faktoryèl se kalkile se ou anpil anpil pitit tout nan chif yo mwens pase oswa egal a N together-- tout nonm antye relatif yo mwens pase oswa egal a n ansanm. 

Se konsa, 5 faktoryèl se 5 fwa 4 fwa 3 fwa 2 fwa 1. Ak 4 faktoryèl se 4 fwa 3 fwa 2 fwa 1 ak sou sa. Ou jwenn lide la. 

Kòm pwogramasyon, nou pa fè sa itilize n, pwen esklamasyon. Se konsa, nou pral defini faktoryèl a fonksyon kòm reyalite nan n. Epitou, n ap sèvi ak faktoryèl yo kreye yon solisyon repetitif nan yon pwoblèm. Apre sa, mwen panse ke ou ta ka jwenn ke li nan yon anpil plis vizyèlman fè apèl kont pase repete nan vèsyon an sa a, ki nou pral pran tou yon gade nan nan yon moman. 

Se konsa, isit la yo se yon koup la facts-- Pun intended-- sou factorial-- nan faktoryèl fonksyon. Faktoryèl a nan 1, jan mwen te di, se 1. Faktoryèl a nan 2 a se 2 fwa 1. Faktoryèl a nan 3 se 3 fwa 2 fwa 1, ak sou sa. Nou te pale de 4 ak 5 deja. 

Men, gade nan sa a, se pa sa a vre? Se pa faktoryèl nan 2 jis 2 fwa faktoryèl a nan 1? Mwen vle di, faktoryèl a nan 1 se 1. Se konsa, poukisa pa ka nou jis di ke, depi faktoryèl a 2 se 2 fwa 1, li a vrèman jis 2 fwa faktoryèl a nan 1? 

Lè sa a, pwolonje lide sa a, se pa faktoryèl a nan 3 jis 3 fwa faktoryèl a nan 2? Apre sa, faktoryèl a nan 4 se 4 fwa faktoryèl a nan 3, ak sou sa? An reyalite, faktoryèl a nan nenpòt ki nimewo ka jis dwe manifeste si nou kalite a pote sa a soti pou tout tan. Nou ka kalite jeneralizasyon pwoblèm nan faktoryèl kòm li nan n fwa yo faktoryèl nan n mwens 1. Li nan n fwa pwodwi a nan tout nimewo yo mwens pase m '. 

Lide sa a, sa a jeneralizasyon nan pwoblèm nan, pèmèt nou recursive defini fonksyon an faktoryèl. Lè ou defini yon fonksyon recursive, gen nan de bagay ki bezwen yo dwe yon pati nan li. Ou bezwen gen yon bagay yo rele yon ka baz, ki, lè ou deklanche li, yo ap sispann pwosesis la repetitif. 

Sinon, yon fonksyon ki rele itself-- jan ou ta ka imagine-- te kapab ale sou pou tout tan. Fonksyon rele fonksyon an rele apèl yo fonksyon fonksyon an rele fonksyon an. Si ou pa gen yon fason yo sispann li, pwogram ou an yo pral efektivman kole nan yon bouk enfini. Li pral aksidan evantyèlman, paske li pral kouri soti nan memwa. Men, sa a bò kote pwen an. 

Nou bezwen gen kèk lòt fason yo sispann bagay san konte ekraze pwogram nou an, paske yon pwogram ki aksidan se pwobableman pa bèl oswa elegant. Se konsa, nou rele ka sa a de baz la. Sa a se yon solisyon senp nan yon pwoblèm ki ap kanpe pwosesis la repetitif soti nan rive. Se konsa, sa a, se yon pati nan yon fonksyon repetitif. 

Pati nan dezyèm se ka a repetitif. Lè sa a se kote rkursyon nan pral aktyèlman pran plas li. Sa a se kote a fonksyon pral rele tèt li. 

Li pa pral rele tèt li nan egzakteman menm jan an li te rele. Li pral yon varyasyon ti tay ki fè pwoblèm nan li a eseye rezoud yon ti jan minuskul pi piti. Men, li jeneralman pase Buck a nan rezoud èstime nan solisyon an nan yon apèl diferan desann liy lan. 

Kilès nan sa yo sanble tankou ka a baz isit la? Ki youn nan sa yo renmen an sanble solisyon ki pi senp nan yon pwoblèm? Nou gen yon pakèt moun sou factorials, epi nou ta ka kontinye ale on-- 6, 7, 8, 9, 10, ak sou sa. 

Men, yonn nan sanble sa yo tankou yon bon ka yo dwe ka a baz. Li se yon solisyon trè senp. Nou pa bezwen fè anyen espesyal. 

Faktoryèl a nan 1 se jis 1. Nou pa gen fè nenpòt ki miltiplikasyon nan tout. Li sanble tankou si nou ap ale eseye ak rezoud pwoblèm sa a, epi nou bezwen sispann nan Rkursyon yon kote, nou pwobableman vle sispann li lè nou jwenn nan 1. Nou pa vle yo sispann anvan sa. 

Se konsa, si nou ap defini fonksyon faktoryèl nou an, isit la nan yon kilè eskèlèt pou ki jan nou ta ka fè sa. Nou bezwen ploge nan sa yo de bagay ka a baz epi ka-a repetitif. Ki sa ki nan ka a baz? Si n se egal a 1, retounen 1-- sa a, se yon pwoblèm vrèman senp yo rezoud. 

Faktoryèl a nan 1 se 1. Li pa 1 fwa anyen. Se jis 1. Li se yon reyalite trè fasil. Se konsa, ki ka ka baz nou an. Si nou jwenn te pase 1 nan sa a fonksyon, nou pral jis retounen 1. 

Ki sa ki nan repetitif nan ka pwobableman sanble? Pou chak nimewo lòt san konte 1, sa ki nan modèl la? Bon, si nou ap pran faktoryèl a nan n, li nan fwa n faktoryèl a nan n mwens 1. 

Si nou ap pran faktoryèl a nan 3, li a 3 fwa faktoryèl a nan 3 moins 1, oswa 2. Se konsa, si nou pa ap gade nan 1, otreman retounen n fwa yo faktoryèl nan n mwens 1. Li trè senp. 

Apre sa, pou dedomajman pou la li te gen yon ti kras pwòp ak plis elegant kòd, konnen ke si nou gen yon sèl liy-pasan oswa yon sèl liy-branch kondisyonèl, nou ka debarase m de tout de la aparèy òtopedik Curly bò kote yo. Se konsa, nou ka konsolide sa a sa a. Sa a gen ekzakteman menm bagay la fonctionnalités tankou sa a. 

Mwen jis pran lwen Curly a aparèy òtopedik, paske gen nan sèlman yon sèl liy andedan nan tout sa yo branch kondisyonèl. Se konsa, sa yo konpòte yo idantik. Si n se egal a 1, retounen 1. Sinon retounen fwa n faktoryèl a nan n mwens 1. Se konsa, nou ap fè pwoblèm nan pi piti. Si n kòmanse soti kòm 5, nou ap ale nan retounen 5 fwa faktoryèl a nan 4. Epitou, n ap wè nan yon minit lè nou pale sou stack-- la rele nan yon lòt videyo kote nou pale sou nan rele stack-- nou pral aprann sou rezon ki fè egzakteman pwosesis sa a travay. 

Men, pandan ke faktoryèl nan 5 di retounen 5 fwa faktoryèl nan 4, ak 4 ki pral di, OK, byen, retounen 4 fwa faktoryèl a nan 3. Ak jan ou ka wè, nou ap sòt de apwoche 1. Nou ap vin pi pre ak pi pre ke ka baz. 

Ak yon lòt fwa nou frape ka a baz, tout nan fonksyon yo anvan yo gen repons lan yo te kap chèche. Faktoryèl nan 2 te di retounen 2 fwa faktoryèl a nan 1. Oke, faktoryèl nan 1 retounen 1. Se konsa, apèl la pou faktoryèl nan 2 ka retounen 2 fwa 1, epi bay ki tounen nan faktoryèl a 3, ki ap tann pou ke rezilta. 

Lè sa a, li ka kalkile rezilta li yo, 3 fwa 2 se 6, epi remèt li tounen nan faktoryèl a 4. Epi ankò, nou gen yon videyo sou chemine a apèl kote sa a se ilistre yon ti kras plis pase sa m ap di kounye a. Men, sa a se li. Sa a pou kont li se solisyon an nan kalkile faktoryèl la nan yon kantite. 

Li nan sèlman kat liy nan kòd. Sa a trè fre, dwa? Li nan kalite sexy. 

Se konsa, an jeneral, men se pa toujou, yon fonksyon repetitif ka ranplase yon riban nan yon ki pa Peye-repetitif fonksyon. Se konsa, isit la, kòt a kòt, se repete nan vèsyon nan fonksyon an faktoryèl. Tou de sa yo kalkile egzakteman menm bagay la. 

Yo tou de kalkile faktoryèl la nan n. Vèsyon an sou bò gòch la sèvi ak rkursyon fè li. Vèsyon an sou bò dwat la sèvi ak iterasyon fè li. 

Apre sa, avi, nou gen deklare yon varyab nonb antye relatif yon pwodwi. Lè sa a, nou riban. Se konsa, lontan ke n se pi gran pase 0, nou kenbe miltipliye ke pwodwi pa n ak decrementing jouk n nou kalkile pwodwi a. Se konsa, de fonksyon sa yo, ankò, fè egzakteman menm bagay la. Men, yo pa fè l 'nan egzakteman menm jan an. 

Koulye a, li se posib yo gen plis pase yon baz ka oswa plis pase yon repetitif ka, tou depann sou sa ki fonksyon ou ap eseye fè. Ou pa nesesèman jis limite a sa sèlman yon ka baz yon selibatè oubyen yon repetitif sèl ka. Se konsa, yon egzanp nan yon bagay ak ka baz miltip ta kapab nan sa a men Fibonacci sekans kantite. 

Ou ka sonje soti nan jou lekòl primè ki sekans ki Fibonacci defini tankou sa a men eleman nan premye se 0. Eleman nan dezyèm se 1. Tou de nan moun ki yo se jis pa definisyon. 

Lè sa a, se chak eleman lòt defini kòm sòm total la nan n mwens 1 ak n mwens 2. Se konsa, eleman nan twazyèm ta dwe 0 plis 1 se 1. Lè sa a, eleman nan katriyèm ta dwe eleman, dezyèm lan, 1, plis eleman nan twazyèm, 1. Apre sa, ki ta ka 2. Yo ak sou sa ak sou sa. 

Se konsa, nan ka sa a, nou gen de ka baz. Si n se egal a 1, retounen 0. Si n se egal a 2, retounen 1. Sinon, retounen Fibonacci nan n mwens 1 plis Fibonacci nan n mwens 2. 

Se konsa, sa a, se ka baz miltip. Ki sa ki sou plizyè ka repetitif? Oke, gen nan yon bagay rele konjekti a Collatz. Mwen pa pwal di, ou konnen ki sa se sa ki, paske li la aktyèlman final nou an pwoblèm pou videyo sa a an patikilye. Lè li nan fè egzèsis nou an nan travay sou yo ansanm. 

Se konsa, isit la nan sa a Collatz konjekti is-- li aplike a chak nonb antye relatif pozitif. Epi, se ipotèz ke li nan toujou posib jwenn tounen a 1 si ou swiv etap sa yo. Si n se 1, sispann. Nou te gen tounen nan 1 si n se 1. 

Sinon, ale nan sa a pwosesis ankò sou n divize pa 2. Apre sa, wè si ou kapab jwenn tounen nan 1. Sinon, si n se enpè, ale nan pwosesis sa a ankò sou 3n plis 1, oswa 3 fwa n plis 1. Se konsa, isit la nou gen yon ka baz sèl. Si n se egal a 1, sispann. Nou pa ap fè nenpòt rkursyon plis. 

Men, nou gen de ka repetitif. Si n se menm, nou fè yon sèl repetitif ka, lè w rele n divize pa 2. Si n se enpè, nou fè yon diferan repetitif ka sou 3 fwa n plis 1. 

Se konsa, objektif la pou videyo sa a se pran yon dezyèm fwa, pran yon poz videyo a, epi eseye epi ekri sa a fonksyon repetitif Collatz kote ou pase nan yon n valè, ak li kalkile ki jan anpil etap li pran pou li ale nan 1 si ou kòmanse soti nan n epi ou swiv moun etap moute pi wo a. Si n se 1, li pran 0 etap. Sinon, li k ap pase yo pran yon sèl etap plis sepandan anpil etap li pran sou chak n divize pa 2 si n se menm, oswa 3n plis 1 si n se enpè. 

Koulye a, mwen te mete moute sou ekran an isit la yon koup de bagay sa yo tès pou ou, yon koup nan tès ka pou ou, yo wè sa divès kalite nimewo Collatz sa yo, se, epi tou li yon ilistrasyon nan etap sa yo ki bezwen yo dwe ale nan se konsa ou kapab sòt de wè pwosesis sa a nan aksyon. Se konsa, si n se egal a 1, Collatz nan n se 0. Ou pa dwe fè anyen yo jwenn tounen nan 1. Ou se deja la. 

Si n se 2, li pran yon sèl etap pou li ale nan 1. Ou kòmanse ak 2. Oke, 2 se pa egal a 1. Se konsa, li k ap pase yo dwe youn etap plis sepandan anpil etap li pran sou n divize pa 2. 

2 divize pa 2 se 1. Se konsa, li pran yon sèl etap plis sepandan anpil etap li pran pou 1. 1 pran zewo etap. 

Pou 3, jan ou ka wè, gen nan byen yon kèk etap enplike nan sa. Ou ale soti nan 3. Lè sa a, ou ale nan 10, 5, 16, 8, 4, 2, 1. Li pran sèt etap sa yo jwenn tounen nan 1. Ak jan ou ka wè, gen nan yon koup ka tès lòt isit la li teste soti pwogram ou an. Se konsa, ankò, pran yon poz videyo a. Apre sa, mwen pral ale so tounen kounye a sa pwosesis aktyèl la se isit la, sa konjekti sa a se. 

Gade wè si ou kapab konnen ki Ki jan yo defini Collatz nan n konsa ke li kalkile ki jan anpil etap li pran pou li ale nan 1. Se konsa, èspere ke, ou te Sarepta videyo a epi w ap pa sèlman ap tann pou m ' l 'ban nou repons lan isit la. Men, si ou se, byen, isit la nan repons lan de tout fason. 

Se konsa, isit la nan yon definisyon posib nan fonksyon an Collatz. Baz nou case-- si n se egal a 1, nou retounen 0. Li pa pran okenn etap sa yo jwenn tounen nan 1. 

Sinon, nou gen de repetitif cases-- yonn pou nimewo menm ak yonn pou enpè. Wout la mwen teste pou chif menm se tcheke si n mod 2 egal 0. Sa a se fondamantalman, ankò, mande kesyon an, si ou sonje sa mod is-- si mwen divize n pa 2 pa gen rès? Ki ta ka yon nimewo menm. 

Se konsa, si n mod 2 egal 0 se tès sa a yon nimewo menm. Si se konsa, mwen vle retounen 1, paske sa a se definitivman pran yon sèl etap plis Collatz a tou sa nonb ki se mwatye nan m '. Sinon, mwen vle retounen 1 plis Collatz a 3 fwa n plis 1. Sa ki te lòt la repetitif etap ke nou te kapab pran yo kalkile an Collatz-- ki kantite etap li pran yo jwenn tounen nan 1 ba w yon kantite. Se konsa, èspere ke, egzanp sa a te ban nou yon ti jan a yon gou nan pwosedi repetitif. Èspere ke, ou panse se yon Kòd ti kras pi bèl si aplike nan yon elegant, fason repetitif. Men, menm si se pa, se yon rkursyon reyèlman pwisan zouti Alòske. Se konsa, li la definitivman yon bagay yo ka resevwa tèt ou alantou li, paske ou pral kapab kreye pwogram trè fre lè l sèvi avèk rkursyon ki ta ka otreman dwe konplèks yo ekri si w ap itilize pasan ak iterasyon. Mwen se Doug Lloyd. Sa a se CS50.