I denne vejledning lærer du at oprette en rekursiv funktion (en funktion, der kalder sig selv).
Hvad er rekursion?
Rekursion er processen med at definere noget i form af sig selv.
Et fysisk verdenseksempel ville være at placere to parallelle spejle overfor hinanden. Ethvert objekt imellem dem reflekteres rekursivt.
Python rekursiv funktion
I Python ved vi, at en funktion kan kalde andre funktioner. Det er endda muligt for funktionen at kalde sig selv. Disse typer konstruktion betegnes som rekursive funktioner.
Det følgende billede viser funktionen af en rekursiv funktion kaldet recurse.
Rekursiv funktion i Python
Det følgende er et eksempel på en rekursiv funktion til at finde et helt tals faktoria.
Faktor af et tal er produktet af alle heltal fra 1 til det tal. For eksempel er faktor 6 (betegnet som 6!) 1 * 2 * 3 * 4 * 5 * 6 = 720.
Eksempel 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
Faktoren på 3 er 6
I ovenstående eksempel factorial()er en rekursiv funktion, som den kalder sig selv.
Når vi kalder denne funktion med et positivt heltal, kalder den sig selv rekursivt ved at mindske antallet.
Hver funktion multiplicerer tallet med faktoren for tallet under det, indtil det er lig med en. Dette rekursive opkald kan forklares i de følgende trin.
fabrik (3) # 1. opkald med 3 3 * fabrik (2) # 2. opkald med 2 3 * 2 * fabrik (1) # 3. opkald med 1 3 * 2 * 1 # retur fra 3. opkald som nummer = 1 3 * 2 # retur fra 2. opkald 6 # retur fra 1. opkald
Lad os se på et billede, der viser en trinvis proces af, hvad der foregår:
Arbejde med en rekursiv faktorfunktion
Vores rekursion slutter, når antallet reduceres til 1. Dette kaldes basistilstanden.
Hver rekursiv funktion skal have en basistilstand, der stopper rekursionen, ellers kalder funktionen sig uendeligt.
Python-tolkene begrænser dybden af rekursion for at undgå uendelige rekursioner, hvilket resulterer i stackoverløb.
Som standard er den maksimale dybde af rekursion 1000. Hvis grænsen overskrides, resulterer den i RecursionError. Lad os se på en sådan tilstand.
def recursor(): recursor() recursor()
Produktion
Traceback (seneste opkald sidst): File "", line 3, in File "", line 2, in a File "", line 2, in a File "", line 2, in a (Forrige linje gentaget 996 gange mere ) RecursionError: maksimal rekursionsdybde overskredet
Fordele ved rekursion
- Rekursive funktioner får koden til at se ren og elegant ud.
- En kompleks opgave kan opdeles i enklere delproblemer ved hjælp af rekursion.
- Sekvensgenerering er lettere med rekursion end at bruge en indlejret iteration.
Ulemper ved rekursion
- Nogle gange er logikken bag rekursion svært at følge.
- Rekursive opkald er dyre (ineffektive), da de tager meget hukommelse og tid.
- Rekursive funktioner er svære at fejle.
