ZAMYLA: Er mwyn deall recursion, rhaid i chi yn gyntaf yn deall recursion. Mae cael recursion mewn modd dylunio rhaglen eich bod wedi hunan-cyfeiriadol diffiniadau. Strwythurau data ailadroddus, er enghraifft, strwythurau data a gynnwys eu hunain mewn eu diffiniadau. Ond heddiw, rydym yn mynd i ganolbwyntio ar swyddogaethau ailadroddus. 

Dwyn i gof bod y swyddogaethau cymryd mewnbynnau, dadleuon, a dychwelyd werth fel eu allbwn a gynrychiolir gan diagram hwn yma. Byddwn yn meddwl am y blwch fel y corff o swyddogaeth, yn cynnwys set o cyfarwyddiadau sy'n dehongli'r mewnbwn a darparu allbwn. Gymryd golwg agosach y tu mewn i'r corff gallai'r swyddogaeth ddatgelu galwadau i swyddogaethau eraill hefyd. Cymerwch y swyddogaeth syml, foo, bod cymryd llinyn unigol fel mewnbwn a printiau faint o lythyrau y llinyn wedi. Mae'r strlen swyddogaeth, ar gyfer hyd llinyn, gelwir, y mae ei allbwn yn eu hangen ar gyfer yr alwad i printf. 

Yn awr, yr hyn sy'n gwneud swyddogaeth ailadroddus arbennig yw ei fod yn galw ei hun. Gall Rydym yn cynrychioli recursive hwn yn galw â'r saeth oren dolennu yn ôl i ei hun. Ond gweithredu ei hun unwaith eto yn unig y bydd gwneud yr alwad ailadroddus arall, a un arall ac un arall. Ond mae swyddogaethau recursive ni all fod yn ddiddiwedd. Maent wedi dod i ben rywsut, neu eich Bydd y rhaglen yn rhedeg am byth. 

Felly, mae angen i ni ddod o hyd i ffordd i dorri allan o'r galwadau ailadroddus. Rydym yn galw hyn yn achos sylfaenol. Pan fydd y cyflwr achos sylfaen yn cael ei fodloni, y swyddogaeth yn dychwelyd heb wneud alwad ailadroddus arall. Cymerwch y swyddogaeth hon, hi, swyddogaeth ddi-rym sy'n cymryd int n fel mewnbwn. Mae'r achos sylfaenol yn dod yn gyntaf. Os yw n yn llai na sero, is print a dychwelyd gyfer pob achos arall, mae'r Bydd swyddogaeth argraffu hi a gweithredu yr alwad ailadroddus. Alwad arall i'r swyddogaeth hi gyda gwerth mewnbwn ostwng o. 

Yn awr, er ein bod yn argraffu hi, y Ni fydd swyddogaeth yn dod i ben hyd nes y byddwn dychwelyd ei fath yn ôl, yn yr achos yn ddi-rym. Felly, ar gyfer pob n ac eithrio'r achos sylfaenol, bydd y swyddogaeth hi yn dychwelyd hi n minws 1. Gan fod y swyddogaeth hon yn ddi-rym, fodd bynnag, rydym yn Ni fydd deipio ddychwelyd yn benodol yma. Byddwn yn unig gyflawni'r swyddogaeth. Felly, galw hi (3) yn argraffu hi a gweithredu hi (2) sy'n executes hi (1) un sy'n executes hi (0), lle mae'r cyflwr achos sylfaenol yn cael ei fodloni. Felly hi (0) printiau is a ffurflenni. 

OK. Felly nawr ein bod yn deall hanfodion swyddogaethau ailadroddus, bod angen o leiaf un achos sylfaenol yn ogystal â alwad ailadroddus, gadewch i ni symud ymlaen i enghraifft mwy ystyrlon. Un nad yw'n unig yn dychwelyd ddi-rym ni waeth beth. 

Gadewch i ni edrych ar y ffactoraidd gweithredu a ddefnyddir yn fwyaf cyffredin mewn cyfrifiadau tebygolrwydd. Ffactorial n yn gynnyrch pob gyfanrif positif llai na a chyfartal i n. Pum Felly ffactoraidd 5 gwaith 4 gwaith 3 gwaith 2 waith 1 i roi 120. Pedwar ffactor yn 4 gwaith 3 gwaith 2 gwaith 1 i roi 24. Ac mae'r un rheol yn gymwys i unrhyw gyfanrif positif. 

