>> ZAMYLA: Om te verstaan rekursie, moet jy
eers verstaan ​​rekursie.
Met rekursie in program ontwerp middel dat jy self-referensiële
definisies.
Rekursiewe data strukture, byvoorbeeld, is data strukture wat
sluit hulself in hul definisies.
Maar vandag gaan ons om te fokus op rekursiewe funksies.
>> Onthou dat funksies neem insette, argumente en terugkeer 'n waarde as hul
uitset verteenwoordig deur hierdie diagram hier.
Ons sal dink van die boks as die liggaam van die funksie, wat die stel van
instruksies wat interpreteer die insette en gee 'n uitset.
Neem 'n nader kyk binne-in die liggaam van die funksie kan oproepe om te openbaar
ander funksies.
Neem hierdie eenvoudige funksie, cat, wat neem 'n enkele string as invoer en
afdrukke hoeveel letters dat string het.
Die funksie StrLen vir string lengte, genoem word, waarvan die opbrengs is
nodig is vir die oproep te printf.
>> Nou, wat maak 'n rekursiewe funksie spesiaal maak, is dat dit 'n beroep self.
Ons kan hierdie rekursiewe verteenwoordig noem met hierdie oranje pyl
herhaling terug na homself.
Maar self die uitvoering weer sal slegs 'n ander rekursiewe oproep, en
'n ander en 'n ander.
Maar rekursiewe funksies kan nie oneindig wees.
Hulle het een of ander manier eindig, of jou program sal vir ewig hardloop.
>> So het ons 'n manier om te breek om uit te vind uit die rekursiewe oproepe.
Ons noem dit die basis geval.
Wanneer die basis geval voorwaarde voldoen word, die funksie gee sonder om
'n ander rekursiewe oproep.
Neem hierdie funksie, hi, 'n leemte funksie dit neem 'n int n as insette.
Die basis saak kom eerste.
As n is minder as nul, druk bye en ruil vir al die ander gevalle, die
funksie sal druk hi en uit te voer die rekursiewe oproep.
Nog 'n oproep om die funksie hi met 'n decremented insette waarde.
>> Nou, selfs al het ons druk hi, die funksie sal nie beëindig totdat ons
terugkeer om sy terugkeer tipe, In hierdie geval is leeg.
So vir elke n ander as die basis geval, hierdie funksie hi sal terugkeer hi
N minus 1.
Aangesien hierdie funksie is nietig al is, ons sal nie uitdruklik tik terugkeer hier.
Ons sal net die funksie uit te voer.
So roep hi (3) sal druk hi en voer hi (2) wat voer hi (1) 'n
wat voer hi (0), waar die basis geval voorwaarde voldoen word.
So hi (0) druk bye en opbrengste.
>> OK.
So nou dat ons verstaan ​​die basiese beginsels van rekursiewe funksies, wat hulle nodig het
ten minste een basis geval, sowel as 'n rekursiewe oproep, laat ons beweeg na 'n
meer betekenisvolle voorbeeld.
Een wat nie net terug nietig maak nie saak wat.
>> Kom ons neem 'n blik op die faktoriaal werking gebruik mees algemeen in
waarskynlikheid berekeninge.
Faktoriaal van n is die produk van elke positiewe heelgetal minder as
en gelyk aan n.
So faktoriaal vyf is 5 keer 4 keer 3 keer 2 keer 1 120 te gee.
Vier faktoriaal is 4 keer 3 keer 2 keer 1 te gee 24.
En dieselfde reël geld aan enige positiewe heelgetal.
>> So, hoe kan ons skryf 'n rekursiewe funksie wat bereken die faktoriaal
van 'n getal?
Wel, ons sal moet identifiseer beide die basis geval en die rekursiewe oproep.
Die rekursiewe sal dieselfde wees vir alle gevalle behalwe vir die basis
geval, wat beteken dat ons sal moet vind 'n patroon wat ons sal gee ons
gewenste resultaat.
>> Vir hierdie voorbeeld, sien hoe 5 faktoriaal behels vermenigvuldig 4 deur 3 by 2 deur 1
En daardie selfde vermenigvuldiging is hier gevind, die
definisie van 4 faktoriaal.
So sien ons dat 5 faktoriaal is net 5 keer 4 faktoriaal.
Nou het hierdie patroon van toepassing 4 faktoriaal asook?
Ja.
Ons sien dat 4 faktoriaal bevat die vermenigvuldiging 3 keer 2 keer 1, die
selfde definisie as 3 faktoriaal.
So 4 faktoriaal is gelyk aan 4 keer 3 faktoriaal, en so aan en so voort ons
patroon stokke tot 1 faktoriaal, wat per definisie is gelyk aan 1.
>> Daar is geen ander positiewe heelgetalle gelaat.
So het ons die patroon vir ons rekursiewe oproep.
n faktoriale is gelyk aan n keer die faktoriaal van n minus 1.
En ons basis geval?
Dit sal net ons definisie 1 faktoriaal.
>> So nou kan ons aanbeweeg na skriftelike kode vir die funksie.
Vir die basis geval is, sal ons die voorwaarde n gelyk gelykes 1, waar
ons sal terugkeer 1.
Dan beweeg op die rekursiewe oproep, ons sal terugkeer n keer die
faktoriaal van n minus 1.
>> Kom ons toets hierdie ons nou.
Kom ons probeer faktoriaal 4.
Per ons funksie dit is gelyk 4 keer faktoriaal (3).
Faktoriaal (3) is gelyk aan 3 keer faktoriaal (2).
Faktoriaal (2) is gelyk aan 2 keer faktoriaal (1), wat terugkeer 1.
Faktoriaal (2) keer terug nou 2 keer 1, 2.
Faktoriaal (3) kan nou terugkeer 3 keer 2, 6.
En uiteindelik, faktoriaal (4) terug 4 keer 6, 24.
>> As jy enige probleme ondervind met die rekursiewe oproep, voorgee dat
die funksie werk reeds.
Wat ek bedoel met dit is dat jy vertrou jou rekursiewe oproepe om terug te keer
die regte waardes.
Byvoorbeeld, as ek weet dat faktoriaal (5) is gelyk aan 5 keer
faktoriaal (4), ek gaan om dit te vertrou faktoriaal (4) gee my 24.
Dink aan dit as 'n veranderlike, as jy sal, asof jy reeds gedefinieer
faktoriaal (4).
So vir enige faktoriaal (n), is dit die produk van N en
die vorige faktoriaal.
En hierdie vorige faktoriaal verkry word deur die roeping
faktoriaal van n minus 1.
>> Nou, kyk of jy kan implementeer om 'n n rekursiewe funksie jouself.
Laai jou terminale, of run.cs50.net, en skryf 'n funksie som
dit neem 'n heelgetal n en gee die som van alle opeenvolgende positiewe
heelgetalle vanaf N tot 1.
Ek het geskryf die somme van 'n paar waardes om jou te help om ons.
Eerstens, vind uit die basis geval toestand.
Dan, kyk na bedrag (5).
Kan jy dit uit te druk in terme van 'n ander som?
Nou, wat oor die som (4)?
Hoe kan jy druk som (4) in terme van 'n ander som?
>> Sodra jy 'n som (5) en som (4) uitgedruk in terme van ander somme, sien
As jy 'n kan identifiseer patroon vir som (n).
Indien nie, probeer om 'n paar ander getalle en hul somme in
terme van 'n ander getalle.
Deur die identifisering van patrone vir diskrete getalle, is jy goed op jou pad na
die identifisering van die patroon vir enige n.
>> Rekursie is 'n baie kragtige instrument, so dit is natuurlik nie beperk tot
wiskundige funksies.
Rekursie kan baie effektief gebruik word om wanneer met bome byvoorbeeld.
Check uit die kort op die bome vir 'n meer deeglike hersiening, maar vir nou
onthou dat binêre soek bome, in besonder, is saamgestel uit nodes, elk
met 'n waarde en twee knoop wysers.
Gewoonlik word hierdie verteenwoordig deur die voorgangernode met een lyn wat
aan die linkerkant kind knoop en een aan die regterkant kind knoop.
Die struktuur van 'n binêre soek boom leen hom goed
'n rekursiewe soek.
Die rekursiewe oproep gaan óf in die linker-of die regterkant knoop, maar meer
van daardie in die boom kort.
>> Sê jy wil 'n operasie uit te voer op elke enkele knoop in 'n binêre boom.
Hoe kan jy te werk gaan dit?
Wel, jy kan 'n rekursiewe skryf funksie wat die operasie uitvoer
op die voorgangernode en maak 'n rekursiewe bel om dieselfde funksie,
verby in die linker-en regte kind nodes.
Byvoorbeeld, hierdie funksie, cat, wat verander die waarde van 'n gegewe knoop en
al sy kinders 1.
Die basis geval van 'n nul-knoop oorsake die funksie om terug te keer, wat aandui
dat daar nie enige nodes links in daardie sub-boom.
>> Kom ons loop deur dit.
Die eerste ouer is 13.
Ons verander die waarde tot 1, en dan bel ons funksie aan die linkerkant asook
as die regterkant.
Die funksie, cat, is 'n beroep op die linker sub-boom eerste, sodat die linker-knoop
sal oorgeplaas word na 1 en cat sal word 'n beroep op die knoop se kinders,
eerste links en dan regs, en so aan en so voort.
En hulle vertel dat takke het nie nog kinders so dieselfde proses
sal voortgaan om vir die reg om kinders totdat die hele boom se knope is
oorgeplaas na 1.
>> Soos jy kan sien, is jy nie beperk om net een rekursiewe oproep.
Net soveel as die werk gedoen te kry.
Wat gebeur as jy 'n boom het waar elke node het drie kinders,
Links, middel, en reg?
Hoe sal jy cat wysig?
Wel, eenvoudig.
Net nog 'n rekursiewe oproep en slaag in die middel knoop wyser.
>> Rekursie is baie sterk en nie te noem elegant, maar dit kan 'n wees
moeilike konsep op die eerste, so wees pasiënt en neem jou tyd.
Begin met die basis geval.
Dit is gewoonlik die maklikste om te identifiseer, en dan kan jy die werk
terug van daar af.
Jy weet wat jy nodig het om te bereik jou basis geval, sodat mag
gee jou 'n paar wenke.
Probeer om een ​​spesifieke geval in te druk terme van ander gevalle, of in sub-stelle.
>> Dankie vir jou kyk hierdie kort.
Op die heel minste, nou kan jy grappies soos hierdie te verstaan.
My naam is Zamyla, en dit is cs50.
>> Neem hierdie funksie, hi, 'n leemte funksie wat '
'n int, N, as insette.
Die basis saak kom eerste.
As n is minder as 0, druk "Bye" en terugkeer.