[TÓNLIST spila] 

DOUG LLOYD: Þú heldur líklega að númerið er bara notað til að ná í verkefni. Þú skrifar það út. Það gerir eitthvað. Það er ansi mikið það. 

Þú þýða það. Þú keyrir forritið. Þú ert góður til fara. 

En trúið því eða ekki, ef þú kóða í langan tíma, þú í raun gæti komið að sjá númer sem eitthvað sem er fallegt. Það leysa vandamál í mjög áhugaverð leið, eða það er bara eitthvað virkilega sniðugt um hvernig það lítur út. Þú gætir verið að hlæja á mig, en það er satt. Og endurkvæmni er ein leið til að raða á að fá þessa hugmynd af falleg, glæsilegur-útlit númer. Það leysir vandamál á þann hátt sem eru áhugaverð, auðvelt að sjón, og furðu stutt. 

The vegur endurkvæmni verk er, a endurkvæma virka er skilgreind sem fall sem kallar sig sem hluta af framkvæmd hennar. Það kann að virðast svolítið skrítið, og við munum sjá smá um hvernig þetta virkar í smá stund. En aftur, þetta endurkvæma aðferðir eru að fara að vera svo glæsilegur vegna þess að þeir eru að fara til að leysa þetta vandamál án þess hafa allar þessar aðrar aðgerðir eða þessar lengi lykkjur. Þú munt sjá að þetta endurkvæma aðferðir við að líta svo stutt. Og þeir raunverulega eru að fara að gera númerið þitt líta mikið fallegri. 

Ég skal gefa ykkur dæmi þetta til að sjá hvernig endurkvæma aðferð má skilgreina. Svo ef þú ert kunnuglegur með þetta frá stærðfræði bekknum mörgum árum, Það er eitthvað sem kallast þáttatilraun virka, sem er yfirleitt táknað sem upphrópunarmerki, sem er skilgreind á allar jákvæðar heiltölur. Og hvernig sem n þáttatilraun er reiknað er þú margfaldar allt tölurnar minna en eða jafnt og n together-- allar heiltölur minna en eða jafnt n saman. 

Svo er 5 þáttatilraun 5 sinnum 4 sinnum 3 sinnum 2 sinnum 1. Og 4 þáttatilraun er 4 sinnum 3 sinnum 2 sinnum 1 og svo framvegis. Þú færð þá hugmynd. 

Sem forritari, eigum við ekki nota n, upphrópunarmerki. Þannig að við munum skilgreina þáttatilraun virka eins og staðreynd n. Og við munum nota þáttatilraun að búa endurkvæma lausn á vandamáli. Og ég held að þú gætir fundið að það er mikið meira sjónrænt aðlaðandi en endurtekningu útgáfa af þessu, þar sem við munum einnig taka a líta á í smá stund. 

Svo hér eru nokkrar facts-- orðaleikur intended-- um factorial-- á þáttatilraun virka. The þáttatilraun 1, eins og ég sagði, er 1. The þáttatilraun af 2 er 2 sinnum 1. Aðfeldi 3 er 3 sinnum 2 sinnum 1, og svo framvegis. Við ræddum um 4 og 5 þegar. 

En að horfa á þetta, er þetta ekki satt? Er ekki þáttatilraun af 2 bara 2 sinnum aðfeldi 1? Ég meina, þáttatilraun af 1 er 1. Svo hvers vegna getum við ekki bara sagt það, þar þáttatilraun af 2 er 2 sinnum 1, það er í raun bara 2 sinnum aðfeldi 1? 

Og þá nær þessi hugmynd, er ekki þáttatilraun af 3 bara 3 sinnum aðfeldi 2? Og þáttatilraun af 4 er 4 sinnum aðfeldi 3, og svo framvegis? Í staðreynd, the þáttatilraun af hvaða númer getur bara gefin ef vér góður af bera þetta út að eilífu. Við getum konar alhæfa þáttatilraun vandamál Eins og það er n sinnum þáttatilraun n mínus 1. Það er n sinnum afurð allar tölur minna en mig. 

Þessi hugmynd, þetta alhæfing af vandamálinu, gerir okkur kleift að endurkvæmt skilgreina þáttatilraun virka. Þegar þú skilgreint fall endurkvæmt, það er tveir hlutir sem þarf að vera hluti af því. Þú þarft að hafa eitthvað sem kallast stöð að ræða, sem, þegar þú kalla það, mun stoppa endurkvæma aðferð. 

