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.

     

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *