[MUSIK SPELA] 

DOUG LLOYD: Du tror nog att kod bara för att utföra en uppgift. Du skriver ut det. Det gör något. Det är ganska mycket det. 

Du kompilera den. Du kör programmet. Du är bra att gå. 

Men tro det eller ej, om du koda för en lång tid, du faktiskt kan komma att se kod som något som är vackert. Den löser ett problem i ett mycket intressant sätt, eller finns det bara något riktigt snyggt om hur det ser ut. Du kanske skrattar på mig, men det är sant. Och rekursion är ett sätt att typ av få denna idé vackra, elegant utseende kod. Det löser problem på ett sätt som är intressanta, lätt att visualisera, och överraskande kort. 

De sätt rekursion fungerar är, en rekursiv funktion definieras som en funktion som anropar sig själv som en del i genomförandet. Det kan verka lite konstigt, och vi får se lite om hur detta fungerar i ett ögonblick. Men återigen, dessa rekursiva procedurer är kommer att bli så elegant eftersom de ska att lösa detta problem utan att ha alla dessa andra funktioner eller dessa långa slingor. Du ser att dessa rekursiva procedurer kommer att se så kort. Och de verkligen kommer att göra koden ser mycket vackrare. 

Jag ska ge er ett exempel av detta för att se hur en rekursiv procedur kan definieras. Så om du är bekant med detta från klassen Math för många år sedan, Det finns något som kallas faktor funktion, som vanligtvis betecknas som ett utropstecken, vilket definieras över alla positiva heltal. Och sättet att n fakultet beräknas är du multiplicera alla talen mindre än eller lika med n together-- alla heltal mindre än eller lika med n tillsammans. 

Så 5 fakultet är 5 gånger 4 gånger 3 gånger 2 gånger 1. Och 4 fakultet är 4 gånger 3 gånger 2 gånger 1 och så vidare. Du får idén. 

Som programmerare, gör vi inte Använd n, utropstecken. Så vi ska definiera fakulteten funktion som ett faktum av n. Och vi kommer att använda faktor att skapa en rekursiv lösning på ett problem. Och jag tror att du kan hitta att det är en mycket mer visuellt tilltalande än den iterativa version av detta, vilket Vi kommer också att titta på i ett ögonblick. 

Så här är ett par facts-- vits intended-- om factorial-- den fakulteten. Fakulteten för en, som sagt, är en. Fakulteten för 2 är 2 gånger 1. Fakulteten för 3 är 3 gånger 2 gånger 1, och så vidare. Vi pratade om 4 och 5 redan. 

Men titta på detta, är inte detta sant? Är inte fakulteten av 2 bara 2 gånger faktor 1? Jag menar, är fakulteten av 1 1. Så varför kan vi inte bara säga att, eftersom fakulteten av 2 är 2 gånger 1, Det är egentligen bara 2 gånger fakulteten för en? 

Och sedan utvidga den tanken, är inte fakulteten av 3 bara 3 gånger faktor 2? Och fakulteten av fyra är 4 gånger fakulteten av 3, och så vidare? I själva verket, fakulteten av valfritt antal kan bara uttryckas om vi typ av genomföra detta för alltid. Vi kan slags generalisera fakulteten problemet eftersom det är n gånger fakulteten av n minus en. Det är n gånger produkten av alla nummer mindre än mig. 

Denna idé, detta generalisering av problemet, ger oss möjlighet att rekursivt definiera fakulteten. När du definierar en funktion rekursivt, det finns två saker som måste vara en del av det. Du måste ha något som kallas en basfall, som när du utlösa det, kommer att stoppa den rekursiva processen. 

Annars en funktion som anropar itself-- som du kanske imagine-- skulle kunna fortsätta i evigheter. Funktionsanrop funktionen kallar funktionsanrop funktionen anropar funktionen. Om du inte har ett sätt att stoppa det, ditt program kommer att på ett effektivt sätt fastnat vid en oändlig slinga. Det kommer att krascha småningom, eftersom det kommer att få slut på minne. Men det är ovidkommande. 

Vi måste ha något annat sätt att stoppa saker förutom vårt program kraschar, eftersom ett program som kraschar är förmodligen inte vacker eller elegant. Och så vi kallar detta basfall. Detta är en enkel lösning ett problem som stannar den rekursiva processen uppstår. Så det är en del av en rekursiv funktion. 

Den andra delen är den rekursiva fallet. Och det är där rekursion faktiskt kommer att äga rum. Det är där funktionen kalla sig. 

Det kommer inte att kalla sig på exakt på samma sätt som det hette. Det blir en liten variation som gör problemet är det försöker lösa ett pyttelitet lite mindre. Men den passerar allmänhet buck att lösa huvuddelen av lösningen till en annan samtals fram. 