Felly, sut y gallem ysgrifennu dychweliadol swyddogaeth sy'n cyfrifo'r ffactoraidd o nifer? Wel, bydd angen i ni ganfod y achos sylfaenol a'r galw ailadroddus. Bydd yr alwad ailadroddus fod yr un fath ar gyfer pob achos ac eithrio ar gyfer y sylfaen achos, sy'n golygu y bydd yn rhaid i ni dod o hyd i batrwm a fydd yn rhoi i ni ein canlyniad a ddymunir. 

Ar gyfer yr enghraifft, weld sut 5 ffactoraidd cynnwys lluosi 4 3 2 1 Ac yr un iawn lluosi yn dod o hyd yma, y diffiniad o 4 ffactoraidd. Felly, rydym yn gweld bod 5 ffactoraidd yn dim ond 5 gwaith 4 ffactoraidd. Nawr mae patrwm hwn yn berthnasol i 4 ffactor hefyd? Ie. Rydym yn gweld bod 4 ffactoraidd yn cynnwys y lluosi 3 gwaith 2 waith 1, mae'r yr un iawn diffiniad 3 ffactoraidd. Hynny 4 ffactoraidd yn hafal i 4 gwaith 3 ffactor, ac yn y blaen ac yn y blaen ar ein patrwm ffyn tan 1 ffactoraidd, a oedd yn trwy ddiffiniad yn hafal i 1. 

Does dim cadarnhaol eraill cyfanrifau ar ôl. Felly, rydym yn cael y patrwm ar gyfer i'n galwad ailadroddus. n ffactoraidd yn hafal i amseroedd n y ffactor n minws 1. Ac mae ein achos sylfaenol? Bydd hynny'n unig fod ein diffiniad o 1 ffactoraidd. 

Felly nawr gallwn symud ymlaen i ysgrifennu cod ar gyfer y swyddogaeth. Ar gyfer yr achos sylfaenol, bydd gennym y cyflwr n hafal hafal 1, lle byddwn yn dychwelyd 1. Yna, symud ymlaen i'r alwad ailadroddus, byddwn yn dychwelyd amseroedd n y ffactorial n minws 1. 

Nawr, gadewch i ni brofi ein hyn. Gadewch i ni geisio ffactoraidd 4. Fesul ein swyddogaeth ei fod yn gyfartal i 4 gwaith ffactoraidd (3). Ffactoraidd (3) yn hafal i 3 gwaith ffactoraidd (2). Ffactoraidd (2) yn hafal i 2 gwaith ffactoraidd (1), sy'n dychwelyd 1. Ffactoraidd (2) yn dychwelyd 2 waith 1, 2. Ffactoraidd (3) yn awr yn dychwelyd 3 gwaith 2, 6. Ac yn olaf, ffactoraidd (4) dychwelyd 4 gwaith 6, 24. 

Os ydych yn dod ar draws unrhyw anhawster â'r alwad ailadroddus, esgus bod y swyddogaeth yn gweithio'n barod. Beth allaf i ei olygu wrth hyn yw y dylech ymddiried yn eich galwadau ailadroddus i ddychwelyd gwerthoedd cywir. Er enghraifft, os wyf yn gwybod y ffactoraidd (5) yn hafal i 5 gwaith ffactoraidd (4), yr wyf i'n mynd i ymddiried yn y ffactoraidd (4) yn rhoi i mi 24. Meddyliwch am y peth fel newidyn, os ydych yn fydd, fel pe baech eisoes wedi'u diffinio ffactoraidd (4). Felly, ar gyfer unrhyw ffactoraidd (n), mae'n gynnyrch n ac y ffactoraidd flaenorol. Ac mae hyn yn ffactoraidd blaenorol yn cael ei sicrhau drwy ffonio ffactorial n minws 1. 

Yn awr, weld a allwch chi weithredu recursive weithredu eich hun. Llwytho i fyny eich terfynell, neu run.cs50.net, ac ysgrifennu swm swyddogaeth sy'n cymryd cyfanrif n ac yn dychwelyd y swm yr holl positif yn olynol chyfanrifau o n i 1. Rwyf wedi ysgrifennu allan y symiau o rai gwerthoedd i helpu chi ein. Yn gyntaf, chyfrif i maes y cyflwr achos sylfaenol. Yna, edrychwch ar swm (5). Allwch chi fynegi mewn termau o'r swm arall? Nawr, beth am swm (4)? Sut y gallwch fynegi swm (4) o ran swm arall? 

