El término recursión se puede definir como el proceso de definir algo en términos de sí mismo. En palabras simples, es un proceso en el que una función se llama a sí misma directa o indirectamente.
Ventajas de usar la recursividad
- Una función complicada se puede dividir en subproblemas más pequeños mediante la recursividad.
- La creación de secuencias es más sencilla mediante la recursividad que utilizando cualquier iteración anidada.
- Las funciones recursivas hacen que el código parezca simple y efectivo.
Desventajas de usar la recursividad
- Se consume mucha memoria y tiempo a través de llamadas recursivas, lo que hace que su uso sea costoso.
- Las funciones recursivas son difíciles de depurar.
- A veces puede resultar difícil analizar el razonamiento detrás de la recursividad.
Sintaxis:
def func(): <-- | | (recursive call) | func() ---->
Ejemplo 1: Una secuencia de Fibonacci es la secuencia entera 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))> |
>
>Producción
Fibonacci series: 0 1 1 2 3 5 8 13 21 34>
Ejemplo 2: ¡El factorial de 6 se denota como 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))> |
cadena a json java
>
>Producción
Factorial of number 6 = 720>
¿Qué es la recursividad de cola?
Un tipo único de recursividad donde el último procedimiento de una función es una llamada recursiva. La recursividad se puede automatizar realizando la solicitud en el marco de pila actual y devolviendo la salida en lugar de generar un nuevo marco de pila. El compilador puede optimizar la recursividad de cola, lo que la hace mejor que las funciones recursivas sin cola.
¿Es posible optimizar un programa haciendo uso de una función recursiva de cola en lugar de una función recursiva sin cola?
Considerando la función que se proporciona a continuación para calcular el factorial de n, podemos observar que la función parece una función recursiva de cola al principio, pero no es una función recursiva de cola. Si observamos de cerca, podemos ver que el valor devuelto por Recur_facto(n-1) se usa en Recur_facto(n), por lo que la llamada a Recur_facto(n-1) no es lo último que hace 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>))> |
>
>Producción
int a carbón
720>
Podemos escribir la función dada Recur_facto como una función recursiva de cola. La idea es usar un argumento más y en el segundo argumento acomodamos el valor del factorial. Cuando n llega a 0, devuelve el valor final del factorial del número deseado.
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>))> |
>
>Producción
720>