Rekursion i Python
Begrebet rekursion kan defineres som processen med at definere noget ud fra sig selv. Med enkle ord er det en proces, hvor en funktion kalder sig selv direkte eller indirekte.
Fordele ved at bruge rekursion
- En kompliceret funktion kan opdeles i mindre delproblemer ved at bruge rekursion.
- Sekvensoprettelse er enklere gennem rekursion end ved at bruge nogen indlejret iteration.
- Rekursive funktioner får koden til at se enkel og effektiv ud.
Ulemper ved at bruge rekursion
- Der tages meget hukommelse og tid gennem rekursive opkald, hvilket gør det dyrt at bruge.
- Rekursive funktioner er udfordrende at fejlfinde.
- Begrundelsen bag rekursion kan nogle gange være svær at tænke igennem.
Syntaks:
def func(): <-- | | (recursive call) | func() ----
Eksempel 1: En Fibonacci-sekvens er heltalssekvensen af 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))> |
Produktion
Fibonacci series: 0 1 1 2 3 5 8 13 21 34
Eksempel 2: Faktorialet på 6 er angivet 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))> |
Produktion
Factorial of number 6 = 720
Hvad er hale-rekursion?
En unik type rekursion, hvor den sidste procedure i en funktion er et rekursivt kald. Rekursionen kan automatiseres væk ved at udføre anmodningen i den aktuelle stakramme og returnere output i stedet for at generere en ny stakramme. Halerekursionen kan optimeres af compileren, hvilket gør den bedre end ikke-halerekursive funktioner.
Er det muligt at optimere et program ved at gøre brug af en hale-rekursiv funktion i stedet for ikke-hale-rekursiv funktion?
I betragtning af funktionen nedenfor for at beregne faktoren af n, kan vi observere, at funktionen ser ud som en hale-rekursiv i starten, men det er en ikke-hale-rekursiv funktion. Hvis vi observerer nøje, kan vi se, at værdien returneret af Recur_facto(n-1) bruges i Recur_facto(n), så kaldet til Recur_facto(n-1) er ikke det sidste, der udføres af 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> ))> |
Produktion
720
Vi kan skrive den givne funktion Recur_facto som en hale-rekursiv funktion. Ideen er at bruge et argument mere, og i det andet argument rummer vi værdien af faktorialet. Når n når 0, returneres den endelige værdi af fakultetet for det ønskede tal.
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> ))> |
Produktion
720
