Recursión en

Acerca de Recursión

La recursión es una forma de ejecutar código repetidamente dentro de una función, haciendo que la función se llame a sí misma. Las funciones que se llaman a sí mismas se conocen como funciones recursivas. La recursión puede verse como otra forma de hacer bucles o iterar. Y, al igual que con los bucles, se usa una expresión Boolean o una prueba True/False para determinar cuándo detener la ejecución recursiva.

A diferencia de los bucles, la recursión sin terminación en Python no puede ejecutarse infinitamente. Los valores que se usan en cada llamada a la función se colocan en su propio marco en la pila del intérprete de Python. Si el número total de llamadas a la función ocupa más espacio del que tiene la pila, se producirá un error.

Bucle vs. implementación recursiva

Los bucles y la recursión pueden parecer similares, ya que ambos son iterativos. Sin embargo, se ven diferentes, tanto a nivel del código como a nivel de la implementación. Un bucle puede ocurrir dentro del mismo marco en la pila de llamadas. Por lo general, esto se maneja actualizando uno o más valores de variables para mantener progresivamente el estado de cada iteración. Esta es una implementación eficiente, pero puede resultar algo desordenada cuando se mira el código.

La recursión, en lugar de actualizar el estado de las variables, puede pasar valores actualizados directamente como argumentos a la siguiente llamada (iteración) de la misma función. Esto despeja el cuerpo de la función y puede aclarar cómo ocurre cada actualización. Sin embargo, también es una implementación menos eficiente, ya que cada llamada a la misma función agrega otro marco a la pila.

Recursión: ¿por qué sí y por qué no?

Si existe el riesgo de provocar un error de pila o un desbordamiento, ¿por qué alguien usaría una estrategia recursiva para resolver un problema? Legibilidad, trazabilidad e intención. Puede haber situaciones en las que una solución sea más legible o más fácil de razonar cuando se expresa mediante recursión que cuando se expresa mediante bucles. También puede haber restricciones del programa relacionadas con usar o modificar datos, gestionar la complejidad, delegar responsabilidad u organizar cargas de trabajo.

Los problemas que se prestan a la recursión incluyen problemas complejos pero repetitivos que se hacen más pequeños con el tiempo, en particular los algoritmos de divide y vencerás y los algoritmos acumulativos. Sin embargo, debido al límite de Python para cuántos marcos se permiten en la pila, no todos los problemas se beneficiarán de una estrategia totalmente recursiva. Los problemas menos aptos para la recursión incluyen los que tienen un estado estable pero necesitan repetirse durante cierto número de ciclos, los problemas que necesitan ejecutarse de forma asíncrona, y las situaciones que exigen un gran número de iteraciones.

Bucle vs. estrategia recursiva: la inseguridad de Indira

Indira recibe el depósito automático de su seguro social mensual en su cuenta bancaria el segundo miércoles de cada mes. A Indira le preocupa cuadrar su chequera. Teme girar cheques antes de que se deposite su dinero. Le pide a su nieta Adya que le dé una lista de las fechas en que su dinero aparecerá en su cuenta.

Adya, que apenas está aprendiendo a programar en Python, escribe un programa basado en sus primeras ideas. Quiere devolver una list de las fechas de depósito para que se puedan imprimir. Quiere escribir una función que sirva para cualquier año. En caso de que el calendario cambie (o de que otros familiares quieran que Adya calcule sus calendarios de depósito), decide que la función necesita un parámetro adicional para el día de la semana. Por último, Adya decide que la función necesita un parámetro para cuál día de la semana del mes es: el primero, el segundo, etc. Para todos estos requisitos, decide usar la clase date importada de datetime. Reuniendo todo eso, a Adya se le ocurre:

from datetime import date


