[CHWARAE CERDDORIAETH] 

DOUG LLOYD: Mae'n debyg y byddwch yn meddwl bod cod yn unig ei ddefnyddio i gyflawni tasg. Byddwch yn ysgrifennu 'ii maes. Mae'n gwneud rhywbeth. Dyna 'n bert lawer iddo. 

Rydych yn llunio ei. Rydych yn rhedeg y rhaglen. Rydych yn dda i fynd. 

Ond credwch neu beidio, os rydych cod am amser hir, chi mewn gwirionedd efallai yn dod i weld cod fel rhywbeth sy'n hardd. Y mae'n eu datrys problem mewn yn ffordd ddiddorol iawn, neu os oes dim ond rhywbeth gwirioneddol daclus am y ffordd y mae'n edrych. Efallai eich bod yn chwerthin arna i, ond mae'n wir. Ac recursion yn un ffordd i fath o gael syniad hwn o hardd cod, cain sy'n edrych. Y mae'n eu datrys problemau mewn ffyrdd sy'n yn ddiddorol, yn hawdd i ddychmygu, ac yn rhyfeddol byr. 

Mae'r gwaith ffordd recursion yw, yn swyddogaeth ailadroddus ei ddiffinio fel swyddogaeth sy'n galw ei hun fel rhan o'i weithredu. Gall hyn ymddangos ychydig yn od, a byddwn yn gweld ychydig am sut mae hyn yn gweithio mewn munud. Ond unwaith eto, mae'r rhain yn gweithdrefnau recursive yn mynd i fod mor gain oherwydd eu bod yn mynd i ddatrys y broblem heb gael yr holl swyddogaethau eraill hyn neu dolenni hir hyn. Byddwch yn gweld bod y rhain recursive gweithdrefnau yn mynd i edrych mor fyr. Ac maent yn wir yn mynd i wneud eich cod edrych yn llawer yn fwy prydferth. 

'N annhymerus' roi enghraifft i chi o hyn i weld sut Gallai trefn ailadroddus gael eu diffinio. Felly os ydych yn gyfarwydd â hyn o ddosbarth mathemateg flynyddoedd lawer yn ôl, mae rhywbeth yn cael ei alw y swyddogaeth ffactoraidd, sydd fel arfer yn ddynodwyd fel pwynt ebychnod, a oedd yn Diffinnir dros pob cyfanrif positif. A'r ffordd y mae n ffactoraidd yn cael ei gyfrifo yn eich lluosi pob un mae'r niferoedd yn llai na neu'n hafal i together-- n yr holl rif cyfan llai na neu'n hafal i n gilydd. 

Felly 5 ffactoraidd yn 5 gwaith 4 gwaith 3 gwaith 2 waith 1. A 4 ffactoraidd yw 4 gwaith 3 gwaith 2 waith 1 ac yn y blaen. Byddwch yn cael y syniad. 

Fel rhaglenwyr, nid ydym yn ei wneud defnyddiwch n, pwynt ebychnod. Felly, byddwn yn diffinio'r ffactoraidd swyddogaeth fel ffaith o n. A byddwn yn defnyddio ffactoraidd i greu ateb recursive i broblem. Ac yr wyf yn meddwl y gallech ddod o hyd ei fod yn llawer mwy ar eu golwg apelio na'r ailadroddol Fersiwn o hyn, a oedd yn byddwn hefyd yn edrych ar mewn munud. 

Felly dyma gwpl o pun facts-- intended-- am factorial-- y swyddogaeth ffactoraidd. Mae ffactorial o 1, fel y dywedais, yw 1. Mae ffactor o 2 yw 2 gwaith 1. Mae ffactor o 3 yw 3 Amseroedd 2 waith 1, ac yn y blaen. Rydym yn siarad am 4 a 5 yn barod. 

Ond o edrych ar hyn, nid yw hyn yn wir? Onid yw ffactorial o 2 yn unig 2 waith ffactorial 1? Yr wyf yn golygu, ffactorial 1 yw 1. Felly ni all pam yr ydym yn unig yn dweud bod, ers ffactoraidd o 2 yw 2 waith 1, 'i' 'n sylweddol dim ond 2 waith ffactorial 1? 