Annars fall sem kallar itself-- eins og þú might imagine-- gæti haldið áfram að eilífu. Virka símtöl aðgerðina kallar virka símtöl virka kallar virka. Ef þú ert ekki með leið til að stöðva það, program verður í raun fastur á óendanlega lykkju. Það verður hrun á endanum, vegna þess að það verður keyrt út af minni. En það er við hliðina á benda. 

Við þurfum að hafa einhverja aðra leið til að stöðva það auki program hrun okkar, vegna þess að forrit sem hrun er sennilega ekki fallegt eða glæsilegt. Og svo við köllum þetta stöð raunin. Þetta er einföld lausn á vandamáli sem stoppar endurkvæma aðferð frá viðburður. Svo er það einn hluti af endurkvæma virka. 

Seinni hluti er endurkvæma raunin. Og þetta er þar sem endurkvæmni mun í raun fara fram. Þetta er þar sem aðgerð mun kalla sig. 

Það mun ekki kalla sig í nákvæmlega á sama hátt og það var kallað. Það verður smávægileg breyting sem gerir vandamál það er reyna að leysa a teeny aðeins minni. En það fer yfirleitt peninginn að leysa megnið af lausninni í annan hringja niður í línu. 

Hver af þessum útlit eins grunn tilfelli hér? Hver einn af þessum lítur út eins og Einfaldasta lausnin á vandamáli? Við höfum fullt af factorials, og við gátum haldið áfram fara on-- 6, 7, 8, 9, 10, og svo framvegis. 

En einn af þessum lítur út eins og gott mál að vera undirstaða raunin. Það er mjög einföld lausn. Við þurfum ekki að gera neitt sérstakt. 

Aðfeldi 1 er bara 1. Við þurfum ekki að gera eitthvað margföldun á öllum. Það virðist eins og ef við erum að fara til að reyna að leysa þetta vandamál, og við þurfum að stöðva endurkvæmni einhvers staðar, við viljum líklega að hætta það þegar við komum til 1. Við viljum ekki að hætta áður. 

Þannig að ef við erum að skilgreina þáttatilraun virka okkar, hér er beinagrind fyrir hvernig við gætum gert það. Við þurfum að stinga í þær tvær things-- grunn tilfelli og endurkvæma raunin. Hvað er stöð málið? Ef n er jafnt og 1, að fara aftur 1-- það er mjög einfalt vandamál að leysa. 

The þáttatilraun af 1 er 1. Það er ekki 1 sinni neitt. Það er bara 1. Það er mjög auðvelt staðreynd. Og svo að hægt er að byggja mál vor. Ef við fá liðið 1 inn í þetta virka, við verðum bara að fara aftur 1. 

Hvað er endurkvæma Málið sennilega líta út? Fyrir hvert annað númer auk 1, hvað er mynstur? Jæja, ef við erum að taka þáttatilraun n, það er n sinnum þáttatilraun n mínus 1. 

Ef við erum að taka þáttatilraun af 3, það er 3 sinnum þáttatilraun af 3 mínus 1, eða 2. Og svo ef við erum ekki horfa á 1, annars Arðsemi n sinnum þáttatilraun n mínus 1. Það er frekar einfalt. 

Og fyrir sakir þess að hafa örlítið hreinni og glæsilegur númer, vita að ef við höfum einn-lína lykkjur eða einn-lína skilyrt útibú, við getum að losna við allt í hrokkið axlabönd kringum þá. Þannig að við getum styrkja þetta að þessu. Þetta hefur nákvæmlega sömu virkni og þetta. 

Ég ætla bara að taka í burtu hrokkið axlabönd, því það er bara ein lína inni af þeim skilyrt greinum. Svo þetta hegða samur. Ef n er jafnt og 1, skila 1. Annars aftur n sinnum þáttatilraun n mínus 1. Þannig að við erum að gera vandamálið minna. Ef n byrjar sem 5, við erum að fara að aftur 5 sinnum aðfeldi 4. Og við munum sjá í eina mínútu þegar við tölum um kalla stack-- í öðru vídeó þar sem við tölum um kalla stack-- lærum um hvers vegna þetta ferli virkar. 

