>> 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.