>> ZAMYLA: För att förstå rekursion, måste du
först förstå rekursion.
Att ha rekursion i programkonstruktionsmedel att du har självrefererande
definitioner.
Rekursiva datastrukturer, till exempel, är datastrukturer som
inkludera sig själva i deras definitioner.
Men i dag, kommer vi att fokusera på rekursiva funktioner.
>> Minns att funktioner tar ingångar, argument, och returnera ett värde som deras
utgång representeras av detta diagram här.
Vi ska tänka på lådan som kroppen av den funktion, som innehåller uppsättningen av
instruktioner som tolkar indata och åstadkomma en utsignal.
Ta en närmare titt inuti kroppen av funktionen kan avslöja samtal till
andra funktioner också.
Ta denna enkla funktion, foo, att tar en sträng som indata och
skriver hur många bokstäver att strängen har.
Funktionen strlen, för stränglängd, heter, vars utgång är
krävs för samtalet till printf.
>> Nu, vad som gör en rekursiv funktion speciell är att den kallar sig.
Vi kan representera denna rekursiva ringa med denna orange pil
loopa tillbaka till sig själv.
Men köra själv igen kommer bara gör ett annat rekursivt anrop, och
en annan och en annan.
Men rekursiva funktioner kan inte vara oändlig.
De måste sluta på något sätt, eller din Programmet kommer att köra för evigt.
>> Så vi måste hitta ett sätt att bryta ut ur de rekursiva anrop.
Vi kallar detta basfallet.
När basfallet villkor är uppfyllt, returnerar funktionen utan att göra
ett rekursivt anrop.
Ta denna funktion, hej, ett tomrum funktion som tar en int n som indata.
Basen fall kommer först.
Om n är mindre än noll, skriva ut bye och tillbaka I alla övriga fall, den
Funktionen kommer att skriva hej och exekvera det rekursiva anropet.
Ett annat anrop till funktionen hej med en dekrementeras ingångsvärde.
>> Nu, även om vi skriver ut hej, det Funktionen kommer inte att upphöra förrän vi
tillbaka sin returtyp, i detta fall tomrum.
Så för varje n annat än grundsystemet, denna funktion hi kommer att återvända hi
n minus 1.
Eftersom denna funktion är ogiltig om, vi inte uttryckligen skriver retur här.
Vi ska bara köra funktionen.
Så ringer hej (3) kommer att skriva hej och exekvera hi (2) som exekverar hi (1) en
som exekverar hi (0), där den basfall villkor uppfylls.
Så hej (0) skriver bye och avkastning.
>> OK.
Så nu när vi förstår grunderna i rekursiva funktioner, som de behöver
minst ett basfall samt en rekursivt anrop, låt oss gå vidare till en
mer meningsfullt exempel.
En som inte bara tillbaka ogiltig oavsett vad.
>> Låt oss ta en titt på fakulteten operation som oftast används i
sannolikhetsberäkningar.
Fakulteten av n är produkten av varje positivt heltal mindre än
och lika med n.
Så faktoriell fem är 5 gånger 4 gånger 3 gånger 2 gånger 1 för att ge 120.
Fyra fakultet är 4 gånger 3 gånger 2 gånger 1 för att ge 24.
Och samma regel gäller till något positivt heltal.
>> Så hur kan vi skriva ett rekursivt funktion som beräknar fakulteten
av ett nummer?
Tja, vi måste identifiera både basfall och rekursiva anrop.
Den rekursiva anrop kommer att vara samma i samtliga fall med undantag för basen
fall, vilket innebär att vi måste hitta ett mönster som ger oss vår
önskade resultatet.
>> För detta exempel, se hur 5 faktoriell innebär att multiplicera 4 med 3 med 2 av 1
Och det mycket samma multiplikation finns här, det
definitionen av fyra faktoriell.
Så vi ser att 5 fakultet är bara 5 gånger 4 fakulteten.
Nu går detta mönster gäller till 4 faktoriell också?
Ja.
Vi ser att 4 fakultet innehåller multiplikation 3 gånger 2 gånger 1, den
samma definition som 3 faktoriell.
Så 4 fakultet är lika med 4 gånger 3 faktoriell, och så vidare och så vidare vår
mönster sticker fram 1 faktoriell, vilket per definition är lika med ett.
>> Det finns ingen annan positiv heltal kvar.
Så vi har mönstret för vår rekursivt anrop.
n faktoriell är lika med n gånger fakulteten av n minus 1.
Och vår bas fallet?
Det ska bara vara vår definition av en faktoriell.
>> Så nu kan vi gå vidare till att skriva kod för funktionen.
För basfallet, vi har den tillstånd n är lika jämlikar 1, där
Vi ska återkomma 1.
Sedan flyttar till rekursivt anrop, Vi ska återkomma n gånger
fakulteten av n minus 1.
>> Nu ska vi testa denna vår.
Låt oss försöka faktoriell 4.
Per vår funktion är det lika till 4 gånger faktoriell (3).
Factorial (3) är lika med Tre gånger faktoriella (2).
Factorial (2) är lika med två gånger factorial (1), som returnerar 1.
Factorial (2) ger nu två gånger 1, 2.
Factorial (3) kan nu återvända 3 gånger 2, 6.
Och slutligen, factorial (4) returnerar 4 gånger 6, 24.
>> Om du stöter på några svårigheter med den rekursiva anrop, låtsas att
funktionen fungerar redan.
Vad jag menar med detta är att du ska lita på din rekursiva anrop för att återvända
de rätta värdena.
Till exempel, om jag vet att faktoriell (5) är lika med fem gånger
factorial (4), kommer jag att lita på att factorial (4) kommer att ge mig 24.
Se det som en variabel, om du kommer, som om du redan har definierat
faktoriell (4).
Så för varje fakultet (n), är det produkten av n och
föregående faktoriell.
Och detta tidigare faktor erhålles genom att anropa
fakulteten av n minus 1.
>> Nu, se om du kan genomföra en rekursiv funktion själv.
Ladda upp din terminal, eller run.cs50.net, och skriva en funktionssumma
som tar ett heltal n och returnerar summan av alla på varandra följande positiva
heltal från n till 1.
Jag har skrivit ut de belopp för vissa värden för att hjälpa dig vår.
Först räkna ut basfallet skick.
Titta sedan på summan (5).
Kan du uttrycka det i termer av en annan summa?
Nu, hur är summan (4)?
Hur kan du uttrycka summa (4) i fråga om en annan summa?
>> När du har summa (5) och summan (4) uttryckt i termer av andra belopp, se
Om du kan identifiera en mönster för summan (n).
Om inte, prova några andra nummer och uttrycka sina summor i
termer av ett annat nummer.
Genom att identifiera mönster för diskreta siffror, du är på god väg att
identifiera mönstret för varje n.
>> Rekursion är ett riktigt kraftfullt verktyg, så naturligtvis det är inte begränsat till
matematiska funktioner.
Rekursion kan användas mycket effektivt vid hanteringen av träd till exempel.
Kolla in den korta på träd för en mer grundlig översyn, men för nu
minns att binära sökträd, i Speciellt består av noder, varvid varje
med ett värde och två noder pekare.
Vanligtvis är denna representeras av förälder nod som har en linje som pekar
till den vänstra underordnade noden och en till det högra underordnade noden.
Strukturen hos en binär sökning träd lämpar sig väl
till en rekursiv sökning.
Den rekursiva anrop passerar antingen i vänster eller höger nod, men mer
av att i träd korta.
>> Säg att du vill utföra en operation på varje enskild nod i ett binärt träd.
Hur kan du gå om det?
Tja, skulle du kunna skriva en rekursiv funktion som utför operationen
på den överordnade noden och gör en rekursiv ring för att samma funktion,
som passerar i den vänstra och högra underordnade noder.
Till exempel, den här funktionen foo, som ändrar värdet för en given nod och
alla sina barn till 1.
Basen Vid en null nod orsakar funktionen för att återgå, vilket indikerar
att det inte finns några noder kvar i den underträdet.
>> Låt oss gå igenom det.
Den första föräldern är 13.
Vi ändrar värdet till 1, och sedan ringa vår funktion till vänster samt
som höger.
Funktionen, foo, kallas till vänster sub-träd först, så den vänstra noden
kommer att omfördelas till 1 och foo kommer uppmanas att nodens barn,
först vänster och sedan till höger, och så vidare och så vidare.
Och tala om för dem att de filialer som inte har något fler barn så samma process
kommer att fortsätta under de rätta barn tills hela trädets noder är
omplacerad till 1.
>> Som ni kan se, är du inte begränsad att bara ett rekursivt anrop.
Lika många som kommer att få jobbet gjort.
Tänk om du hade ett träd där varje nod hade tre barn,
Vänster, mitten och höger?
Hur skulle du redigera foo?
Jo, enkelt.
Lägg bara till en annan rekursivt anrop och passera i mitten noden pekaren.
>> Rekursion är mycket kraftfullt och inte till nämna elegant, men det kan vara en
svårt begrepp i början, så var patient och ta din tid.
Börja med basfallet.
Det är oftast lättast att identifiera, och sedan kan du arbeta
baklänges därifrån.
Du vet att du behöver för att nå din basfall, så det kanske
ge dig några tips.
Försök att uttrycka ett specifikt fall i fråga om andra fall, eller i delmängder.
>> Tack för att du tittar på den här korta.
Åtminstone nu kan du förstå skämt som denna.
Mitt namn är Zamyla, och detta är CS50.
>> Ta denna funktion, hej, en void funktion som tar
en int, n, som inmatning.
Basen fall kommer först.
Om n är mindre än 0, print "Bye" och retur.