Rekurzija v Pythonu
Izraz rekurzija je mogoče definirati kot proces definiranja nečesa v smislu samega sebe. Preprosto povedano, to je proces, v katerem funkcija neposredno ali posredno kliče samo sebe.
Prednosti uporabe rekurzije
- Zapleteno funkcijo je mogoče razdeliti na manjše podprobleme z uporabo rekurzije.
- Ustvarjanje zaporedja je preprostejše z rekurzijo kot uporaba katere koli ugnezdene iteracije.
- Zaradi rekurzivnih funkcij je koda videti preprosta in učinkovita.
Slabosti uporabe rekurzije
- Rekurzivni klici vzamejo veliko pomnilnika in časa, zaradi česar je uporaba draga.
- Rekurzivne funkcije je težko odpraviti.
- Razloge za rekurzijo je včasih težko premisliti.
Sintaksa:
def func(): <-- | | (recursive call) | func() ----
Primer 1: Fibonaccijevo zaporedje je celoštevilsko zaporedje 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))> |
Izhod
Fibonacci series: 0 1 1 2 3 5 8 13 21 34
Primer 2: Faktoriel 6 je označen kot 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))> |
Izhod
Factorial of number 6 = 720
Kaj je repna rekurzija?
Edinstvena vrsta rekurzije, kjer je zadnji postopek funkcije rekurziven klic. Rekurzijo lahko avtomatizirate tako, da izvedete zahtevo v trenutnem okvirju sklada in vrnete izhod namesto generiranja novega okvira sklada. Repno rekurzijo lahko optimizira prevajalnik, zaradi česar je boljša od rekurzivnih funkcij brez repa.
Ali je mogoče optimizirati program z uporabo repne rekurzivne funkcije namesto nerepne rekurzivne funkcije?
Če upoštevamo spodnjo funkcijo za izračun faktoriala n, lahko opazimo, da je funkcija na začetku videti kot repna rekurzivna, vendar je nerekurzivna funkcija. Če pozorno opazujemo, lahko vidimo, da je vrednost, ki jo vrne Recur_facto(n-1), uporabljena v Recur_facto(n), tako da klic Recur_facto(n-1) ni zadnja stvar, ki jo naredi 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> ))> |
Izhod
720
Dano funkcijo Recur_facto lahko zapišemo kot repno rekurzivno funkcijo. Ideja je, da uporabimo še en argument in v drugem argumentu prilagodimo vrednost faktoriala. Ko n doseže 0, vrne končno vrednost faktoriala želenega števila.
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> ))> |
Izhod
720
