Recursiune în Python
Termenul de recursivitate poate fi definit ca procesul de definire a ceva în termenii însuși. Cu cuvinte simple, este un proces în care o funcție se numește direct sau indirect.
Avantajele utilizării recursiunii
- O funcție complicată poate fi împărțită în sub-probleme mai mici utilizând recursiunea.
- Crearea secvenței este mai simplă prin recursivitate decât utilizarea oricărei iterații imbricate.
- Funcțiile recursive fac codul să arate simplu și eficient.
Dezavantajele utilizării recursiunii
- O mulțime de memorie și timp sunt luate prin apeluri recursive, ceea ce îl face costisitor pentru utilizare.
- Funcțiile recursive sunt dificil de depanat.
- Raționamentul din spatele recursiunii poate fi uneori greu de gândit.
Sintaxă:
def func(): <-- | | (recursive call) | func() ----
Exemplul 1: O secvență Fibonacci este șirul întreg de 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))> |
Ieșire
Fibonacci series: 0 1 1 2 3 5 8 13 21 34
Exemplul 2: Factorialul lui 6 este notat cu 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))> |
Ieșire
Factorial of number 6 = 720
Ce este Tail-Recursion?
Un tip unic de recursivitate în care ultima procedură a unei funcții este un apel recursiv. Recursiunea poate fi automatizată prin efectuarea cererii în cadrul de stivă curent și returnarea ieșirii în loc de a genera un nou cadru de stivă. Recursiunea coadă poate fi optimizată de compilator, ceea ce o face mai bună decât funcțiile recursive non-coadă.
Este posibil să se optimizeze un program utilizând o funcție recursivă coadă în loc de funcția recursivă non-coadă?
Având în vedere funcția dată mai jos pentru a calcula factorialul lui n, putem observa că funcția arată la început ca o coadă-recursivă, dar este o funcție non-coadă-recursivă. Dacă observăm îndeaproape, putem vedea că valoarea returnată de Recur_facto(n-1) este folosită în Recur_facto(n), deci apelul la Recur_facto(n-1) nu este ultimul lucru făcut de 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> ))> |
Ieșire
720
Putem scrie funcția dată Recur_facto ca o funcție recursivă de coadă. Ideea este să folosim încă un argument și în al doilea argument, găzduim valoarea factorialului. Când n ajunge la 0, returnează valoarea finală a factorialului numărului dorit.
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> ))> |
Ieșire
720
