Share
Vissa problem löses naturligt med recursion. Exempelvis har en sekvens som Fibonacci-sekvensen en rekursiv definition. Varje nummer i sekvensen är summan av de föregående två talen i sekvensen. Problem som kräver att du bygger eller spårar en trädliknande datastruktur kan också lösas med rekursion. Träna dig själv för att tänka rekursivt kommer att ge dig en kraftfull färdighet att attackera sådana problem.
I denna handledning går jag igenom flera rekursiva funktioner steg för steg för att se hur de fungerar och visa dig tekniker du kan använda för att systematiskt definiera rekursiva funktioner.
En rekursivt definierad funktion är en funktion som definieras i form av en enklare version av sig själv. Detta är ett förenklat exempel:
funktion doA (n) ... doA (n-1);
För att förstå hur rekursionen fungerar konceptuellt ser vi på ett exempel som inte har något med kod att göra. Tänk dig att du är ansvarig för att besvara telefonsamtal på jobbet. Eftersom det här är ett upptaget företag har din telefon flera telefonlinjer så att du kan jonglera flera samtal samtidigt. Varje telefonlinje är en knapp på mottagaren, och när det kommer ett inkommande samtal blinkar knappen. Idag när du kommer till jobbet och slår på telefonen är det fyra linjer som blinkar på en gång. Så du kommer till jobbet och svarar på alla samtal.
Du plockar upp linje ett och berättar för dem "vänligen håll". Då plockar du upp linje två och lägger dem i vänteläge. Därefter plockar du upp linje tre och lägger dem i vänteläge. Slutligen svarar den fjärde raden och talar med den som ringer. När du är färdig med den fjärde uppringaren, lägger du upp och tar upp det tredje samtalet. När du avslutar med det tredje samtalet lägger du upp och tar upp det andra samtalet. När du avslutar med det andra samtalet lägger du upp och tar upp det första samtalet. När du avslutar det samtalet kan du äntligen sätta telefonen ner.
Varje telefonsamtal i det här exemplet är som ett rekursivt samtal i en funktion. När du får ett samtal sätts det på samtalstacken (i kodtal). Om du inte kan slutföra ett samtal direkt lägger du samtalet i vänteläge. Om du har ett funktionssamtal som inte kan utvärderas omedelbart, stannar det på samtalstapeln. När du kan svara på ett samtal tas det upp. När din kod kan utvärdera ett funktionssamtal är det poppat av stapeln. Håll denna analogi i åtanke när du tittar på följande kodexempel.
Alla rekursiva funktioner behöver ett basfall så att de kommer att avslutas. Men bara att lägga till ett basfall till vår funktion hindrar inte det från att springa oändligt. Funktionen måste ha ett steg för att ta oss närmare basfallet. Det sista är det rekursiva steget. I det rekursiva steget reduceras problemet till en mindre version av problemet.
Antag att du har en funktion som summerar numren från 1 till n. Till exempel, om n = 4, kommer det att summa 1 + 2 + 3 + 4.
Först bestämmer vi basfallet. Att hitta basfallet kan också ses som att hitta fallet där problemet kan lösas utan rekursion. I det här fallet är det när n är lika med noll. Noll har inga delar, så vår recursion kan sluta när vi når 0.
Vid varje steg kommer du att subtrahera en från det aktuella numret. Vad är det rekursiva fallet? Det rekursiva fallet är funktionssumman som heter med det reducerade numret.
funktionssumma (num) if (num === 0) return 0; annars return num + summa (- num) summa (4); // 10
Detta är vad som händer vid varje steg:
Detta är ett annat sätt att se hur funktionen behandlar varje samtal:
summa (4) 4 + summa (3) 4 + (3 + summa (2)) 4 + (3 + (2 + summa)) 4 + (3 + (2 + (1 + summa )) 4 + (3 + (2 + (1 + 0))) 4 + (3 + (2 + 1)) 4 + (3 + 3) 4 + 6 10
Argumentet bör ändras i rekursivt fall och föra dig närmare basfallet. Detta argument bör testas i basfallet. I föregående exempel, eftersom vi subtraherar ett i rekursivt fall, testar vi om argumentet är lika med noll i vårt basfall.
Accentsconagua
multiplicera (2,4) kommer tillbaka 8. Skriv vad som händer vid varje steg för multiplicera (2,4).Återkommande på en lista liknar återkommande på ett nummer, förutom att istället för att minska antalet vid varje steg reducerar vi listan vid varje steg tills vi kommer till en tom lista.
Tänk på summan som tar en lista som input och returnerar summan av alla element i listan. Detta är en implementering för funktionssumman:
funktionssumma (l) om (tomt (l)) return 0; annars returbil (l) + summa (cdr (l));
De tömma funktionen returnerar sant om listan inte har några element. De bil funktionen returnerar det första elementet i listan. Till exempel, bil ([1,2,3,4]) returnerar 1. The CDR funktionen returnerar listan utan det första elementet. Till exempel, CDR ([1,2,3,4]) returnerar [2,3,4]. Vad händer när vi kör summan ([1,2,3,4])?
summa ([1,2,3,4]) 1 + summa ([2,3,4]) 1 + (2 + summa ([3,4])) 1 + (2 + (3 + summa 1) (2 + (3 + (4 + 0)) 1 + (2 + (3 + 4)) 1 + (2 + (3 + + (2 + 7) 1 + 9 10
När återkommande på en lista, kontrollera om den är tom. Annars gör du det rekursiva steget på en reducerad version av listan.
längd (['a', 'b', 'c', 'd')) bör returnera 4. Skriv vad som händer vid varje steg.I det sista exemplet återvände vi ett nummer. Men anta att vi ville återvända en lista. Det skulle innebära att vi i stället för att lägga till ett nummer till vårt rekursiva steg skulle behöva lägga till en lista. Tänk på funktionen ta bort, som tar en vara och lista som input och returnerar listan med objektet borttaget. Endast det första hittade objektet kommer att tas bort.
funktionen ta bort (item, l) if (empty (l)) return []; annars om (eq (bil (l), objekt)) return cdr (l); else return cons (bil (l), ta bort (item, cdr (l))); ta bort ('c', ['a', 'b', 'c', 'd'] // / '' ',' b ',' d ']Här, den eq funktionen returnerar sant om båda ingångarna är desamma. De nackdelar funktionen tar ett element och en lista som ingångar och returnerar en ny lista med elementet som läggs till i början av det.
Vi kommer att kolla om det första objektet i listan är lika med det objekt vi vill ta bort. Om det är, ta bort det första elementet från listan och returnera den nya listan. Om det första objektet inte är lika med det objekt som vi vill ta bort tar vi det första elementet i listan och lägger till det i det rekursiva steget. Det rekursiva steget kommer att innehålla listan med det första elementet som tagits bort.
Vi kommer att fortsätta att ta bort element tills vi når vårt basfall, vilket är en tom lista. En tom lista innebär att vi har kryssat alla objekt i vår lista. Vad gör ta bort ('c', ['a', 'b', 'c', 'd')) do?
ta bort ('c', ['a', 'b', 'c', 'd']) cons ('a', ta bort ('c', ['b', 'c', ' ) nackdelar ('a', cons ('b', remove ('c', ['c', 'd'])) cons ('a', ['b', 'd']) ['a', 'b', 'd']I en situation när vi behöver bygga en lista tar vi det första elementet och lägger det till den rekursiva delen av vår lista.
ta bort ('c', ['a', 'b', 'c', 'd', 'c'] returnerar ['a', 'b', 'd']. Skriv vad som händer steg för steg.Det finns tre delar till en rekursiv funktion. Den första är basfallet, vilket är avslutningsvillkoren. Det andra är steget för att komma närmare vårt basfall. Den tredje är det rekursiva steget, där funktionen kallar sig med den reducerade ingången.
Rekursion är som iteration. Varje funktion som du kan definiera rekursivt kan också definieras med hjälp av loopar. Andra saker att tänka på när du använder rekursion är återkommande på kapslade listor och optimering av dina rekursiva samtal.
En stor resurs att fortsätta lära sig om rekursion är boken The Little Schemer. Det lär dig hur du tänker rekursivt med hjälp av en fråga och svarformat.