Ac yna ymestyn y syniad hwnnw, Nid yw ffactoraidd o 3 dim ond 3 gwaith ffactorial 2? Ac ffactorial 4 yw 4 gwaith ffactorial 3, ac yn y blaen? Yn wir, mae'r ffactoraidd o unrhyw rif y gall dim ond gael eu mynegi os ydym yn garedig o gwneud hyn am byth. Gallwn fath o gyffredinoli y broblem ffactoraidd gan ei fod yn amseroedd n y ffactorial n minws 1. Mae'n n gwaith yn gynnyrch yr holl rifau llai na fi. 

Mae'r syniad hwn, mae hyn yn cyffredinoli o'r broblem, yn ein galluogi i recursively diffinio'r swyddogaeth ffactoraidd. Pan fyddwch yn diffinio swyddogaeth recursively, mae ddau beth y mae angen i fod yn rhan ohono. Mae angen i chi gael rhywbeth a elwir yn achos sylfaenol, sydd, pan fyddwch yn sbarduno hynny, Bydd atal y broses ailadroddus. 

Fel arall, mae swyddogaeth sy'n galw itself-- fel y byddech yn imagine-- allai fynd ymlaen am byth. Swyddogaeth yn galw y swyddogaeth galwadau y galwadau swyddogaeth y swyddogaeth yn galw y swyddogaeth. Os nad oes gennych ffordd i'w atal, eich rhaglen Bydd yn cael ei sownd yn effeithiol mewn dolen ddiddiwedd. Bydd yn damwain yn y pen draw, oherwydd bydd yn rhedeg allan o gof. Ond dyna ymyl y pwynt. 

Mae angen i ni gael rhyw ffordd arall i roi'r gorau pethau heblaw ein chwilfriwio rhaglen, oherwydd bod rhaglen sy'n damweiniau yn Mae'n debyg na hardd neu cain. Ac felly rydym yn galw hyn yr achos sylfaenol. Mae hwn yn ateb syml i broblem sy'n atal y broses ailadroddus rhag digwydd. Felly dyna un rhan o swyddogaeth ailadroddus. 

Mae'r ail ran yn wir ailadroddus. A dyma lle mae'r recursion Bydd yn digwydd. Dyma lle mae'r Bydd swyddogaeth galw ei hun. 

Ni fydd yn galw ei hun yn union yr un ffordd y cafodd ei alw. Bydd yn amrywiad bach ar sy'n gwneud y broblem 'i' yn ceisio datrys ychydig teeny llai. Ond yn gyffredinol mae'n pasio baich o ddatrys y rhan fwyaf o'r ateb i alwad gwahanol i lawr y lein. 

Pa un o'r edrych hyn fel yr achos sylfaenol yma? Pa un o'r rhain yn edrych fel y ateb symlaf i broblem? Mae gennym griw o factorials, a gallem barhau mynd on-- 6, 7, 8, 9, 10, ac yn y blaen. 

Ond un o steiliau hyn fel achos da i fod yn achos sylfaenol. Mae'n ateb syml iawn. Nid oes rhaid i ni wneud unrhyw beth arbennig. 

Mae ffactoraidd o 1 yn unig yw 1. Nid oes rhaid i ni wneud unrhyw lluosi o gwbl. Mae'n ymddangos fel pe ydym yn mynd i geisio datrys y broblem hon, ac mae angen i ni atal y recursion yn rhywle, mae'n debyg am roi'r gorau pan gawn i 1. Nid ydym am i roi'r gorau cyn hynny. 

Felly, os ydym yn diffinio ein swyddogaeth ffactoraidd, dyma sgerbwd ar gyfer sut y gallwn wneud hynny. Mae angen i ni dopio mewn dwy rhai things-- yr achos sylfaenol a'r achos ailadroddus. Beth yw'r achos sylfaenol? Os yw n yn hafal i 1, dychwelyd 1-- dyna broblem wirioneddol syml i'w datrys. 

Mae ffactoraidd o 1 yw 1. Dyw hi ddim yn 1 amserau unrhyw beth. Dim ond 1. Mae'n ffaith hawdd iawn. Ac felly gall hynny fod yn ein achos sylfaenol. Os byddwn yn cael eu pasio i mewn i hyn 1 swyddogaeth, byddwn yn jyst yn dychwelyd 1. 

