El terme recursivitat es pot definir com el procés de definir alguna cosa en termes de si mateix. En paraules simples, és un procés en el qual una funció s'anomena directament o indirectament.
Avantatges de l'ús de la recursivitat
- Una funció complicada es pot dividir en subproblemes més petits mitjançant recursivitat.
- La creació de seqüències és més senzilla mitjançant la recursivitat que la utilització de qualsevol iteració imbricada.
- Les funcions recursives fan que el codi sembli senzill i efectiu.
Inconvenients de l'ús de la recursivitat
- Es pren molta memòria i temps a través de trucades recursives, cosa que fa que el seu ús sigui car.
- Les funcions recursives són difícils de depurar.
- El raonament de la recursivitat de vegades pot ser difícil de pensar.
Sintaxi:
def func(): <-- | | (recursive call) | func() ---->
Exemple 1: Una successió de Fibonacci és la seqüència entera de 0, 1, 1, 2, 3, 5, 8...
Python 3
# 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))> |
>
>Sortida
Fibonacci series: 0 1 1 2 3 5 8 13 21 34>
Exemple 2: El factorial de 6 es denota com 6! = 1*2*3*4*5*6 = 720.
Python 3
# 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))> |
>
conjunt mecanografiat
>Sortida
Factorial of number 6 = 720>
Què és Tail-Recursion?
Un tipus únic de recursivitat on l'últim procediment d'una funció és una crida recursiva. La recursivitat es pot automatitzar mitjançant la realització de la sol·licitud al marc de pila actual i retornant la sortida en lloc de generar un nou marc de pila. El compilador pot optimitzar la recursivitat de la cua, cosa que la fa millor que les funcions recursives sense cua.
És possible optimitzar un programa fent ús d'una funció recursiva de la cua en lloc d'una funció recursiva no de la cua?
Tenint en compte la funció que es mostra a continuació per calcular el factorial de n, podem observar que la funció sembla una recursiva de cua al principi, però és una funció no recursiva de la cua. Si observem de prop, podem veure que el valor retornat per Recur_facto(n-1) s'utilitza a Recur_facto(n), de manera que la crida a Recur_facto(n-1) no és l'última cosa que fa Recur_facto(n).
Python 3
emojis d'iphone al telèfon Android
# 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>))> |
>
>Sortida
720>
Podem escriure la funció donada Recur_facto com a funció recursiva de la cua. La idea és utilitzar un argument més i en el segon argument, ens adaptem al valor del factorial. Quan n arriba a 0, retorna el valor final del factorial del nombre desitjat.
Python 3
# 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>))> |
>
>Sortida
720>