Vilken av dessa ser som grund fallet här? Vilken av dessa ser ut som den enklaste lösningen på ett problem? Vi har ett gäng faktorial, och vi kunde fortsätta gå on-- 6, 7, 8, 9, 10, och så vidare. 

Men en av dessa ser ut som en bra fall för att vara basen fallet. Det är en mycket enkel lösning. Vi behöver inte göra något speciellt. 

Fakulteten för en är bara en. Vi behöver inte göra något multiplikation alls. Det verkar som om vi tänker att försöka lösa detta problem, och vi måste stoppa rekursion någonstans, vi förmodligen vill sluta det när vi kommer till en. Vi vill inte sluta innan dess. 

Så om vi definierar vår faktoriell funktion, Här är ett skelett för hur vi kan göra det. Vi måste koppla in dessa två saker-- basfallet och rekursiva fallet. Vad är basen fallet? Om n är lika med ett, retur 1-- det är ett riktigt enkelt problem att lösa. 

Fakulteten för 1 är en. Det är inte 1 gånger någonting. Det är bara en. Det är ett mycket enkelt faktum. Och så det kan vara vår bas fallet. Om vi ​​få passerat 1 till detta funktion, kommer vi bara tillbaka en. 

Vad är den rekursiva väska antagligen ut? För varje annat nummer förutom ett, vad är mönstret? Tja, om vi tar fakulteten av n, det är n gånger fakulteten av n minus en. 

Om vi ​​tar fakulteten av 3 Det är 3 gånger fakulteten av 3 minus 1, eller 2. Och så om vi inte tittar på en, annars retur N gånger fakulteten av n minus en. Det är ganska enkelt. 

Och för den skull ha något renare och mer elegant kod, vet att om vi har en enda rad slingor eller enradig villkorliga grenar, vi kan bli av med alla de klamrar runt dem. Så vi kan konsolidera denna till detta. Detta har exakt samma funktion som redan. 

Jag bara ta bort lockigt hängslen, eftersom det bara finns en rad insidan av dessa villkorliga förgreningar. Så dessa beter sig på samma sätt. Om n är lika med 1, returnera ett. Annars åter n gånger fakulteten av n minus 1. Så vi gör problemet mindre. Om n börjar som 5, ska vi tillbaka 5 gånger fakulteten av fyra. Och vi får se i en minut när vi talar om samtalet stack-- i en annan video där vi talar om Ring stack-- vi lär om varför just den här processen fungerar. 

Men medan fakulteten av 5 säger tillbaka 5 gånger fakulteten av fyra, och fyra kommer att säga, OK, ja, retur 4 gånger faktor 3. Och som ni kan se, vi är sorts närmar 1. Vi får närmare och närmare den basfall. 

Och när vi slog basfallet, alla de tidigare funktionerna har svaret de letade efter. Fakulteten av 2 sade avkastning 2 gånger faktor 1. Tja, fakulteten för 1 returnerar 1. Så uppmaningen till fakulteten 2 kan återvända 2 gånger 1, och ge det tillbaka till fakulteten av 3, som väntar på det resultatet. 

Och då kan det beräkna dess resultat, 3 gånger 2 är 6, och ge det tillbaka till fakulteten av fyra. Och återigen, vi har en video på anropsstacken där detta illustreras lite mer än vad jag säger just nu. Men det är det. Bara detta är lösningen på beräkna fakulteten för ett tal. 

Det är bara fyra rader kod. Det är ganska coolt, va? Det finns en slags sexig. 

Så i allmänhet, men inte alltid, en rekursiv funktion kan ersätta en slinga i ett icke-rekursiv funktion. Så här, sida vid sida, är den iterativa versionen av fakulteten. Båda dessa kalkylera exakt samma sak. 

De båda beräkna fakulteten av n. Versionen till vänster använder rekursion att göra det. Versionen på höger använder iteration att göra det. 

Och varsel, måste vi förklara en variabel ett heltal produkt. Och då är vi loop. Så länge som n är större än 0, vi hålla multiplicera produkten med n och nedräkna n tills vi beräkna produkten. Så dessa två funktioner, återigen, gör exakt samma sak. Men de gör det inte i exakt samma sätt. 

Nu är det möjligt att ha mer än en bas ärende eller mer än en rekursiv fall beroende på vad din funktion försöker göra. Du är inte nödvändigtvis bara begränsat till en enda bas ärende eller en enda rekursiv fallet. Så ett exempel på något med flera bas fall kan vara this-- den Sekvensen Fibonacci nummer. 

Ni kanske minns från elementära skoldagar att Fibonacci sekvensen definieras liknande this-- det första elementet är 0. Den andra delen är en. Båda dessa är bara genom definition. 

