Vad är rekursiv funktion?
Funktion kallar sig igen och igen tills den uppfyller ett rekursivt skick. En rekursionsfunktion delar upp problemet i mindre problem och kallar sin egen logik för att lösa det mindre problemet. Denna teknik är känd som splittring och erövring. Det används inom matematik och datavetenskap.
Den rekursiva funktionen inkluderar ett basfall (eller terminalfall) och ett rekursivt fall. I grundfallet kan du överväga det stora problemet att lösa och det rekursiva fallet delar upp problemet i mindre delar tills det når en nivå där det enkelt kan lösas. Ett rekursivt fall kan returnera ett resultat eller det kan kalla sig igen för att ytterligare dela problemet. Varje gång problemet bryts ned till mindre problem sparar funktionen som kallas rekursivt samtalstillståndet och förväntar sig resultatet från sig själv efter att problemet har brutits ner.
Rekursiv funktion i Python
Rekursionsbegreppet förblir detsamma i Python. Funktionen kallar sig själv att dela upp problemet i mindre problem. Det enklaste exemplet som vi skulle kunna tänka oss på rekursion skulle vara att hitta en siffra.
Låt oss säga att vi måste hitta faktorn för nummer 5 => 5! (Vårt problem)
Att hitta 5! problemet kan delas upp i mindre 5! => 5 x 4!
Så för att få 5! Vi måste hitta 4! och multiplicera det med 5.
Låt oss fortsätta dela problemet
5! = 4! x 5
4! = 3! x 4
3! = 3 x 2!
2! = 2 x 1!
1! = 1
När den når den minsta biten, dvs genom att få fabriken 1 kan vi returnera resultatet som
Låt oss ta ett pseudokodsexempel: -
Algoritm för factorial
Låt oss se algoritmen för factorial:
function get_factorial( n ):
if n < 2:
return 1
else:
return get_factorial(n -1)
Funktionssamtal
Anta att vi hittar ett faktorium av 5.
get_factorial(5) 5 * get_factorial(4) = returns 120 #1st call
get_factorial(4) 4 * get_factorial(3) = returns 24 #2nd call
get_factorial(3) 3 * get_factorial(2) = returns 6 #3rd call
get_factorial(2) 2 * get_factorial(1) = returns 2 #4th call
get_factorial(1) returns 1 #5th call
Slutresultatet blir 120 där vi startade exekveringen av funktionen. Vår rekursionsfunktion kommer att stanna när antalet är så reducerat att resultatet kan uppnås.
- Det första samtalet som får faktorn 5 kommer att resultera i ett rekursivt tillstånd där det kommer att läggas till bunten och ytterligare ett samtal kommer att göras efter att antalet har minskat till 4.
- Denna rekursion fortsätter att ringa och bryta problemet i mindre bitar tills det når bastillståndet.
- Basvillkoret här är när siffran är 1.
- Varje rekursiv funktion har sitt eget rekursiva tillstånd och ett bastillstånd.
Fördelar och nackdelar med Python rekursiv funktion
- Utförandet av rekursion är så att det inte kommer att göra några beräkningar förrän når basvillkoret.
- När du når basförhållandena kan du hålla slut på minnet.
- I ett stort problem där det kan finnas en miljon steg eller vi kan säga att en miljon rekursioner för att göra programmet kan sluta ge minnesfel eller ett segmenteringsfel.
- 1000000! = 1000000 * 999999! =?
- Rekursion är annorlunda än iteration, den skalas inte upp som en iterativ metod.
- Olika språk har olika optimeringar för rekursion.
- På många språk skulle den iterativa metoden fungera bättre än rekursion.
- Varje språk har vissa begränsningar för rekursionsdjupet som du kan möta när du löser stora problem.
- Ibland är det svårt att förstå de komplexa problemen med rekursion medan det är ganska enkelt med iteration.
Några fördelar
- I vissa fall är rekursion ett bekvämt och snabbare sätt att använda.
- Mycket användbart vid korsningen av trädet och binär sökning.
Python Code - Rekursion vs Iteration
Vi förstod vad som är rekursion och hur det fungerar i Python, eftersom vi vet att alla språk har olika implementering av rekursion för minne och beräkningsoptimeringar. Det kan finnas ett fall där iteration skulle vara snabbare än rekursion.
Här skulle vi jämföra både rekursions- och iterationsmetod för att se hur Python presterar i båda fallen.
1. Rekursionskod för Factorial
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2: #base condition
return 1
else:
return n * get_recursive_factorial(n -1) #recursion condition
2. Faktoriellt problem med iteration (looping)
def get_iterative_factorial(n):
if n < 0:
return -1
else:
fact = 1
for i in range( 1, n+1 ):
fact *= i
return fact
3. Skriva ut resultat
print(get_recursive_factorial(6))
print(get_iterative_factorial(6))
Produktion:
Som vi ser båda ger samma output som vi har skrivit samma logik. Här kan vi inte se någon skillnad i utförandet.
Låt oss lägga till lite tidskod för att få mer information om utförandet av rekursion och iteration i Python.
Vi kommer att importera "tid" -biblioteket och kontrollera vilken tid rekursion och iteration tar för att returnera resultatet.
4. Kod med tidsberäkning
import time
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2:
return 1
else:
return n * get_recursive_factorial(n-1)
def get_iterative_factorial(n):
if n < 0 :
return -1
else:
fact = 1
for i in range(1, n+1):
fact *= i
return fact
start_time = time.time()
get_recursive_factorial(100)
print("Recursion--- %s seconds ---" % (time.time() - start_time))
start_time = time.time()
get_iterative_factorial(100)
print("Iteration--- %s seconds ---" % (time.time() - start_time))
Vi kommer att göra upprepade avrättningar med ett annat värde för factorial och se resultaten. Nedanstående resultat kan variera från maskin till maskin. Vi har använt MacBook Pro 16 GB RAM i7.
Vi använder Python 3.7 för körning
Fall 1: - Factorial of 6:
Fall 2: Factorial of 50:
Fall 3: Factorial of 100:
Fall 4: Factorial of 500:
Fall 5: Factorial av 1000:
Vi har analyserat båda metoderna i ett annat problem. Dessutom har båda utfört liknande utom fall 4.
I fall 5 fick vi ett fel när vi gjorde det med rekursion.
Python fick en begränsning av det maximala djupet du kan gå med rekursion men samma problem jag kunde lösa det med iteration.
Python har begränsningar mot överflödesproblemet. Python är inte optimerad för svansrekursion, och okontrollerad rekursion orsakar ett stacköverskridande.
"Sys.getrecursionlimit ()" -funktionen skulle säga gränsen för rekursion.
Rekursionsgränsen kan ändras men rekommenderas inte att det kan vara farligt.
Slutsats - Python rekursiv funktion
- Rekursion är en praktisk lösning för vissa problem som trädkorsning och andra problem.
- Python är inte ett funktionellt programmeringsspråk och vi kan se rekursionsstacken är inte så optimerad jämfört med iteration.
- Vi bör använda iteration i vår algoritm eftersom den är mer optimerad i Python och ger dig bättre hastighet.
Rekommenderade artiklar
Detta är en guide till rekursiv funktion i Python. Här diskuterar vi vad som är rekursiv funktion, rekursiv funktion i Python, algoritm för fakultet etc. Du kan också gå igenom våra andra föreslagna artiklar för att lära dig mer–
- Factorial i Python
- Spark Shell-kommandon
- Bästa C-kompilatorer
- Typer av algoritmer
- Factorial-program i JavaScript
- Guide till listan över Unix Shell-kommandon
- Typer av formulär som reagerar med exempel