Rekursion är ett roligt programmeringskoncept men kan vara lite knepigt att lära sig. Rekursion betyder helt enkelt något som upprepar sig. Om du vill se ett fräckt exempel på rekursion, försök att söka efter rekursion på Google. Du hittar ett påskägg där förslagen på sökresultat är rekursiva. Om du däremot skulle vilja lära dig hur man kodar en rekursiv funktion, läs vidare!
Vad är en rekursiv funktion?
En rekursiv funktion är en funktion som kallar sig själv. Du skapar i princip en loop med en funktion. Som du kan föreställa dig kan det här vara knepiga funktioner att skriva. Du vill inte att din kod ska köras för alltid.
I likhet med en loop kommer en rekursiv funktion att styras av ett villkor. När villkoret är uppfyllt slutar funktionen att anropa sig själv, vilket stoppar loopen. Så här kan du skapa en funktion som kallar sig själv utan att den körs för alltid.
Även om en rekursiv funktion fungerar som en loop, exekveras den på olika sätt av datorn. Så, vissa algoritmer är mer effektiva i en loop och andra drar nytta av en rekursiv funktion. Men innan vi tittar på hur man använder en rekursiv funktion måste du veta hur man skriver en.
Hur man skriver en rekursiv funktion
Alla rekursiva funktioner har samma grundstruktur:
FUNCTION name
IF condition THEN
RETURN result
ELSE
CALL FUNCTION name
END FUNCTION
Ovanstående exempel är skrivet i pseudokod. Den beskriver strukturen för funktionen, som kan tillämpas på alla språk. För enkelhetens skull kommer vi i den här artikeln att koncentrera oss på Python.
Det första att notera om en rekursiv funktion är att när villkoret är uppfyllt lämnar funktionen rekursionen. Det betyder att när du skriver en rekursiv funktion är det första du vill bestämma när du ska stoppa rekursionen.
Om villkoret inte är uppfyllt anropar funktionen sig själv. Så om du vill skicka information till nästa loop måste du skicka den som ett argument i din funktion. Detta kan ge rekursiva funktioner mycket mer kraft.
Exempel på rekursiv funktion i Python
Det blir mycket lättare att förstå hur rekursion fungerar när du ser den i aktion. För att demonstrera det, låt oss skriva en rekursiv funktion som returnerar faktorialen för ett tal.
Faktorer returnerar produkten av ett tal och av alla heltal före det. Till exempel är faktorvärdet 5 5 x 4 x 3 x 2 x 1 eller 120.
def factorialFunction(numberToMultiply):
if numberToMultiply == 1 :
return 1
else :
return numberToMultiply * factorialFunction(numberToMultiply - 1)result = factorialFunction(3)
print(result)
//Outputs: 6
Ovanstående program kommer att ge dig resultatet 6, vilket är faktorn för siffran 3. Detta kan vara lite förvirrande till en början. Det hjälper om vi går igenom programmet steg för steg.
- När funktionen anropas, numberToMultiply är lika med 3. Villkoret är inte uppfyllt, så vi går in på annan skick. Vår funktion returnerar 3 * men pausas sedan. Den måste anropa sig själv för att bestämma resten av värdet den returnerar. När funktionen anropas den här gången är värdet på numberToMultiply lika med 2. Villkoret är inte uppfyllt, så vi går in på else-villkoret. Vår funktion returnerar 2 * men pausas sedan. Den måste anropa sig själv för att bestämma resten av värdet den returnerar. Funktionen anropas igen. Den här gången är värdet på numberToMultiply lika med 1. Vår om villkoret är uppfyllt. Funktionen returnerar 1. Funktionen från steg 6 kan nu returnera 2 * 1 till funktionen på steg 3. Funktionen på steg tre kan nu returnera 3 * 2 * 1, vilket är 6.
Rekursion är ett knepigt begrepp. Det kan vara bra att tänka på det som att stapla en funktion ovanpå en annan. När en funktion äntligen är löst, kan den skicka informationen tillbaka ner i stacken, tills alla funktioner har sitt svar.
Detta är faktiskt ungefär vad din dator gör. När du anropar funktionen hålls den i minnet tills den returneras. Detta innebär att rekursiva funktioner kan använda mycket mer minne än en loop.
Så det kanske inte är effektivt att skriva loopar som rekursiva funktioner, men det är ett bra sätt att träna på att konstruera dem. Du bör kunna koda loopar som rekursiva funktioner med liknande resultat.
Ett exempel på hur man konverterar en loop till en rekursiv funktion
print("Enter an even number:")
i = int(input())
while (i % 2) != 0 :
print("That number is not even. Please enter a new number:")
i = int(input())
Denna loop kan också skrivas rekursivt som:
def recursiveFunction(number) :
if (number % 2) == 0 :
return number
else:
print("That number is not even. Please enter a new number:")
recursiveFunction(int(input()))print("Enter and even number:")
i = recursiveFunction(int(input()))
Det första steget är att bestämma när du vill att din funktion ska stoppas. I det här fallet vill vi att det slutar när ett jämnt tal har angetts. I vårt exempel, siffra spårar användarens input. Om de matar in ett jämnt tal returnerar vi numret. Annars kommer vi att fortsätta att be om ett nytt nummer.
För att sätta upp slingan anropar vi vår funktion igen. Men den här gången är numret vi skickar till nästa funktion det nya numret som användaren matat in. Nästa funktionsanrop kommer att kontrollera numret.
Detta är en riktigt dålig funktion! Ja, den kontrollerar om numret är jämnt, som vår loop, men det är inte effektivt. Varje gång användaren anger ett udda nummer hålls funktionen i minnet och en ny funktion anropas. Om du gör detta tillräckligt många gånger kommer du få ont om minne!
Ett verkligt exempel på en rekursiv funktion
Ovanstående exempel var bra exempel på när man inte ska använda rekursion. Så, var används rekursion? Ett bra exempel på när du skulle vilja använda rekursion är att söka i ett binärt träd.
När data är strukturerad i ett binärt träd måste du gå ner på många vägar för att söka efter data. Vid varje punkt i trädet måste du bestämma om du vill fortsätta söka till höger eller vänster. Du kan spara vilken del av trädet du besökte i en variabel, men en rekursiv funktion kan naturligtvis spåra den informationen.
Föreställ dig att vi letar efter siffran sex i trädet ovan. Vi skulle kunna göra en rekursiv funktion som söker i trädet från vänster till höger. Algoritmen skulle se ut ungefär så här:
FUNCTION searchTree(branchToSearch)
IF find 6 OR end of tree THEN
RETURN result
ELSE
PROCESS branch
CALL FUNCTION searchTree(left)
CALL FUNCTION searchTree(right)
END FUNCTION
I det här pseudokodexemplet skulle algoritmen först söka på vänster sida av trädet. Varje gång den besöker ett nytt nummer pausas funktionen och sparas i minnet. Detta gör att vi kan spåra var vi har varit.
Algoritmen kommer alltid att söka på vänster sida så långt den kan först. när den når slutet av trädet kommer sökträdet (vänster) att slutföras och det kommer att kontrollera den högra sidan. När båda sidor är kontrollerade, backar sökningen upp en gren och fortsätter att kontrollera den högra sidan.
Om algoritmerna sökte igenom hela trädet, skulle det göra det i följande ordning:
2, 7, 2, 6, 5, 11, 5, 9 och 4
Se om du kan följa med med pseudokoden ovan.
Recension av Rekursion
Rekursion är ett avancerat ämne. Det kommer att ta lite tid att förstå och ännu längre tid att bli bra på att koda det. Det hjälper om du går igenom rekursiva funktioner steg för steg. Det kan till och med hjälpa att stapla registerkort eller post-it-lappar när du går igenom en funktion när du lär dig representera varje funktionsanrop.
När du skriver en rekursiv funktion, börja med att bestämma hur du vill avsluta funktionen. Bestäm sedan hur du ställer in din loop. Identifiera vilken information som behöver skickas till nästa funktionsanrop och vad som behöver returneras.
Det bästa sättet att lära sig rekursion är att öva på det och lära av dina misstag. Titta på lite av din gamla kod och utmana dig själv att skriva om loopar som rekursiva funktioner. Det kommer sannolikt inte att göra din kod mer effektiv, men det kommer att vara bra praxis.
Om författaren
Jennifer Seaton (21 artiklar publicerade)
J. Seaton är en vetenskapsskribent som specialiserat sig på att bryta ner komplexa ämnen. Hon har en doktorsexamen från University of Saskatchewan; hennes forskning fokuserade på att använda spelbaserat lärande för att öka elevernas engagemang online. När hon inte arbetar hittar du henne när hon läser, spelar tv-spel eller trädgårdsarbete.
Mer från Jennifer Seaton
Prenumerera på vårt nyhetsbrev
Gå med i vårt nyhetsbrev för tekniska tips, recensioner, free e-böcker och exklusiva erbjudanden!
Klicka här för att prenumerera
