Hva er rekursiv funksjon?
Funksjon kaller seg igjen og igjen til den tilfredsstiller en rekursiv tilstand. En rekursjonsfunksjon fordeler problemet i mindre problemer og kaller sin egen logikk for å løse det mindre problemet. Denne teknikken er kjent som splitt og erobre. Det brukes i matematikk og informatikkfeltet.
Den rekursive funksjonen inkluderer en base case (eller terminal case) og en rekursive case. I basissaken kan du vurdere det største problemet å løse, og den rekursive saken deler opp problemet i mindre deler til det når et nivå der det lett kan løses. En rekursiv sak kan gi et resultat, eller den kan kalle seg igjen for å dele problemet ytterligere. Hver gang problemet brytes ned til mindre problem, lagrer funksjonen som blir kalt rekursivt tilstanden for samtalen og forventer resultatet fra seg selv etter å ha brutt ned problemet.
Rekursiv funksjon i Python
Rekursjonbegrepet forblir det samme i Python. Funksjonen kaller seg selv å fordele problemet i mindre problemer. Det enkleste eksemplet vi kunne tenke oss rekursjon ville være å finne faktabladet til et tall.
La oss si at vi trenger å finne fakultetet til nummer 5 => 5! (Vårt problem)
For å finne 5! problemet kan deles inn i mindre 5! => 5 x 4!
Så, for å få 5! Vi trenger å finne 4! og multipliser det med 5.
La oss fortsette å 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 minste delen, dvs. får fabrikken 1 kan vi returnere resultatet som
La oss ta et pseudokodeksempel: -
Algoritme for fabrikk
La oss se algoritmen for factorial:
function get_factorial( n ):
if n < 2:
return 1
else:
return get_factorial(n -1)
Funksjonssamtaler
Anta at vi finner et fabrikksted 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
Sluttresultatet blir 120 der vi startet utførelsen av funksjonen. Rekursjonsfunksjonen vår vil stoppe når antallet er så redusert at resultatet kan oppnås.
- Den første samtalen som får fakultetet til 5 vil resultere i en rekursiv tilstand der den blir lagt til stabelen og et nytt anrop vil bli foretatt etter å ha redusert tallet til 4.
- Denne rekursjonen fortsetter å ringe og dele problemet i mindre biter til det når basistilstanden.
- Grunnbetingelsen her er når tallet er 1.
- Hver rekursive funksjon har sin egen rekursive tilstand og en grunntilstand.
Fordeler og ulemper med Python rekursiv funksjon
- Utførelsen av rekursjon er slik at den ikke gjør noen beregninger før når basistilstanden.
- Når du når basisforholdene, kan det hende at du går tom for minne.
- I et stort problem der det kan være en million trinn, eller vi kan si at en million rekursjoner for å gjøre programmet, kan det ende opp med å gi minnefeil eller en segmenteringsfeil.
- 1000000! = 1000000 * 999999! =?
- Rekursjon er annerledes enn iterasjon, den skalerer ikke opp som en iterativ metode.
- Ulike språk har forskjellige optimaliseringer for rekursjon.
- På mange språk vil den iterative metoden fungere bedre enn rekursjon.
- Hvert språk har noen begrensninger for dybden av rekursjon som du kan møte når du løser store problemer.
- Noen ganger er det vanskelig å forstå de komplekse problemene med rekursjon, mens det er ganske enkelt med iterasjon.
Noen fordeler
- I noen tilfeller er rekursjon en praktisk og raskere måte å bruke.
- Veldig mye nyttig i krysset av treet og binært søk.
Python Code - Rekursjon vs Iteration
Vi forsto hva som er rekursjon og hvordan det fungerer i Python, ettersom vi vet at alle språk har ulik implementering av rekursjon for minne og beregningsoptimaliseringer. Det kan være et tilfelle hvor iterasjon vil være raskere enn rekursjon.
Her vil vi sammenligne både rekursjon og iterasjonsmetode for å se hvordan Python presterer i begge tilfeller.
1. Rekursjonskode for 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 hjelp av iterasjon (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. Skrive ut resultater
print(get_recursive_factorial(6))
print(get_iterative_factorial(6))
Produksjon:
Som vi ser begge gir samme output som vi har skrevet den samme logikken. Her kan vi ikke se noen forskjell i utførelse.
La oss legge til litt tidskode for å få mer informasjon om utførelse av rekursjon og iterasjon i Python.
Vi vil importere "tid" -biblioteket og sjekke hvilken tid rekursjon og iterasjon tar for å 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 gjøre gjentatte henrettelser med en annen verdi for factorial og se resultatene. Resultatene nedenfor kan variere fra maskin til maskin. Vi har brukt MacBook Pro 16 GB RAM i7.
Vi bruker Python 3.7 for utførelse
Sak 1: - Factorial av 6:
Sak 2: Factorial av 50:
Sak 3: Factorial av 100:
Sak 4: Factorial of 500:
Sak 5: Factorial av 1000:
Vi har analysert begge metodene i et annet problem. Dessuten har begge utført lignende bortsett fra tilfelle 4.
I tilfelle 5 fikk vi en feil mens vi gjorde det med rekursjon.
Python fikk en begrensning på den maksimale dybden du kan gå med rekursjon, men det samme problemet klarte jeg å løse det med iterasjon.
Python har begrensninger mot overløpsproblemet. Python er ikke optimalisert for rekursjon av haler, og ukontrollert rekursjon fører til et stabilt overløp.
“Sys.getrecursionlimit ()” -funksjonen forteller deg grensen for rekursjon.
Rekursjonsgrensen kan endres, men anbefales ikke at det kan være farlig.
Konklusjon - Python rekursiv funksjon
- Rekursjon er en praktisk løsning for noen problemer som trekjøring og andre problemer.
- Python er ikke et funksjonelt programmeringsspråk, og vi kan se at rekursjonstakken ikke er så optimalisert sammenlignet med iterasjon.
- Vi bør bruke iterasjon i algoritmen vår da den er mer optimalisert i Python og gir deg bedre hastighet.
Anbefalte artikler
Dette er en guide til rekursiv funksjon i Python. Her diskuterer vi Hva er rekursiv funksjon, rekursiv funksjon i Python, algoritme for fakultet osv. Du kan også gå gjennom våre andre foreslåtte artikler for å lære mer–
- Factorial i Python
- Spark Shell-kommandoer
- Beste C-kompilatorer
- Typer av algoritmer
- Factorial-program i JavaScript
- Veiledning til listen over Unix Shell-kommandoer
- Typer skjemaer som reageres med eksempler