Dominando la recursión en Python: Cómo las funciones se llaman a sí mismas

Dominando la recursión en Python

Descubra cómo las funciones de Python pueden llamarse a sí mismas, la mecánica de la recursión y mejores prácticas para escribir código recursivo seguro y eficiente.

¿Qué es la recursión?

La recursión es la técnica de definir un problema en términos de una instancia menor del mismo problema.

Una ilustración clásica involucra dos espejos paralelos enfrentados; cada imagen es un reflejo recursivo del otro.

Función recursiva en Python

En Python, una función puede invocar otras funciones, e incluso invocarse a sí misma. Tales constructos se llaman funciones recursivas.

La imagen siguiente demuestra la pila de llamadas para una función recursiva simple llamada recurse:

A continuación se muestra un ejemplo clásico: una implementación recursiva de la función factorial, que devuelve el producto de todos los enteros positivos hasta x.

Ejemplo de función recursiva

def factorial(x):
    """Calcula recursivamente el factorial de un entero positivo."""
    if x == 1:
        return 1
    return x * factorial(x - 1)
num = 3
print("El factorial de", num, "es", factorial(num))

Salida

El factorial de 3 es 6

Aquí, factorial() es una función recursiva porque se llama a sí misma hasta alcanzar el caso base x == 1.

Cuando se invoca con un entero positivo, la función se llama repetidamente con un valor decrementado:

factorial(3) # 1ra llamada con 3
3 * factorial(2) # 2da llamada con 2
3 * 2 * factorial(1) # 3ra llamada con 1
3 * 2 * 1 # retorno de 3ra llamada
3 * 2 # retorno de 2da llamada
6 # retorno de 1ra llamada

A continuación se muestra una representación visual de este proceso paso a paso:

La recursión termina cuando el valor de entrada alcanza la condición base (en este caso, x == 1). Toda función recursiva debe incluir tal criterio de parada; de lo contrario, continuaría indefinidamente y eventualmente agotaría la pila de llamadas.

Python impone una profundidad máxima de recursión (por defecto 1000) para prevenir que la recursión infinita bloquee el intérprete. Exceder este límite lanza RecursionError:

def recursora():
    recursora()
recursora()

Salida

Traceback (most recent call last):
File "<string>", line 3, in <module>
File "<string>", line 2, in a
File "<string>", line 2, in a
File "<string>", line 2, in a
[Línea anterior repetida 996 veces más]
RecursionError: maximum recursion depth exceeded

Puede ajustar el límite de recursión programáticamente usando sys.setrecursionlimit(), pero hágalo con precaución para evitar desbordamiento de pila.

Ventajas de la recursión

1. Las soluciones recursivas son a menudo más concisas y fáciles de leer, especialmente para problemas expresados naturalmente en términos recursivos.
2. Permiten descomposición elegante de tareas complejas en sub-problemas más simples.
3. La generación de secuencias (ej. Fibonacci, permutaciones) es directa con recursión comparado a bucles anidados.

Desventajas de la recursión

1. La lógica recursiva puede ser más difícil de seguir y razonar para principiantes.
2. Cada llamada recursiva consume espacio en pila; recursiones profundas pueden ser intensivas en memoria y más lentas que alternativas iterativas.
3. Depurar recursión puede ser desafiante debido a la pila de llamadas en capas.

En la práctica, elija recursión cuando lleve a código más claro y mantenible y cuando el tamaño de entrada sea moderado. Para entradas muy grandes, enfoques iterativos u optimizaciones de recursión de cola (cuando se soporten) pueden ser preferibles.