Beth yw'r dychweliadol yn ôl pob tebyg achos yn edrych? Ar gyfer pob rhif arall eithr 1, beth yw'r patrwm? Wel, os ydym yn cymryd ffactorial n, 'i' amseroedd n ffactorial n minws 1. 

Os ydym yn cymryd y ffactorial o 3, 'i' 3 gwaith y ffactorial o 3 minws 1, neu 2. Ac felly os nad ydym yn gan edrych ar 1, fel arall Amseroedd dychwelyd n y ffactorial n minws 1. Mae'n eithaf syml. 

Ac er mwyn cael ychydig yn glanach a chod mwy cain, gwybod os ydym wedi ddolenni-lein sengl neu un-lein canghennau amodol, gallwn gael gwared ar bob un o'r bresys cyrliog o'u cwmpas. Felly, gallwn atgyfnerthu'r hyn at hyn. Mae hyn wedi union yr un fath ymarferoldeb fel hyn. 

Im 'jyst yn cymryd i ffwrdd y cyrliog bresys, oherwydd dim ond un llinell tu mewn canghennau amodol hynny. Felly mae'r rhain yn ymddwyn yn union yr un fath. Os yw n yn hafal i 1, dychwelyd 1. Fel arall dychwelyd amseroedd n ffactorial n minws 1. Felly, rydym yn gwneud y broblem yn llai. Os yw n dechrau allan fel 5, rydym yn mynd i dychwelyd 5 gwaith yr ffactoraidd o 4. A byddwn yn gweld mewn munud pan fyddwn yn sôn am y stack-- galw i mewn 'n fideo arall lle rydym yn siarad am y ffoniwch stack-- byddwn yn dysgu ynghylch pam yn union y broses hon yn gweithio. 

Ond er bod ffactoraidd o 5 yn dweud dychwelyd 5 gwaith ffactoraidd o 4, a 4 yn mynd i ddweud, OK, wel, yn dychwelyd 4 gwaith y ffactoraidd o 3. Ac fel y gwelwch, rydym yn math o agosáu 1. Rydym yn mynd yn agosach a yn nes at yr achos sylfaenol. 

Ac ar ôl i ni gyrraedd yr achos sylfaenol, holl swyddogaethau blaenorol cael yr ateb eu bod yn chwilio am. Roedd ffactorial o 2 yn dweud yn dychwelyd 2 waith y ffactoraidd o 1. Wel, ffactoraidd o 1 yn dychwelyd 1. Felly yr alwad am ffactoraidd Gall o 2 yn dychwelyd 2 waith 1, ac yn rhoi bod yn ôl i ffactoraidd o 3, sydd yn aros am y canlyniad. 

Ac yna gall gyfrifo ei ganlyniad, 3 gwaith 2 yw 6, ac yn rhoi yn ôl i ffactor o 4. Ac eto, mae gennym fideo ar y pentwr alwad lle mae hyn yn cael ei ddangos ychydig mwy na'r hyn yr wyf ddim yn dweud ar hyn o bryd. Ond mae hyn yn ei. Hyn yn unig yw'r ateb i cyfrifo ffactorial o nifer. 

Dim ond pedair llinell o god. Dyna 'n bert oera, dde? Mae'n fath o sexy. 

Felly, yn gyffredinol, ond nid bob amser, swyddogaeth ailadroddus Gall gymryd lle dolen mewn swyddogaeth heb fod yn ailadroddus. Felly dyma, ochr yn ochr, yw'r iterus fersiwn o'r swyddogaeth ffactoraidd. Mae'r ddau o'r rhain yn cyfrifo yn union yr un peth. 

Mae'r ddau yn cyfrifo ffactorial n. Mae'r fersiwn ar y chwith defnyddio recursion i wneud hynny. Mae'r fersiwn ar y dde defnyddio iteriad i wneud hynny. 

