Vad är rekursion?

rekursion är processen att definiera något i sig själv.

ett fysiskt världsexempel skulle vara att placera två parallella speglar mot varandra. Varje objekt mellan dem skulle återspeglas rekursivt.

Python rekursiv funktion

i Python vet vi att en funktion kan ringa 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 arbetet med en rekursiv funktion som heter recurse.

Följande är ett exempel på en rekursiv funktion för att hitta faktoriellt för ett heltal.

faktoriell av ett tal är produkten av alla heltal från 1 till det numret. Till exempel faktoriell av 6 (betecknad som 6!) är 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 = 3print("The factorial of", num, "is", factorial(num))

utgång

The factorial of 3 is 6

i exemplet ovan är factorial() en rekursiv funktion som den kallar sig själv.

När vi kallar denna funktion med ett positivt heltal, kommer det rekursivt att ringa sig själv genom att minska antalet.

varje funktion multiplicerar numret med faktoriellt av numret under det tills det är lika med ett. Detta rekursiva samtal kan förklaras i följande steg.

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

låt oss titta på en bild som visar en steg-för-steg-process av vad som händer:

vår rekursion slutar när antalet minskar till 1. Detta kallas basförhållandet.

varje rekursiv funktion måste ha ETT basförhållande som stoppar rekursionen, 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 korsas resulterar den i RecursionError. Låt oss titta på ett sådant tillstånd.

def recursor(): recursor()recursor()

utgång

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

fördelar med rekursion

1. rekursiva funktioner gör att koden ser ren och elegant ut.
2. en komplex uppgift kan delas upp i enklare delproblem med rekursion.
3. Sekvensgenerering är lättare med rekursion än att använda någon kapslad iteration.

nackdelar med rekursion

1. ibland är logiken bakom rekursion svår att följa igenom.
2. rekursiva samtal är dyra (ineffektiva) eftersom de tar upp mycket minne och tid.
3. rekursiva funktioner är svåra att felsöka.