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.