A rhybudd, mae'n rhaid i ni ddatgan newidyn cynnyrch cyfanrif. Ac yna rydym yn ddolen. Cyn belled â n yn fwy na 0, rydym cadw lluosi cynnyrch hwnnw gan n a decrementing n nes rydym yn cyfrifo'r cynnyrch. Felly mae'r rhain ddwy swyddogaeth, unwaith eto, gwneud yn union yr un peth. Ond nid ydynt yn gwneud hynny mewn yn union yr un ffordd. 

Yn awr, mae'n bosibl gael mwy nag un ganolfan achos neu fwy nag un achos recursive, yn dibynnu ar beth yw eich swyddogaeth yn ceisio ei wneud. Nid ydych yn o angenrheidrwydd yn unig yn gyfyngedig i achos sylfaenol unigol neu dychweliadol sengl achos. Felly enghraifft o rywbeth gydag achosion sylfaenol lluosog allai fod this-- y Dilyniant rhif Fibonacci. 

Efallai y cofiwch o niwrnod ysgol elfennol bod y dilyniant Fibonacci ei ddiffinio fel this-- yr elfen gyntaf yw 0. Yr ail elfen yw 1. Mae'r ddau o'r rheiny yn unig trwy ddiffiniad. 

Yna bob elfen arall yn cael ei ddiffinio fel swm minws n 1 ac n minws 2. Felly mae'r drydedd elfen fyddai 0 ac 1 yn 1. Ac yna y bedwaredd elfen fyddai'r ail elfen, 1, yn ogystal â'r drydedd elfen, 1. A byddai hynny'n 2. Ac yn y blaen ac yn y blaen. 

Felly, yn yr achos hwn, mae gennym ddau achos sylfaen. Os yw n yn hafal i 1, yn dychwelyd 0. Os yw n yn hafal i 2, dychwelyd 1. Fel arall, yn dychwelyd Fibonacci n minws 1 plws Fibonacci n minws 2. 

Felly dyna achosion sylfaen lluosog. Beth am achosion recursive lluosog? Wel, mae rhywbeth Gelwir y dyfalu Collatz. Dydw i ddim yn mynd i ddweud, eich bod yn gwybod beth yw hwnnw, am ei fod mewn gwirionedd yn ein derfynol broblem ar gyfer y fideo penodol. Ac mae'n ein hymarfer i weithio ar y cyd. 

Felly, dyma beth mae'r Collatz dyfaliad yw-- mae'n berthnasol i bob cyfanrif positif. Ac mae'n dyfalu ei fod yn bob amser yn bosibl i fynd yn ôl i 1 os byddwch yn dilyn y camau hyn. Os yw n yw 1, roi'r gorau iddi. Rydym wedi mynd yn ôl i 1 os yw n 1. 

Fel arall, ewch drwy hyn broses eto ar n rhannu â 2. A gweld os allwch chi fynd yn ôl i 1. Fel arall, os n yn od, yn mynd drwy y broses hon unwaith eto ar 3n ac 1, neu 3 gwaith n plws 1. Felly dyma mae gennym achos sail unigol. Os yw n yn hafal i 1, roi'r gorau iddi. Nid ydym yn gwneud unrhyw mwy recursion. 

Ond mae gennym ddau achos recursive. Os yw n hyd yn oed, rydym yn ei wneud yn un ailadroddus achos, gan alw wedi'i rannu gan 2 n. Os yw n yn od, rydym yn gwneud gwahanol achos recursive ar 3 gwaith n plws 1. 

Ac felly y nod ar gyfer fideo hwn yw i gymryd ail, oedi y fideo, ac yn ceisio ysgrifennu hyn swyddogaeth recursive Collatz lle byddwch yn mynd heibio mewn gwerth a n, a mae'n cyfrifo faint o gamau y mae'n gymryd i fynd i 1 os ydych yn dechrau o n ac eich bod yn dilyn y camau hynny i fyny uchod. Os yw n yw 1, mae'n cymryd camau 0. Fel arall, mae'n mynd i cymryd un cam yn ogystal, fodd bynnag mae llawer o gamau y mae'n ei gymryd ar y naill n wedi'i rannu â 2 os n yn oed, neu 3n ac 1 os n yn od. 

