Comprender las funciones recursivas con Python

Introducción

Cuando pensamos en repetir una tarea, normalmente pensamos en la for y while bucles. Estos constructos nos permiten realizar iteración sobre una lista, colección, etc.

Sin embargo, hay otra forma de repetir una tarea, de una manera ligeramente diferente. Al llamar a una función dentro de sí misma, para resolver una instancia más pequeña del mismo problema, estamos realizando recursividad.

Estas funciones se llaman a sí mismas hasta que se resuelve el problema, dividiendo prácticamente el problema inicial en muchas instancias más pequeñas de sí mismo, como por ejemplo, tomar pequeños bocados de un trozo de comida más grande.

El objetivo final es comerse todo el plato de bolsitas calientes, esto se hace mordiendo una y otra vez. Cada bocado es un recursivo acción, después de la cual emprende la misma acción la próxima vez. Haces esto para cada bocado, evaluando que debes tomar otro para alcanzar la meta, hasta que no queden bolsillos calientes en tu plato.

¿Qué es la recursividad?

Como se indicó en la introducción, recursividad implica un proceso que se autodenomina en la definición. Una función recursiva generalmente tiene dos componentes:

• los caso base que es una condición que determina cuándo debe detenerse la función recursiva
• La llamada a sí misma

Echemos un vistazo a un pequeño ejemplo para demostrar ambos componentes:

# Assume that remaining is a positive integer
def hi_recursive(remaining):
    # The base case
    if remaining == 0:
        return
    print('hi')

    # Call to function, with a reduced remaining count
    hi_recursive(remaining - 1)

los caso base para nosotros es si el remaining variable es igual a 0 es decir, cuántas cadenas de “hola” restantes debemos imprimir. La función simplemente regresa.

Después de la declaración impresa, llamamos hi_recursive de nuevo pero con un valor restante reducido. ¡Esto es importante! Si no disminuimos el valor de remaining la función se ejecutará indefinidamente. Generalmente, cuando una función recursiva se llama a sí misma, los parámetros se cambian para estar más cerca del caso base.

Visualicemos cómo funciona cuando llamamos hi_recursive(3):

Después de que la función imprime ‘hola’, se llama a sí misma con un valor menor para remaining hasta que llegue 0. En cero, la función vuelve a donde fue llamada en hi_recursive(1), que vuelve al lugar donde se llamó hi_recursive(2) y que finalmente regresa a donde fue llamado en hi_recursive(3).

¿Por qué no utilizar un bucle?

Todo el recorrido se puede manejar con bucles. Aun así, algunos problemas suelen resolverse más fácilmente con la recursividad que con la iteración. Un caso de uso común para la recursividad es el cruce de árboles:

Atravesar los nodes y las hojas de un árbol suele ser más fácil de pensar cuando se utiliza la recursividad. Aunque los bucles y la recursividad atraviesan el árbol, tienen diferentes propósitos: los bucles están destinados a repetir una tarea, mientras que la recursividad está destinada a dividir una tarea grande en tareas más pequeñas.

La recursividad con árboles, por ejemplo, se bifurca bien porque podemos procesar todo el árbol procesando partes más pequeñas del árbol individualmente.

Ejemplos

La mejor manera de familiarizarse con la recursividad, o con cualquier concepto de programación, es practicarlo. La creación de funciones recursivas es sencilla: asegúrese de incluir su caso base y llame a la función de manera que se acerque más al caso base.

Suma de una lista

Python incluye un sum función para listas. La implementación predeterminada de Python, CPython, usa un bucle for indefinido en C para crear esas funciones (código fuente Aquí para los interesados). Veamos cómo hacerlo con recursividad:

def sum_recursive(nums):
    if len(nums) == 0:
        return 0

    last_num = nums.pop()
    return last_num + sum_recursive(nums)

El caso base es la lista vacía, la mejor sum porque eso es 0. Una vez que manejamos nuestro caso base, eliminamos el último elemento de la lista. Finalmente llamamos al sum_recursive función con la lista reducida, y agregamos el número que sacamos al total.

En un intérprete de Python sum([10, 5, 2]) y sum_recursive([10, 5, 2]) ambos deberían darte 17.

Números factoriales

Puede recordar que un factorial de un entero positivo, es el producto de todos los enteros que lo preceden. El siguiente ejemplo lo aclararía más:

5! = 5 x 4 x 3 x 2 x 1 = 120

El signo de exclamación denota un factorial, y vemos que multiplicamos 5 por el producto de todos los enteros de 4 hasta que 1. Y si alguien entra 0? Es ampliamente entendido y probado que 0! = 1. Ahora creemos una función como la siguiente:

def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

Atendemos los casos en los que 1 o 0 se ingresa, y de lo contrario multiplicamos el número actual por el factorial del número disminuido por 1.

Una simple verificación en su intérprete de Python mostraría que factorial(5) te dio 120.

Secuencia Fibonacci

UN secuencia Fibonacci es uno donde cada número es la suma de los dos números siguientes. Esta secuencia supone que los números de Fibonacci para 0 y 1 también son 0 y 1. El equivalente de Fibonacci para 2 sería, por tanto, 1.

Veamos la secuencia y sus correspondientes números naturales:

    Integers:   0, 1, 2, 3, 4, 5, 6, 7
    Fibonacci:  0, 1, 1, 2, 3, 5, 8, 13

Podemos codificar fácilmente una función en Python para determinar el equivalente de Fibonacci para cualquier entero positivo usando la recursividad:

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

Puede verificar que funciona como se esperaba comprobando que fibonacci(6) igual a 8.

Ahora me gustaría que considerara otra implementación de esta función que usa un bucle for:

def fibonacci_iterative(n):
    if n <= 1:
        return n

    a = 0
    b = 1
    for i in range(n):
        temp = a
        a = b
        b = b + temp
    return a

Si el número entero es menor o igual a 1, devuélvelo. Ahora que nuestro caso base está manejado. Agregamos continuamente el primer número con el segundo almacenando el primer número en un temp variable antes de actualizarla.

La salida es la misma que la primera fibonacci() función. Esta versión es más rápida que la recursiva, ya que las implementaciones de Python no están optimizadas para la recursividad, pero sobresalen con la programación imperativa. Sin embargo, la solución no es tan fácil de leer como nuestro primer intento. Ahí reside una de las mayores fortalezas de la recursividad: la elegancia. Algunas soluciones de programación se resuelven de forma más natural mediante la recursividad.

Conclusión

La recursividad nos permite dividir una tarea grande en tareas más pequeñas llamándose a sí misma repetidamente. Una función recursiva requiere un caso base para detener la ejecución, y la llamada a sí misma que conduce gradualmente a la función al caso base. Se usa comúnmente en árboles, pero otras funciones se pueden escribir con recursividad para brindar soluciones elegantes.