En á meðan þáttatilraun af 5 segir aftur 5 sinnum þáttatilraun af 4, og 4 er að fara að segja, OK, vel, aftur 4 sinnum þátta af 3. Og eins og þú sérð, við erum konar nálgast 1. Við erum að fá nær og nær að grunn tilfelli. 

Og þegar við högg grunn tilfelli, allar fyrri aðgerðir hafa svarið sem þeir voru að leita að. Factorial af 2 var að segja aftur 2 sinnum aðfeldi 1. Jæja, þáttatilraun af 1 skilar 1. Svo kalla Hrópmerkt af 2 getur aftur 2 sinnum 1, og gefa það aftur til aðfeldi 3, sem er að bíða eftir að niðurstöðu. 

Og þá er það er hægt að reikna þess vegna, 3 sinnum 2 er 6, og gefa það aftur til Hrópmerkt af 4. Og aftur, höfum við vídeó á símtali mánudaginn þar sem þessi er sýnd smá meira en það sem ég er að segja núna. En þetta er það. Þetta eitt og sér er lausn á reikna aðfeldi tölu. 

Það er aðeins fjórum línum af kóða. Það er laglegur kaldur, ekki satt? Það er góður af kynþokkafullur. 

Svo almennt, en ekki alltaf, endurkvæma virka Hægt er að skipta lykkju a ekki endurkvæma virka. Svo hér, hlið við hlið, er endurtekningu útgáfa af þátta virka. Báðir þessir Reikna nákvæmlega það sama. 

Þeir báðir reikna aðfeldi n. The útgáfa á vinstri notar endurkvæmni til að gera það. The útgáfa á hægri notar endurtekning til að gera það. 

Og takið eftir, verðum við að lýsa a breyta heiltala vara. Og þá erum við lykkja. Svo lengi sem n er stærra en 0, við halda að margfalda þá vöru af N og decrementing n til við reiknum vöruna. Svo þessar tvær aðgerðir, aftur, gera nákvæmlega það sama. En þeir gera það ekki í nákvæmlega sama hátt. 

Nú, það er hægt að hafa fleiri en einn basa tilvik eða fleiri en eitt endurkvæma ræða, eftir á hvaða virka er að reyna að gera. Þú ert ekki endilega bara takmarkað við einni stöð ræða eða eitt endurkvæma ræða. Svo dæmi um eitthvað með mörgum tilfellum grunn gæti verið this-- að Fibonacci talnarunu. 

Þú getur muna frá grunnskólabörn daga skóla að Fibonacci raðar er skilgreind eins this-- fyrsti þátturinn er 0. Annað þáttur er 1. Bæði af þeim eru bara með skilgreiningu. 

Þá annað hvert frumefni er skilgreint sem summa n mínus 1 og n mínus 2. Svo þriðja þáttur væri 0 plús 1 er 1. Og þá fjórði þáttur væri annað þáttur, 1, auk Þriðji þáttur 1. Og það væri 2. Og svo framvegis og svo framvegis. 

Þannig að í þessu tilfelli, höfum við tvær grunn tilvikum. Ef n er jafnt og 1, aftur 0. Ef n er jafnt og 2, skila 1. Annars skal skila Fibonacci n mínus 1 plus Fibonacci n mínus 2. 

Svo er það margar tilvikum grunn. Hvað um margra endurkvæma tilvikum? Jæja, það er eitthvað kallað Collatz ágiskanir. Ég ætla ekki að segja, þú veist hvað það er, vegna þess að það er í raun endanlega okkar Vandamálið fyrir þessa tilteknu vídeó. Og það er æfing okkar að vinna saman. 

Svo er hér það sem Collatz conjecture is-- það á við um sérhverja jákvæða heiltölu. Og það veltir að það er alltaf hægt að fá til baka 1 ef þú fylgir þessum leiðbeiningum. Ef n er 1, hætta. Við höfum fengið til baka 1 ef n er 1. 

Annars er farið í gegnum þetta Ferlið aftur á n deilt með 2. Og sjá hvort þú getur fengið aftur til 1. Annars, ef n er oddatala, fara í gegnum Þetta ferli aftur á 3N plús 1, eða 3 sinnum n plús 1. Svo hér höfum við einn grunn tilfelli. Ef n er jafnt og 1, hætta. Við erum ekki að gera eitthvað meira endurkvæmni. 

