I denna handledning lär du dig att skapa en rekursiv funktion (en funktion som kallar sig själv).
Vad är rekursion?
Rekursion är processen att definiera något i termer av sig själv.
Ett fysiskt världsexempel skulle vara att placera två parallella speglar mot varandra. Varje objekt däremellan skulle återspeglas rekursivt.
Python rekursiv funktion
I Python vet vi att en funktion kan anropa andra funktioner. Det är till och med möjligt för funktionen att ringa sig själv. Dessa typer av konstruktioner kallas rekursiva funktioner.
Följande bild visar hur en rekursiv funktion kallas recurse.
Rekursiv funktion i Python
Följande är ett exempel på en rekursiv funktion för att hitta faktorn för ett heltal.
Faktorn för ett tal är produkten av alla heltal från 1 till det numret. Till exempel är faktorn 6 (betecknad 6!) 1 * 2 * 3 * 4 * 5 * 6 = 720.
Exempel på en rekursiv funktion
def factorial(x): """This is a recursive function to find the factorial of an integer""" if x == 1: return 1 else: return (x * factorial(x-1)) num = 3 print("The factorial of", num, "is", factorial(num))
Produktion
Faktorn 3 är 6
I exemplet ovan factorial()är en rekursiv funktion som den kallar sig själv.
När vi kallar denna funktion med ett positivt heltal kommer den rekursivt att ringa sig själv genom att minska antalet.
Varje funktion multiplicerar talet med faktorn för numret under det tills det är lika med en. Detta rekursiva samtal kan förklaras i följande steg.
fabrik (3) # 1: a samtal med 3 3 * fabrik (2) # 2: a samtal med 2 3 * 2 * fabrik (1) # 3: e samtal med 1 3 * 2 * 1 # retur från 3: e samtal som nummer = 1 3 * 2 # retur från andra samtalet 6 # retur från första samtalet
Låt oss titta på en bild som visar en steg-för-steg-process av vad som händer:
Arbetar med en rekursiv faktorfunktion
Vår rekursion slutar när antalet minskar till 1. Detta kallas basvillkoret.
Varje rekursiv funktion måste ha ett grundförhållande som stoppar rekursion eller annars kallar funktionen sig oändligt.
Python-tolken begränsar djupet av rekursion för att undvika oändliga rekursioner, vilket resulterar i stacköverflöden.
Som standard är det maximala rekursionsdjupet 1000. Om gränsen överskrids resulterar det i RecursionError. Låt oss titta på ett sådant tillstånd.
def recursor(): recursor() recursor()
Produktion
Spårning (senaste samtalet senast): Fil "", rad 3, i fil "", rad 2, i en fil "", rad 2, i en fil "", rad 2, i en (föregående rad upprepad 996 gånger till ) Rekursionsfel: maximalt rekursionsdjup överskridits
Fördelar med rekursion
- Rekursiva funktioner gör att koden ser ren och elegant ut.
- En komplex uppgift kan delas upp i enklare delproblem med rekursion.
- Sekvensgenerering är lättare med rekursion än att använda någon kapslad iteration.
Nackdelar med rekursion
- Ibland är logiken bakom rekursion svår att följa igenom.
- Rekursiva samtal är dyra (ineffektiva) eftersom de tar mycket minne och tid.
- Rekursiva funktioner är svåra att felsöka.