def paydates_for_year(year, weekday, ordinal):
    """Returns a list of the matching weekday dates.
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    output = []

    for month in range(1, 13):
        for day_num in range(1, 8):
            if date(year, month, day_num).isoweekday() == weekday:
                output.append(date(year, month, day_num + (ordinal - 1) * 7))
                break
    return output

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year(2022, 3, 2))

Esta primera iteración funciona, pero Adya se pregunta si puede refactorizar el código para usar menos líneas y menos bucles anidados. También ha leído que es bueno minimizar la modificación del estado, así que le gustaría ver si puede evitar modificar algunas de sus variables, como output, month y day_num.

También sabe de recursión, y piensa en cómo podría cambiar su programa para usar un enfoque recursivo. Las variables que se crean y se modifican en su función con bucle podrían pasarse como argumentos en su lugar. En lugar de modificar las variables dentro de su función, podría pasar valores actualizados como argumentos a la siguiente llamada a la función. Con esas intenciones, llega a este enfoque recursivo:

from datetime import date


def paydates_for_year_rec(year, weekday, ordinal, month, day_num, output):
    """Returns a list of the matching weekday dates
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
        month (int): The month number currently being processed.
        day_num (int): The day number of the month currently being processed.
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    if month == 13:
        return output
        
    if date(year, month, day_num).isoweekday() == weekday:
        return paydates_for_year_rec(
                 year, weekday, ordinal, month + 1, 1, output
                 + [date(year, month, day_num + (ordinal - 1) * 7)]
                 )
    
    return paydates_for_year_rec(year, weekday, ordinal, month, day_num + 1, output)

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year_rec(2022, 3, 2, 1, 1, []))

¡Adya está contenta de que ya no haya bucles anidados, ni estado modificado, y 2 líneas de código menos!

Le preocupa un poco que el enfoque recursivo use más pasos que el enfoque con bucle y, por lo tanto, sea menos «performant». Pero reescribir el problema usando recursión definitivamente la ayudó a lidiar con los feos bucles anidados (un riesgo para el rendimiento), la extensa modificación del estado y la confusión en torno a la lógica condicional compleja. También se siente «más legible»: está segura de que, cuando vuelva a este código después de un descanso, podrá leerlo y recordar más fácilmente qué hace.

En el futuro, es posible que Adya intente resolver los problemas primero de forma recursiva. Puede que le resulte más fácil recorrer el problema inicialmente en pasos claros cuando la anidación, la modificación y la complejidad se reducen al mínimo. Después de resolver la lógica básica, puede centrarse en optimizar sus pasos recursivos iniciales hacia un enfoque con bucles más eficiente.

Incluso más adelante, cuando aprenda sobre tuples, Adya podría considerar enfoques para «optimizar» aún más, como usar una list comprehension con Calendar.itermonthdates, o memoizar ciertos valores.

Variante recursiva: la llamada de cola

Una llamada de cola ocurre cuando la última sentencia de una función solo se llama a sí misma y nada más. Este ejemplo no es una llamada de cola, ya que la función suma 1 al resultado de llamarse a sí misma:

def print_increment(step, max_value):
    if step > max_value:
        return 1
    print(f'The step is {step}')
    return 1 + print_increment(step + 1, max_value)


def main():
    retval = print_increment(1, 2)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

Esto imprimirá:

The step is 1
The step is 2
retval is 3 after recursion

Para refactorizarlo a una llamada de cola, haz que retval sea un parámetro de print_increment.

def print_increment(step, max_value, retval):
    if step > max_value:
        return retval
    print(f'The step is {step}')
    return print_increment(step + 1, max_value, retval + 1)


def main():
    retval = print_increment(1, 2, 1)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

Puede que una llamada de cola te resulte incluso más fácil de razonar que una llamada recursiva que no es una llamada de cola. Sin embargo, al usar recursión siempre es importante saber que no habrá tantas iteraciones como para que la pila se desborde.

Límites de recursión en Python

Algunos lenguajes pueden optimizar las llamadas de cola para que cada llamada recursiva reutilice el marco de pila de la primera llamada a la función (de forma similar a como un bucle reutiliza un marco), en lugar de agregar un marco adicional a la pila. Python no es uno de esos lenguajes. Para protegerse contra el desbordamiento de la pila, Python tiene un límite de recursión que por defecto es de mil marcos. Se genera una excepción RecursionError cuando el intérprete detecta que se ha superado el límite de recursión. Es posible usar el método sys.setrecursionlimit para aumentar el límite de recursión, pero hacerlo conlleva el riesgo de sufrir un fallo de segmentación en tiempo de ejecución que hará fallar el programa y, posiblemente, el sistema operativo.

Recursos

Para aprender más sobre cómo usar la recursión en Python, puedes empezar con

• python-programming: recursion
• Real Python: python-recursion
• Real Python: python-thinking-recursively