Sedan varannan element definieras som summan av n minus 1 och n minus 2. Så det tredje elementet skulle vara 0 plus 1 är en. Och sedan det fjärde elementet skulle vara det andra elementet, en, plus den tredje delen, 1. Och det skulle vara två. Och så vidare och så vidare. 

Så i det här fallet har vi två bas fall. Om n är lika med 1, returnerar 0. Om n är lika med 2, returnera ett. Annars åter Fibonacci n minus en plus Fibonacci av n minus 2. 

Så det är flera bas fall. Vad sägs om flera rekursiva fall? Tja, det finns något kallas Collatz gissningar. Jag tänker inte säga, du vet vad det är, eftersom det är faktiskt vår sista problem för denna viss video. Och det är vår träning att arbeta tillsammans. 

Så här är vad Collatz förmodanden är-- det gäller för varje positivt heltal. Och det spekulerar att det är alltid möjligt att få tillbaka till 1 om du följer dessa steg. Om n är 1, sluta. Vi har kommit tillbaka till 1 om n är 1. 

Annars går igenom detta processen igen på n dividerat med två. Och se om du kan komma tillbaka till ett. Annars, om n är udda, gå igenom denna process igen på 3n plus 1, eller 3 gånger n plus 1. Så här har vi en enda bas fallet. Om n är lika med 1, sluta. Vi ska inte göra något mer rekursion. 

Men vi har två rekursiva fall. Om n är ännu, gör vi en rekursiva fall, Ringa n dividerat med två. Om n är udda, vi gör en annan rekursiva fall på 3 gånger n plus 1. 

Och så målet för den här videon är att ta en andra, pausa videon, och försöka skriva detta rekursiv funktion Collatz där du passerar på ett värde n, och Det beräknar hur många steg det tar för att komma till en om du börjar från n och du följer dessa steg upp ovan. Om n är 1, det tar 0 steg. Annars kommer det att ta ett steg plus dock många steg det tar på antingen n dividerat med 2 om n är ännu, eller 3n plus 1 om n är udda. 

Nu, jag har lagt upp på skärmen här ett par test saker för dig, ett par tester fall för dig, för att se vad dessa olika Collatz siffror är, och även en illustration av de åtgärder som måste gås igenom så att du kan sorts se denna process i aktion. Så om n är lika med 1, Collatz n är 0. Du behöver inte göra något att komma tillbaka till ett. Du är redan där. 

Om n är 2, det tar ett steg för att komma till en. Du börjar med 2. Tja, är två inte är lika med ett. Så det kommer att bli ett steg plus hur många steg det tar på n dividerat med två. 

2 delat med 2 är en. Så det tar ett steg plus dock många steg det tar för en. 1 tar noll steg. 

För tre, som ni kan se, det finns ett par steg inblandade. Du går från 3. Och sedan gå till 10, 5, 16, 8, 4, 2, 1. Det tar sju steg för att komma tillbaka till ett. Och som ni kan se, det finns en par andra testfall här att testa programmet. Så återigen, pausa videon. Och jag ska gå hoppa tillbaka nu vad själva processen är här, vad denna hypotes är. 

Se om du kan räkna ut hur man definierar Collatz n så att den beräknar hur många steg som krävs för att komma till en. Så förhoppningsvis har du pausat videon och du inte bara väntar på mig för att ge dig svaret här. Men om du är, tja, Här är svaret ändå. 

Så här är en möjlig definition av Collatz funktionen. Vår bas case-- om n är lika med 1, återvänder vi 0. Det tar inte någon åtgärder för att komma tillbaka till ett. 

Annars har vi två rekursiva cases-- en för jämna nummer och ett för udda. Som jag testa jämna nummer är att kontrollera om n mod 2 är lika med 0. Detta är i grunden, återigen, ställer frågan, om du minns vad mod är-- om jag dividera n med 2 finns det ingen resten? Det skulle vara ett jämnt antal. 

Och så om n mod 2 är lika med 0 är testning är detta ett jämnt antal. Om så är fallet, jag vill återvända 1, eftersom detta är definitivt tar ett steg plus Collatz av oavsett antal är hälften av mig. Annars, jag vill återvända 1 plus Collatz av 3 gånger n plus 1. Det var den andra rekursiva steg som vi kan vidta för att beräkna Collatz-- antalet steg det tar att komma tillbaka 1 ges ett nummer. Så förhoppningsvis detta exempel gav dig lite en smak av rekursiva procedurer. Förhoppningsvis tycker du koden är en lite vackrare om de genomförs i en elegant, rekursiv sätt. Men även om det inte är rekursion en verkligen kraftfullt verktyg ändå. Och så det är definitivt något att få huvudet runt, eftersom du kommer att kunna skapa ganska cool program med rekursion som annars skulle vara komplicerat att skriva Om du använder loopar och iteration. Jag är Doug Lloyd. Detta är CS50.