Unwaith y byddwch yn cael swm (5) a swm (4) mynegi yn nhermau symiau eraill, gweler os gallwch nodi patrwm ar gyfer swm (n). Os nad yw, rhowch gynnig ar ychydig o rifau eraill a mynegi eu symiau yn ran niferoedd arall. Drwy nodi patrymau ar gyfer arwahanol rhifau, rydych yn dda ar eich ffordd i nodi'r patrwm ar gyfer unrhyw n. 

Recursion yn arf pwerus iawn, felly, wrth gwrs nid yw'n gyfyngedig i swyddogaethau mathemategol. Gellir defnyddio recursion yn effeithiol iawn wrth ymdrin â choed er enghraifft. Edrychwch ar y byr ar goed ar gyfer mwy o adolygiad trwyadl, ond am y tro dwyn i gof bod coed chwiliad deuaidd, yn benodol, yn cynnwys nodau, pob gyda gwerth a dau awgrymiadau nod. Fel arfer, mae hyn yn ei gynrychioli gan y rhiant nod cael un pwyntio llinell at y nôd plentyn chwith ac un at y nôd plentyn cywir. Mae strwythur chwiliad deuaidd goeden yn benthyg ei hun yn dda i chwilio ailadroddus. Mae'r alwad ailadroddus naill ai yn mynd yn y chwith neu y nod iawn, ond yn fwy o hynny yn y tymor byr coed. 

Dywedwch eich bod chi eisiau i berfformio llawdriniaeth ar pob un nod mewn coeden deuaidd. Sut y gallwch fynd am hynny? Wel, gallech chi ysgrifennu dychweliadol swyddogaeth sy'n perfformio y llawdriniaeth ar y rhiant nôd ac yn gwneud dychweliadol yn galw i'r un swyddogaeth, pasio yn y chwith a nodau plentyn iawn. Er enghraifft, y swyddogaeth hon, foo, bod yn newid y gwerth nod a roddwyd ac ei holl blant i 1. Yr achos sylfaenol o achosion nod null y swyddogaeth i ddychwelyd, gan nodi nad oes unrhyw nodau ar ôl yn yr is-coed. 

Gadewch i ni gerdded trwyddo. Y rhiant cyntaf yw 13. Rydym yn newid y gwerth i 1, ac yna galw ein swyddogaeth ar y chwith, yn ogystal fel yr hawl. Mae'r swyddogaeth, foo, a elwir yn ar y chwith is-goeden gyntaf, felly y nod chwith Bydd yn cael ei symudir i 1 a foo yn cael eu galw ar blant y nod, yn yn gyntaf y chwith ac yna i'r dde, ac yn y blaen ac yn y blaen. A dweud wrthynt nad yw canghennau oes gan unrhyw mwy o blant felly mae'r un broses yn parhau ar gyfer y plant cywir hyd nes y nodau y goeden gyfan yn symudir i 1. 

Fel y gwelwch, nid ydych yn gyfyngedig i ddim ond un recursive alwad. Yn union fel y mae llawer gan y bydd yn cael y swydd ei wneud. Beth os oedd gennych coeden lle mae pob Roedd nod dri o blant, Chwith, canol, ac i'r dde? Sut fyddech chi olygu foo? Wel, yn syml. Dim ond ychwanegu alwad recursive arall ac pasio yn y pwyntydd nod canol. 

Recursion yn bwerus iawn ac i beidio â sôn am cain, ond gall fod yn gysyniad anodd ar y dechrau, felly byddwch yn cleifion a chymerwch eich amser. Dechreuwch gyda'r achos sylfaenol. Fel arfer yw'r hawsaf i nodi, ac yna gallwch weithio yn ôl oddi yno. Rydych yn gwybod mae angen i chi gyrraedd eich achos sylfaenol, fel y gallai rhoi ychydig o awgrymiadau i chi. Ceisiwch i fynegi un achos penodol yn o ran achosion eraill, neu yn is-setiau. 

Diolch am wylio hyn byr. Ar y lleiaf, yn awr gallwch deall jôcs fel hyn. Fy enw i yw Zamyla, ac mae hyn yn CS50. 

Cymerwch y swyddogaeth hon, hi, a swyddogaeth eiddo gwag sy'n cymryd yn int, n, fel mewnbwn. Mae'r achos sylfaenol yn dod yn gyntaf. Os yw n yn llai na 0, print "Bye" a dychwelyd.