Yn awr, rydw i wedi rhoi i fyny ar y sgrin yma un neu ddau o bethau brawf ar eich cyfer, un neu ddau o achosion, profion ar gyfer chi, i weld beth amrywiol hyn rifau Collatz yw, a hefyd darlun o'r camau y Mae angen mynd drwy fel y gallwch math o weld y broses hon ar waith. Felly os n yn hafal i 1, Collatz o n yw 0. Nid oes rhaid i chi ei wneud unrhyw beth i fynd yn ôl i 1. Rydych yno eisoes. 

Os yw n yw 2, mae'n cymryd un cam i gyrraedd 1. Byddwch yn dechrau gyda 2. Wel, nid yw 2 yn hafal i 1. Felly, mae'n mynd i fod yn un cam yn ogystal â faint bynnag o gamau y mae'n yn cymryd ar rhannu'n n â 2. 

2 wedi'i rannu â 2 yw 1. Felly, mae'n cymryd un cam yn ogystal, fodd bynnag mae llawer o gamau y mae'n ei gymryd ar gyfer 1. 1 yn cymryd camau sero. 

Ar gyfer 3, fel y gwelwch, mae yna eithaf ychydig o gamau sy'n gysylltiedig. Rydych yn mynd o 3. Ac yna byddwch yn mynd i 10, 5, 16, 8, 4, 2, 1. Mae'n cymryd saith cam i fynd yn ôl i 1. Ac fel y gwelwch, mae 'na cwpl achosion prawf eraill yma i brofi eich rhaglen. Felly unwaith eto, oedi y fideo. A byddaf yn mynd neidio yn ôl yn awr i beth mae'r broses ei hun yn fan hyn, pa dyfalu yw hyn. 

Weld a allwch chi chyfrif i maes sut i ddiffinio Collatz o n fel ei fod yn cyfrifo faint o camau y mae'n ei gymryd i gyrraedd 1. Felly, gobeithio, yr ydych wedi seibio y fideo ac nid ydych yn unig yn aros i mi i roi'r ateb i chi yma. Ond os ydych chi, yn dda, dyma yw'r ateb beth bynnag. 

Felly dyma ddiffiniad posibl y swyddogaeth Collatz. Mae ein sylfaen achos-- os n yn yn hafal i 1, byddwn yn dychwelyd 0. Nid yw'n cymryd unrhyw camau i fynd yn ôl i 1. 

Fel arall, mae gennym ddau cases-- recursive un ar gyfer eilrifau ac un ar gyfer od. Y ffordd yr wyf yn profi ar gyfer rhifau hyd yn oed yw i gadarnhau a oes n mod 2 yn dychwelyd 0. Mae hyn yn y bôn, unwaith eto, gofyn y cwestiwn, os cofiwch yw-- beth mod os byddaf rhannu n â 2 yw nad oes gweddill? Byddai hynny yn eilrif. 

Ac felly os n mod 2 yn dychwelyd 0 yw profi a yw hyn yn eilrif. Os felly, yr wyf am ddychwelyd 1, oherwydd mae hyn yn bendant gan gymryd un cam yn ogystal Collatz o pa bynnag rhif yn hanner mi. Fel arall, yr wyf am ddychwelyd 1 yn ogystal â Collatz o 3 gwaith n plws 1. Dyna oedd y llall cam recursive ein bod yn Gallai cymryd i gyfrifo'r Collatz-- nifer o gamau mae'n ei gymryd i fynd yn ôl i 1 Rhoddir rhif. Felly, gobeithio, yr enghraifft hon Rhoddodd ychydig bach i chi o flas o weithdrefnau ailadroddus. Gobeithio, yn eich barn chi cod yn ychydig yn fwy prydferth os cânt eu gweithredu mewn, ffordd ailadroddus cain. Ond hyd yn oed os na, recursion yn arf pwerus iawn serch hynny. Ac felly mae'n bendant yn rhywbeth i gael eich pen o gwmpas, oherwydd byddwch yn gallu creu rhaglenni 'n bert oera gan ddefnyddio recursion a allai fel arall fod yn gymhleth i ysgrifennu os ydych yn defnyddio dolenni a ailadrodd. Rwy'n Doug Lloyd. Mae hyn yn CS50.