ZAMYLA: Om te begrijpen recursie, moet u eerst begrijpen recursie. Met recursie in programma-ontwerp middelen dat je zelf-referentiële definities. Recursieve datastructuren, bijvoorbeeld data structuren zijn behoren zich in hun definities. Maar vandaag, we gaan richten op recursieve functies. 

Bedenk dat functies nemen ingangen, argumenten, en terug een waarde als hun uitgang vertegenwoordigers dit schema hier. We bedenken de doos als het lichaam van de functie, bevat de set van aanwijzingen dat de interpretatie van de input en een output geven. Het nemen van een kijkje in het lichaam van de functie zou kunnen oproepen om te onthullen andere functies. Neem deze eenvoudige functie, foo, dat neemt een enkele string als input en prints hoeveel letters die string heeft. De functie strlen, voor strijkkwartet lengte, wordt genoemd, waarvan de uitvoer nodig is voor de oproep om printf. 

Nu, wat maakt een recursieve functie bijzonder is dat het zelf noemt. We kunnen dit recursieve vertegenwoordigen bellen met deze oranje pijl looping terug naar zichzelf. Maar zich opnieuw uitvoeren alleen zal andere recursieve bellen, en een en ander. Maar recursieve functies kan niet oneindig. Ze moeten een of andere manier te beëindigen, of uw programma zal voor altijd draaien. 

Dus moeten we een manier om te breken vinden uit de recursieve oproepen. We noemen dit het nulalternatief. Wanneer de base case voorwaarde is voldaan, retourneert de functie zonder andere recursieve aanroep. Neem deze functie, hi, een leegte functie dat neemt een int n als invoer. Het nulalternatief komt eerst. Als n kleiner is dan nul, print-bye en terug Voor alle andere gevallen, de functie wordt afgedrukt hi en uitvoeren de recursieve aanroep. Ander gesprek om de functie hi met een verlaagd invoerwaarde. 

Nu, hoewel we drukken hi, de functie zal niet eindigen totdat we terug zijn return type, in dit geval vervallen. Dus voor elke n ander dan het basisscenario, deze functie hi zal terugkeren hi n minus 1. Omdat deze functie is nietig hoewel, we zal hier niet expliciet return type. We zullen gewoon de functie uit te voeren. Dus bellen hi (3) wordt afgedrukt hi en voeren hi (2), die hi voert (1) een die hi uitvoert (0), waarbij de base case voorwaarde wordt voldaan. Dus hi (0) drukt bye en rendement. 

OK. Dus nu dat we begrijpen de basis van recursieve functies, die ze nodig hebben minstens een referentiemodel en een recursieve aanroep, laten we overgaan tot een zinvoller voorbeeld. Een die niet alleen terug vervalt er ook gebeurt. 

Laten we eens een kijkje nemen op de faculteit operatie gebruikt meestal in kansberekeningen. Faculteit van n is het product van elke positief geheel getal kleiner dan en gelijk aan n. Dus faculteit vijf is 5 keer 4 keer 3 maal 2 maal 1 geven 120. Vier faculteit is 4 keer 3 keer 2 maal 1 tot 24 geven. En hetzelfde geldt elk positief geheel getal. 

Dus hoe kunnen we schrijven een recursieve functie die de faculteit berekent van een nummer? Nou, we moeten identificeren zowel de base case en de recursieve aanroep. De recursieve aanroep zal hetzelfde zijn voor alle gevallen, behalve de basis geval, wat betekent dat we zullen moeten vind een patroon dat ons zal geven onze gewenste resultaat. 

Voor dit voorbeeld zien hoe 5 faculteit gaat vermenigvuldigen 4 bij 3 bij 2 bij 1 En diezelfde vermenigvuldiging is hier te vinden, de definitie van 4 factorial. Zo zien we dat 5 faculteit is slechts 5 keer 4 faculteit. Nu heeft dit patroon van toepassing 4 faculteit ook? Ja. We zien dat 4 faculteit bevat het vermenigvuldiging 3 maal 2 maal 1, de zeer dezelfde definitie als 3 faculteit. Dus 4 faculteit is gelijk aan 4 maal 3 faculteit, en zo verder en zo voort onze patroon stokken tot 1 faculteit, die per definitie gelijk is aan 1. 

Er is geen andere positieve getallen links. Dus hebben we het patroon voor onze recursieve aanroep. n faculteit is gelijk aan n keer de faculteit van n minus 1. En ons basisscenario? Dat zal alleen onze definitie 1 factorial. 

Dus nu kunnen we overgaan tot het schrijven code voor de functie. Voor het nulalternatief, moeten we de voorwaarde n gelijk gelijken 1, waar we zullen 1 terugkeren. Dan verplaatsen naar de recursieve aanroep, we zullen n keer terug de faculteit van n minus 1. 