En við höfum tvær endurkvæma tilvikum. Ef n er jafnvel, gera við einn endurkvæma ræða, köllun n deilt með 2. Ef n er oddatala, gera við aðra endurkvæma málið á 3 sinnum N plús 1. 

Og svo markmið fyrir þetta vídeó er að taka annað, gera hlé á vídeó, og reyna að skrifa þetta endurkvæma virka Collatz þar sem þú framhjá í gildi n, og það reiknar hversu mörg skref það tekur að fá 1 ef þú byrjar frá n og þú fylgir þessum skrefum upp hér að ofan. Ef n er 1, það tekur 0 skrefum. Annars, það er að fara að taka eitt skref auk hins vegar margir stíga það tekur að annaðhvort n deilt með 2 ef n er jafnvel, eða 3n auk 1 ef n er oddatala. 

Nú, ég hef sett upp á skjánum hér a par af próf hlutum fyrir þig, a par af próf tilfelli fyrir þig, til að sjá hvað þessar mismunandi Collatz tölur eru, og einnig mynd sem sýnir af þeim skrefum sem þarf að vera farinn í gegnum svo þú getur konar sjá þetta ferli í aðgerð. Þannig að ef n er jafnt og 1, Collatz af n er 0. Þú þarft ekki að gera allt til að komast aftur til 1. Þú ert nú þegar. 

Ef n er 2, það tekur eitt skref til að fá til 1. Þú byrjar með 2. Ja, 2 er ekki jafnt og 1. Svo það er að fara að vera einu skrefi auk hins vegar margir skref IT tekur á n deilt með 2. 

2 deilt með 2 er 1. Þannig að það tekur eitt skref auk hins vegar margir stíga það tekur fyrir 1. 1 tekur núll skref. 

Fyrir 3, eins og þú geta sjá, það er alveg nokkur skref sem taka þátt. Þú ferð frá 3. Og þá fara að 10, 5, 16, 8, 4, 2, 1. Það tekur sjö skref til að komast aftur til 1. Og eins og þú geta sjá, það er nokkrar aðrar tilvikum próf hér til að prófa forritið þitt. Svo aftur, gera hlé á vídeó. Og ég ætla að fara að hoppa til baka núna til hvað í raun ferli er hér, hvað þetta conjecture er. 

Athugaðu hvort þú getur fundið út hvernig á að skilgreina Collatz á n þannig að það reiknar hversu margir skref sem það tekur að fá til 1. Svo vonandi hefur þú bið vídeó og þú ert ekki bara að bíða eftir mér til að gefa þér svarið hér. En ef þú ert vel, hér er svarið samt. 

Svo hér er hægt skilgreining af Collatz virka. Stöð okkar case-- ef n er jöfn 1, aftur við 0. Það þýðir ekki að taka eitthvað skref til að komast aftur til 1. 

Annars höfum við tvær endurkvæma cases-- einn fyrir sléttar tölur og einn fyrir skrýtið. Og ég prófa að jafnvel tölur er að athuga hvort n unga fólkið 2 jafngildir 0. Þetta er í grundvallaratriðum, aftur, spyrja spurningu, ef þú manst hvað unga fólkið is-- ef ég skipta n um 2 er engin afgangurinn? Það væri jafnvel tala. 

Og svo ef n unga fólkið 2 er 0 er próf er þetta slétt tala. Ef svo er, ég vil skila 1, vegna þess að þetta er örugglega taka eitt skref auk Collatz af hvað sem tala er helmingur af mér. Annars vil ég að skila 1 auk Collatz 3 sinnum n plús 1. Það var hinn endurkvæma skref sem við gæti tekið að reikna Collatz-- fjölda skrefa það tekur að komast aftur til 1 gefið númer. Svo vonandi, þetta dæmi gaf þér svolítið af bragð af endurkvæma málsmeðferð. Vonandi finnst þér númerið er lítið fallegri ef til framkvæmda í glæsilegri, endurkvæma hátt. En jafnvel ef ekki, endurkvæmni er mjög öflugt tól engu að síður. Og svo er það örugglega eitthvað að fá höfuðið í kring, vegna þess að þú munt vera fær til að búa til laglegur kaldur forrit með endurkvæmni sem annars gæti verið flókið að skrifa ef þú ert að nota lykkjur og ítrun. Ég er Doug Lloyd. Þetta er CS50.