Hvad er rekursiv funktion?
Funktion kalder sig igen og igen, indtil den opfylder en rekursiv tilstand. En rekursionsfunktion opdeler problemet i mindre problemer og kalder sin egen logik for at løse det mindre problem. Denne teknik er kendt som splittelse og erobring. Det bruges i matematik og computervidenskabsfeltet.
Den rekursive funktion inkluderer en base case (eller terminal case) og en rekursive case. I basissagen kan du overveje det største problem, der skal løses, og den rekursive sag deler problemet op i mindre dele, indtil det når et niveau, hvor det let kan løses. En rekursiv sag kan returnere et resultat, eller den kan kalde sig selv igen for at opdele problemet yderligere. Hver gang problemet opdeles i mindre problem, gemmer funktionen, der bliver kaldt rekursivt, opkaldets tilstand og forventer resultatet fra sig selv efter nedbrydning af problemet.
Rekursiv funktion i Python
Rekursionskonceptet forbliver det samme i Python. Funktionen kalder sig selv til at opdele problemet i mindre problemer. Det enkleste eksempel, vi kunne tænke på rekursion, ville være at finde et nummer.
Lad os sige, at vi er nødt til at finde fabrikken med nummer 5 => 5! (Vores problem)
At finde 5! problemet kan opdeles i mindre 5! => 5 x 4!
Så for at få 5! Vi er nødt til at finde 4! og multiplicer det med 5.
Lad os fortsætte med at dele 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 mindste del, dvs. ved at få fabrikken 1, kan vi returnere resultatet som
Lad os tage et pseudokodeksempel: -
Algoritme til factorial
Lad os se algoritmen til factorial:
function get_factorial( n ):
if n < 2:
return 1
else:
return get_factorial(n -1)
Funktion opkald
Antag, at vi finder et faktablad om 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 bliver 120, hvor vi startede udførelsen af funktionen. Vores rekursionsfunktion stopper, når antallet er så reduceret, at resultatet kan opnås.
- Det første opkald, der får fabrikken til 5, vil resultere i en rekursiv tilstand, hvor det føjes til stakken, og et andet opkald foretages, efter at antallet er reduceret til 4.
- Denne rekursion fortsætter med at kalde og opdele problemet i mindre bidder, indtil det når basistilstanden.
- Basisbetingelsen her er, når tallet er 1.
- Hver rekursiv funktion har sin egen rekursive tilstand og en basisbetingelse.
Fordele og ulemper ved Python rekursiv funktion
- Udførelsen af rekursion er således, at den ikke foretager nogen beregninger, før den når basistilstand.
- Når du når frem til basisbetingelserne, kan du løbe tør for hukommelsen.
- I et stort problem, hvor der kan være en million trin, eller vi kan sige, at en million rekursioner til at udføre programmet kan ende med at give hukommelsesfejl eller en segmenteringsfejl.
- 1000000! = 1000000 * 999999! =?
- Rekursion er anderledes end iteration, den skalereres ikke som en iterativ metode.
- Forskellige sprog har forskellige optimeringer til rekursion.
- På mange sprog ville den iterative metode fungere bedre end rekursion.
- Hvert sprog har nogle begrænsninger i dybden af rekursion, som du måske står overfor, når du løser store problemer.
- Nogle gange er det svært at forstå de komplekse problemer med rekursion, hvorimod det er temmelig enkelt med iteration.
Nogle fordele
- I nogle tilfælde er rekursion en praktisk og hurtigere måde at bruge.
- Meget meget nyttigt i krydset af træet og binær søgning.
Python-kode - rekursion vs itteration
Vi forstod, hvad der er rekursion, og hvordan det fungerer i Python, da vi ved, at alle sprog har forskellige implementeringer af rekursion til hukommelse og beregningsoptimeringer. Der kan være et tilfælde, hvor iteration ville være hurtigere end rekursion.
Her vil vi sammenligne både rekursion og iterationsmetode for at se, hvordan Python klarer sig i begge tilfælde.
1. Rekursionskode til 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. Factorial problem ved hjælp af 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. Udskrivning af resultater
print(get_recursive_factorial(6))
print(get_iterative_factorial(6))
Produktion:
Som vi kan se, giver begge de samme output, som vi har skrevet den samme logik. Her kan vi ikke se nogen forskel i udførelse.
Lad os tilføje nogle tidskoder for at få mere information om udførelse af rekursion og iteration i Python.
Vi importerer "tidsbiblioteket" og kontrollerer, hvad tid rekursion og iteration tager for at returnere resultatet.
4. Kode med tidsberegning
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 vil gennemføre gentagne henrettelser med en anden værdi for factorial og se resultaterne. Nedenstående resultater kan variere fra maskine til maskine. Vi har brugt MacBook Pro 16 GB RAM i7.
Vi bruger Python 3.7 til udførelse
Sag 1: - Factorial af 6:
Sag 2: Factorial af 50:
Sag 3: Factorial af 100:
Sag 4: Factorial af 500:
Sag 5: Factorial af 1000:
Vi har analyseret begge metoder i et andet problem. Derudover har begge opført lignende undtagen tilfælde 4.
I tilfælde 5 fik vi en fejl, mens vi gjorde det med rekursion.
Python fik en begrænsning af den maksimale dybde, du kan gå med rekursion, men det samme problem var jeg i stand til at løse det med iteration.
Python har begrænsninger mod overløbsproblemet. Python er ikke optimeret til halekursur, og ukontrolleret rekursion forårsager en stakoverløb.
"Sys.getrecursionlimit ()" -funktionen fortæller dig grænsen for rekursion.
Rekursionsgrænsen kan ændres, men det anbefales ikke, at det kan være farligt.
Konklusion - Python rekursiv funktion
- Rekursion er en praktisk løsning til nogle problemer som træovergang og andre problemer.
- Python er ikke et funktionelt programmeringssprog, og vi kan se, at rekursionstakken ikke er så optimeret sammenlignet med iteration.
- Vi bør bruge iteration i vores algoritme, da den er mere optimeret i Python og giver dig bedre hastighed.
Anbefalede artikler
Dette er en guide til rekursiv funktion i Python. Her diskuterer vi Hvad er rekursiv funktion, rekursiv funktion i Python, algoritme til faktoriale osv. Du kan også gennemgå vores andre foreslåede artikler for at lære mere–
- Factorial i Python
- Spark Shell-kommandoer
- Bedste C-kompilatorer
- Typer af algoritmer
- Factorial-program i JavaScript
- Vejledning til listen over Unix Shell-kommandoer
- Typer af formularer, der reageres med eksempler