Rekursjon i Python
Begrepet rekursjon kan defineres som prosessen med å definere noe i form av seg selv. Med enkle ord er det en prosess der en funksjon kaller seg selv direkte eller indirekte.
Fordeler med å bruke rekursjon
- En komplisert funksjon kan deles ned i mindre delproblemer ved å bruke rekursjon.
- Sekvensoppretting er enklere gjennom rekursjon enn å bruke en nestet iterasjon.
- Rekursive funksjoner gjør at koden ser enkel og effektiv ut.
Ulemper ved å bruke rekursjon
- Det tas mye minne og tid gjennom rekursive samtaler som gjør det dyrt i bruk.
- Rekursive funksjoner er utfordrende å feilsøke.
- Begrunnelsen bak rekursjon kan noen ganger være vanskelig å tenke gjennom.
Syntaks:
def func(): <-- | | (recursive call) | func() ----
Eksempel 1: En Fibonacci-sekvens er heltallssekvensen av 0, 1, 1, 2, 3, 5, 8….
Python3
# Program to print the fibonacci series upto n_terms> # Recursive function> def> recursive_fibonacci(n):> > if> n <> => 1> :> > return> n> > else> :> > return> (recursive_fibonacci(n> -> 1> )> +> recursive_fibonacci(n> -> 2> ))> n_terms> => 10> # check if the number of terms is valid> if> n_terms <> => 0> :> > print> (> 'Invalid input ! Please input a positive value'> )> else> :> > print> (> 'Fibonacci series:'> )> for> i> in> range> (n_terms):> > print> (recursive_fibonacci(i))> |
Produksjon
Fibonacci series: 0 1 1 2 3 5 8 13 21 34
Eksempel 2: Faktorialet på 6 er betegnet som 6! = 1*2*3*4*5*6 = 720.
Python3
# Program to print factorial of a number> # recursively.> # Recursive function> def> recursive_factorial(n):> > if> n> => => 1> :> > return> n> > else> :> > return> n> *> recursive_factorial(n> -> 1> )> # user input> num> => 6> # check if the input is valid or not> if> num <> 0> :> > print> (> 'Invalid input ! Please enter a positive number.'> )> elif> num> => => 0> :> > print> (> 'Factorial of number 0 is 1'> )> else> :> > print> (> 'Factorial of number'> , num,> '='> , recursive_factorial(num))> |
Produksjon
Factorial of number 6 = 720
Hva er hale-rekursjon?
En unik type rekursjon der den siste prosedyren i en funksjon er et rekursivt kall. Rekursjonen kan automatiseres bort ved å utføre forespørselen i gjeldende stabelramme og returnere utdata i stedet for å generere en ny stabelramme. Halerekursjonen kan optimaliseres av kompilatoren som gjør den bedre enn ikke-halerekursive funksjoner.
Er det mulig å optimalisere et program ved å bruke en hale-rekursiv funksjon i stedet for ikke-hale-rekursiv funksjon?
Tatt i betraktning funksjonen gitt nedenfor for å beregne faktoren til n, kan vi observere at funksjonen ser ut som en hale-rekursiv først, men det er en ikke-hale-rekursiv funksjon. Hvis vi observerer nøye, kan vi se at verdien returnert av Recur_facto(n-1) brukes i Recur_facto(n), så kallet til Recur_facto(n-1) er ikke det siste som gjøres av Recur_facto(n).
Python3
# Program to calculate factorial of a number> # using a Non-Tail-Recursive function.> # non-tail recursive function> def> Recur_facto(n):> > > if> (n> => => 0> ):> > return> 1> > > return> n> *> Recur_facto(n> -> 1> )> > # print the result> print> (Recur_facto(> 6> ))> |
Produksjon
720
Vi kan skrive den gitte funksjonen Recur_facto som en hale-rekursiv funksjon. Tanken er å bruke ett argument til, og i det andre argumentet tar vi hensyn til verdien av faktoren. Når n når 0, returner den endelige verdien av faktoren til ønsket tall.
Python3
# Program to calculate factorial of a number> # using a Tail-Recursive function.> # A tail recursive function> def> Recur_facto(n, a> => 1> ):> > > if> (n> => => 0> ):> > return> a> > > return> Recur_facto(n> -> 1> , n> *> a)> > # print the result> print> (Recur_facto(> 6> ))> |
Produksjon
720
