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 mod hinanden. Ethvert objekt imellem dem ville blive reflekteret 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.

følgende billede viser funktionen af en rekursiv funktion kaldetrecurse.

Følgende er et eksempel på en rekursiv funktion til at finde faktorialet for et heltal.

Factorial af et tal er produktet af alle heltal fra 1 til dette tal. For eksempel er faktorialet af 6 (betegnet som 6!) er 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 = 3print("The factorial of", num, "is", factorial(num))

Output

The factorial of 3 is 6

i ovenstående eksempelfactorial() er en rekursiv funktion, som den kalder sig selv.

når vi kalder denne funktion Med et positivt heltal, vil det rekursivt kalde sig ved at reducere nummeret.

hver funktion multiplicerer tallet med faktorialet for tallet under det, indtil det er lig med et. Dette rekursive opkald kan forklares i følgende trin.

factorial(3) # 1st call with 33 * factorial(2) # 2nd call with 23 * 2 * factorial(1) # 3rd call with 13 * 2 * 1 # return from 3rd call as number=13 * 2 # return from 2nd call6 # return from 1st call

lad os se på et billede, der viser en trinvis proces af, hvad der foregår:

vores rekursion slutter, når antallet reduceres til 1. Dette kaldes basisbetingelsen.

hver rekursiv funktion skal have en basisbetingelse, der stopper rekursionen, ellers kalder funktionen sig uendeligt.Python-tolken begrænser dybden af rekursion for at undgå uendelige rekursioner, hvilket resulterer i stakoverløb.

som standard er den maksimale dybde af rekursion 1000. Hvis grænsen krydses, resulterer den i RecursionError. Lad os se på en sådan tilstand.

def recursor(): recursor()recursor()

Output

Traceback (most recent call last): File "<string>", line 3, in <module> File "<string>", line 2, in a File "<string>", line 2, in a File "<string>", line 2, in a RecursionError: maximum recursion depth exceeded

fordele ved rekursion

1. rekursive funktioner får koden til at se ren og elegant ud.
2. en kompleks opgave kan opdeles i enklere underproblemer ved hjælp af rekursion.
3. Sekvensgenerering er lettere med rekursion end at bruge en indlejret iteration.

ulemper ved rekursion

1. nogle gange er logikken bag rekursion svært at følge igennem.
2. rekursive opkald er dyre (ineffektive), da de tager meget hukommelse og tid.
3. rekursive funktioner er svære at debugge.