Nu laten we dit testen onze. Laten we proberen faculteit 4. Per onze functie het gelijk 4 keer factorial (3). Faculteit (3) is gelijk aan 3 keer factorial (2). Faculteit (2) is gelijk aan 2 keer faculteit (1), die terugkeert 1. Faculteit (2) geeft nu 2 maal 1, 2. Faculteit (3) kan nu terugkeren 3 maal 2, 6. En tenslotte, faculteit (4) geeft 4 keer 6, 24. 

Als je ondervindt enige moeite met de recursieve aanroep, doen alsof de functie werkt reeds. Wat ik bedoel is dat je moet vertrouw op je recursieve oproepen om terug te keren de juiste waarden. Bijvoorbeeld, als ik weet dat faculteit (5) is gelijk aan 5 keer faculteit (4), ga ik ervan uit dat faculteit (4) zal me 24 geven. Zie het als een variabele, als je zal, alsof je al gedefinieerd factorial (4). Dus voor elke faculteit (n), het het product van n en de vorige faculteit. En dit vorige faculteit wordt verkregen door te bellen naar faculteit van n minus 1. 

Nu, kijk of je kunt implementeren van een recursieve functie zelf. Laad je terminal, of run.cs50.net, en schrijf een functie sum dat neemt een geheel getal n en geeft de som van alle opeenvolgende positieve gehele getallen van 1 tot n. Ik heb geschreven uit de sommen van sommige waarden om u te helpen ons. Eerste, figuur uit de base case conditie. Dan, kijk naar sum (5). Kun je het uitdrukken in termen ander som? Nu, hoe zit sum (4)? Hoe kun je uitdrukken sum (4) in termen van een ander bedrag? 

Zodra u een bedrag (5) en sum (4) uitgedrukt in termen van andere bedragen, zie als je kunt identificeren van een patroon voor sum (n). Zo niet, probeer dan een paar andere nummers en uiten hun sommen in termen van een ander nummer. Door het identificeren van patronen voor discrete nummers, je bent goed op weg naar het identificeren van de patroon voor elke n. 

Recursie is echt een krachtig hulpmiddel, dus natuurlijk is het niet beperkt tot wiskundige functies. Recursie kan zeer effectief worden gebruikt bij het omgaan met bomen bijvoorbeeld. Bekijk de korte op bomen voor een meer grondige herziening, maar voor nu herinneren dat binary search bomen, bijzonder zijn opgebouwd uit knooppunten die elk met een waarde en twee knooppunt pointers. Meestal wordt dit weergegeven door de parent node met een lijn wijzend naar links kind knooppunt en een rechts onderliggende node. De structuur van een binary search boom leent zich goed een recursieve zoekopdracht. De recursieve aanroep ofwel passen in de links of rechts knooppunt, maar van dat de boom kort. 

Stel dat je wilt om een ​​operatie uit te voeren op elk knooppunt in een binaire boom. Hoe zou je over dat? Nou, je kan een recursieve schrijven functie die de operatie uitvoert op het bovenliggende knooppunt en maakt een recursieve roepen om dezelfde functie, passeren in de linker en rechts kind knooppunten. Bijvoorbeeld, deze functie foo, dat verandert de waarde van een bepaald knooppunt en al zijn kinderen 1. Het basisscenario van een null knooppunt oorzaken de functie weer te geven dat er geen knopen links in die sub-boom. 

Laten we er doorheen lopen. De eerste ouder is 13. We veranderen de waarde op 1, en dan bellen onze functie links en als rechts. De functie, foo, wordt een beroep op de linker sub-boom voor het eerst, dus de linker knooppunt zullen worden toegewezen aan 1 en foo zal worden opgeroepen kinderen dat knooppunt, eerst links en dan rechts, en zo verder en zo voort. En vertel hen dat takken niet hebben meer kinderen dus hetzelfde proces zal blijven voor de juiste kinderen tot knooppunten van de hele boom zijn toegewezen aan 1. 

Zoals je kunt zien, bent u niet beperkt slechts een recursieve aanroep. Net zoveel als zal de klus te klaren. Wat als je een boom had waar elke knooppunt had drie kinderen, Links, midden en rechts? Hoe zou u foo bewerken? Nou, simpel. Voeg gewoon nog een recursieve aanroep en passeren in het midden knooppunt aanwijzer. 

Recursie is zeer krachtig en niet te noemen elegant, maar het kan een moeilijk concept op het eerste, dus wees patiënt en neem de tijd. Begin met het nulalternatief. Het is meestal het makkelijkst te identificeren en dan kun je werken achteruit vanaf daar. Je weet dat je nodig hebt om te bereiken uw base case, zodat de macht geven je een paar tips. Proberen om een ​​specifiek geval te drukken in termen van andere gevallen, of in sub-sets. 

Bedankt voor het kijken deze korte. Op zijn minst, nu kunt u begrijpen grappen als deze. Mijn naam is Zamyla, en dit is CS50. 

Neem deze functie, hi, een leegte functie die neemt een int, n, als input. Het nulalternatief komt eerst. Als n kleiner is dan 0, afdrukken "Bye" en terugkeer.