Recursión de cola en Python

1. Recursividad en Python
2. Recursión de cola en Python
3. Llame a la función recursiva de cola en Python
4. Beneficios de las funciones recursivas de cola

En el tutorial de hoy, aprenderemos sobre la recursividad de cola al analizar la recursividad y sus tipos. Además, también aprenderemos cómo llamar a la recursividad de cola en Python y exploraremos algunos beneficios de usarlo.

Recursividad en Python

En informática, la recursión es un método de resolución de problemas en el que una función se llama a sí misma en el cuerpo hasta que se cumple una condición específica.

Es uno de los métodos valiosos y tiene muchos casos de uso de la vida real; sin embargo, tiene algunas limitaciones, y esa es su complejidad espacial y temporal. Veamos un ejemplo de una recursividad a continuación.

Código de ejemplo:

def factorial(n):
    if n == 1 or n == 0:
        return 1
    else:
        return n * factorial(n - 1)  # recursive call


num = 4

# In this case factorial is 4x3x2x1 = 24
print(f"The factorial of {num} is {factorial(num)}")

Producción :

The factorial of 4 is 24

La recursión usa una pila para mantener las variables locales, cada ejecución de las recursiones aumenta su tamaño y el tamaño de la pila es limitado. Es la razón por la que los desarrolladores comenzaron a pensar en algunas soluciones optimizadas.

Es adecuado solo para números pequeños; es por eso que a los desarrolladores se les ocurrió la solución optimizada de recursividad simple, y esa es Tail Recursion.

Tipos de recurrencias

Cuando se trata de funciones recursivas, hay dos tipos principales:

1. recursividad principal
2. recursión de cola

La recursividad de cabeza es cuando la función se llama a sí misma al principio, mientras que la recursividad de cola es cuando una función se llama a sí misma al final de la recursividad.

Ambos tienen ventajas y desventajas, pero la recursión de cola generalmente se considera más eficiente. Vamos a entenderlo con más detalle a continuación.

Recursión de cola en Python

Tail recursion en Python es una solución optimizada para la recursividad simple; permite una recursividad ilimitada sin generar ningún error de desbordamiento de pila.

Pero antes de entrar en los detalles de la recursión de llamada de cola, entendamos la definición de recursión de llamada de cola; la llamada significa que estamos considerando llamar a la función, mientras que la cola significa que es la última. Entonces, llamar al método recursivo de cola significa que la función se llama a sí misma repetidamente desde el final de la función.

Hoy en día, la mayoría de los lenguajes de programación son recursivos de cola, lo que significa que están optimizando las funciones recursivas.

Llame a la función recursiva de cola en Python

Hay dos formas de llamar a una función recursiva de cola en Python. La primera es usar la palabra clave return, y la segunda es usar la palabra clave yield.

Use la palabra clave return para llamar a una función recursiva de cola

En primer lugar, puede utilizar la palabra clave return para devolver un valor de una función. Sin embargo, debe tener cuidado con esta palabra clave, ya que terminará inmediatamente la función.

Significa que solo puede usarlo si está seguro de que la función nunca necesitará volver a llamarse. Recuerde, cuando usamos la palabra clave ‘return’, la función devuelve el último valor calculado.

Es la forma más común de llamar a una función recursiva de cola. Por ejemplo, vea una valla de código a continuación.

Código de ejemplo:

def trisum(n, csum):
    while True:  # Change recursion to a while loop
        if n == 0:
            return csum
        n, csum = n - 1, csum + n  # Update parameters instead of tail recursion


trisum(1000, 0)

Producción :

500500

Use la palabra clave “rendimiento” para llamar a una función recursiva de cola

Otra forma de llamar a funciones recursivas de cola es usar la palabra clave yield. Esta palabra clave le permite devolver un valor de una función sin terminar la función.

Puede llamar a la función repetidamente, devolviendo un valor diferente cada vez. Es útil para funciones que necesitan devolver una gran cantidad de valores.

Al usar la palabra clave rendimiento, la función rendirá el último valor calculado. Es una forma menos común de llamar a una función recursiva de cola, pero puede ser útil en algunos casos.

Código de ejemplo:

def lprint(a):
    if isinstance(a, list):
        for i in a:
            yield from lprint(i)
    else:
        yield a


b = [[1, [2, 3], 4], [5, 6, [7, 8, [9]]]]
for i in lprint(b):
    print(i)

Producción :

1
2
3
4
5
6
7
8
9

Beneficios de las funciones recursivas de cola

Las funciones recursivas de cola son un tipo de función recursiva en la que la última instrucción de la función es una llamada a la función recursiva.

Esta función es más eficiente que las funciones recursivas sin cola porque no requiere que la función realice un seguimiento de los valores intermedios de las llamadas recursivas.

Hace que las funciones recursivas de cola sean más eficientes y fáciles de entender. Hay muchos beneficios al usar funciones recursivas de cola.

1. Uno de los principales beneficios de la recursión de cola es que es más fácil de optimizar. Debido a que la llamada de cola es lo último que sucede en la función, el compilador puede optimizarla más fácilmente. Significa que las funciones recursivas de cola pueden ser más eficientes en términos de tiempo y espacio.
2. Otro beneficio de la recursión de cola es que a menudo es más fácil de entender. Debido a que la llamada recursiva es lo último que sucede en la función, es más fácil ver lo que sucede. Puede hacer que las funciones recursivas de cola sean más fáciles de depurar y mantener.
3. Son más eficientes que las funciones recursivas sin cola porque evitan la necesidad de realizar un seguimiento de los valores intermedios.
4. Son más fáciles de razonar porque la pila de llamadas de función siempre está vacía al final de la función. Además, las funciones recursivas de cola se pueden paralelizar más fácilmente.
5. Podemos convertirlos fácilmente en programas iterativos, que pueden ser más eficientes en algunos casos.
6. Puede hacer que la función se ejecute más rápido y use menos memoria. Además, puede facilitar la escritura del código correcto.