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 de iterar. Y, al igual que con los bucles, se usa una expresión booleana o una comprobación True/False para determinar cuándo detener la ejecución recursiva.

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

Bucles frente a implementación recursiva

Puede que los bucles y la recursión parezcan similares, ya que ambos son iterativos. Sin embargo, se ven diferentes, tanto a nivel de código como a nivel de implementación. Los bucles pueden tener lugar dentro del mismo marco de la pila de llamadas. Normalmente, esto se gestiona actualizando uno o varios valores de variables para mantener progresivamente el estado en cada iteración. Es una implementación eficiente, pero puede resultar algo recargada cuando se mira el código.

La recursión, en lugar de actualizar el estado de las variables, puede pasar los 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 se produce cada actualización. Sin embargo, también es una implementación menos eficiente, ya que cada llamada a la misma función añade 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é iba alguien a usar 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 en cuanto al uso o la mutación de datos, la gestión de la complejidad, la delegación de responsabilidades o la organización de la carga de trabajo.

Entre los problemas que se prestan a la recursión están los problemas complejos pero repetitivos que se van reduciendo con el tiempo, en particular los algoritmos de divide y vencerás y los algoritmos acumulativos. Sin embargo, debido al límite de Python sobre cuántos marcos se permiten en la pila, no todos los problemas se beneficiarán de una estrategia totalmente recursiva. Entre los problemas menos adecuados de forma natural para la recursión están los que tienen un estado estable pero necesitan repetirse durante un número determinado de ciclos, los que deben ejecutarse de forma asíncrona y las situaciones que requieren un gran número de iteraciones.

Bucles frente a estrategia recursiva: la inseguridad de Indira

Indira recibe automáticamente el ingreso mensual de su seguridad social en su cuenta bancaria el segundo miércoles de cada mes. A Indira le preocupa cuadrar su talonario de cheques. Teme escribir cheques antes de que se le deposite el dinero. Le pide a su nieta Adya que le dé una lista de las fechas en las que el dinero aparecerá en su cuenta.

Adya, que acaba de empezar a aprender a programar en Python, escribe un programa a partir de sus primeras ideas. Quiere devolver una list con las fechas de los depósitos para poder imprimirlas. Quiere escribir una función que sirva para cualquier año. Por si cambia el calendario (o por si otros familiares quieren 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 indicar qué día de la semana del mes es: el primero, el segundo, etc. Con todos estos requisitos, decide usar la clase date importada de datetime. Reuniendo todo esto, a Adya se le ocurre lo siguiente:

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 mutación del estado, así que le gustaría ver si puede evitar mutar algunas de sus variables, como output, month y day_num.

También conoce la recursión y piensa en cómo podría cambiar su programa para usar un enfoque recursivo. Las variables que se crean y se mutan en su función con bucles podrían pasarse en su lugar como argumentos. En lugar de mutar las variables dentro de su función, podría pasar valores actualizados como argumentos a la siguiente llamada a la función. Con estas 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 mutado, ¡y 2 líneas de código menos!

Le preocupa un poco que el enfoque recursivo use más pasos que el de bucles y, por tanto, sea menos «eficiente». Pero reescribir el problema usando recursión la ha ayudado sin duda a lidiar con bucles anidados feos (un riesgo para el rendimiento), con mucha mutación de estado y con la confusión en torno a una lógica condicional compleja. También le parece más «legible»: está segura de que, cuando vuelva a este código tras un descanso, podrá leerlo y recordar con más facilidad qué hace.

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

Más adelante, cuando aprenda sobre tuples, Adya podría considerar otros enfoques de «optimización», como usar una list comprehension con Calendar.itermonthdates, o memoizar ciertos valores.

Variante recursiva: la llamada de cola

Una llamada de cola se produce cuando la última instrucción de una función se limita a llamarse 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 como 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 sea 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 son capaces de optimizar las llamadas de cola de modo que cada llamada recursiva reutiliza 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 añadir otro marco a la pila. Python no es uno de esos lenguajes. Para protegerse de un desbordamiento de pila, Python tiene un límite de recursión que por defecto es de mil marcos. Se lanza 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 bloqueará el programa y posiblemente el sistema operativo.

Recursos

Para aprender más sobre el uso de la recursión en Python, puedes empezar por

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