Recursión en Python: Conceptos, ejemplos y consejos

La recursión es un concepto fundamental en programación, y tiene especial importancia en Python. Se refiere a la técnica en la que una función se llama a sí misma para resolver un problema, descomponiéndolo en subproblemas más pequeños y manejables. 

Este método permite soluciones elegantes y concisas, sobre todo cuando se trata de problemas que implican tareas repetitivas o estructuras jerárquicas. En Python, la recursividad se utiliza en una gran variedad de aplicaciones, desde la ordenación algoritmos a complejos recorridos de datos.

Las soluciones recursivas suelen reflejar las definiciones matemáticas de los problemas, lo que las hace intuitivas para quienes están familiarizados con el razonamiento matemático. La belleza de la recursividad reside en su capacidad para expresar algoritmos complejos en unas pocas líneas de código, creando soluciones elegantes y legibles. Sin embargo, dominar la recursividad requiere un cambio de mentalidad respecto a los enfoques iterativos más comunes.

En este artículo, exploraré el concepto de recursividad, cómo funciona en Python y sus aplicaciones prácticas, incluyendo un debate sobre problemas comunes y comparaciones con la iteración. Si eres nuevo en Python, considera la posibilidad de seguir uno de nuestros cursos, como por ejemplo Introducción a Python, Conceptos de Paradigmas de Programacióno Fundamentos de Programación en Python.

¿Qué es la recursión en Python?

En Python, la recursividad se refiere a una función que se llama a sí misma para resolver un problema. Implica dos componentes críticos:

• Caso base: Es la condición que pone fin a la recursividad. Sin ella, las llamadas recursivas continuarían eternamente, provocando finalmente el fallo de la función o el agotamiento de la memoria disponible.
• Caso recursivo: Esta parte de la función consiste en descomponer el problema en partes más pequeñas y volver a llamar a la función con esas partes más pequeñas.

He aquí una forma sencilla de pensar en la recursividad: imagina una función que resuelve un problema complejo resolviendo versiones más pequeñas del mismo problema, llegando finalmente a una solución que no requiere más recursividad.

El enfoque recursivo sigue la estrategia de "divide y vencerás", descomponiendo los problemas complejos en versiones más sencillas hasta llegar a un caso trivial. Este enfoque suele reflejar la forma en que pensamos de forma natural sobre la resolución de problemas. Por ejemplo, al ordenar una baraja de cartas, podríamos naturalmente ordenar grupos más pequeños y luego combinarlos, que es esencialmente como lo hacen los algoritmos de ordenación recursivos como ordenación por combinación funcionan.

Toda función recursiva debe tener al menos un caso base y al menos un caso recursivo. El caso base evita la recursividad infinita proporcionando una condición que no requiere más llamadas a funciones. El caso recursivo reduce el tamaño del problema con cada llamada, garantizando que finalmente se alcance el caso base.

¿Cómo funciona la recursión en Python?

La recursión funciona permitiendo que una función se llame a sí misma con argumentos modificados, resolviendo gradualmente el problema en pasos más pequeños. Para entenderlo más concretamente, considera la tarea de calcular la suma de números de 1 a num.

Aquí tienes un sencillo método recursivo para calcular la suma:

def sum_recursive(num):
    if num == 1:  # Base case
        return num
    return num + sum_recursive(num - 1)  # Recursive case

print(sum_recursive(3)) # 3 + 2 + 1 

6

En esta función, el caso base es cuando num == 1, que detiene la recursión. En caso contrario, la función se llama a sí misma con num - 1 hasta llegar al caso base.

Cómo funciona paso a paso:

1. sum_recursive(3) llama a sum_recursive(2).
2. sum_recursive(2) llama a sum_recursive(1).
3. sum_recursive(1) devuelve 1 (caso base).
4. Ahora, sum_recursive(2) puede devolver 2 + 1 = 3, y sum_recursive(3) puede devolver 3 + 3 = 6.

Otro ejemplo sería una función recursiva para calcular la potencia de un número:

def power(base, exponent):
    if exponent == 0:  # Base case
        return 1
    else:
        return base * power(base, exponent - 1)  # Recursive case

print(power(2, 3))

8

Explicación paso a paso de esta función de potencia:

• power(2, 3) llama a power(2, 2).
• power(2, 2) llama a power(2, 1).
• power(2, 1) llama a power(2, 0).
• power(2, 0) devuelve 1 (caso base).
• Ahora, trabajando hacia atrás: power(2, 1) devuelve 2 * 1 = 2.
• Entonces power(2, 2) devuelve 2 * 2 = 4.
• Por último, power(2, 3) devuelve 2 * 4 = 8.

Cuando se llama a una función recursiva, cada llamada recursiva crea una nueva entrada en la pila de llamadas. Esta pila lleva la cuenta de todas las llamadas a funciones y sus variables. Cuando se alcanza el caso base, la pila empieza a resolver cada llamada en orden inverso, calculando el resultado final paso a paso.

Comprender este comportamiento de la pila es crucial porque explica tanto la potencia como las limitaciones de la recursividad en Python. Conserva elegantemente el contexto, pero también puede provocar problemas de memoria con la recursividad profunda.

Implementación del Factorial en Python mediante Recursión

La función factorial es un ejemplo clásico utilizado para demostrar la recursividad. El factorial de un número n, denotado n!, es el producto de todos los enteros positivos menores o iguales que n. Matemáticamente:

n! = n × (n − 1) × (n − 2) × … × 1

Recursivamente, la función factorial puede definirse como:

n! = n × (n − 1)!

Vamos a implementarlo en Python:

def compute_factorial(num):
    if num == 0:  # Base case
        return 1
    return num * compute_factorial(num - 1)  # Recursive case

print(compute_factorial(4)) # 4 * 3 * 2 * 1

24

Explicación paso a paso del código:

• La función compute_factorial(num) comprueba si num == 0 y devuelve 1 en ese caso.
• En caso contrario, devuelve num * compute_factorial(num - 1), donde la función se llama a sí misma con un valor menor de num.

La función factorial ilustra perfectamente la elegancia de la recursividad. La propia definición matemática es recursiva, lo que hace que la implementación del código sea intuitiva y esté estrechamente alineada con el concepto matemático. Éste es uno de los puntos fuertes de la recursividad: permite que el código exprese directamente definiciones matemáticas.

Hay que tener en cuenta que existen casos extremos. Por ejemplo, el factorial sólo suele definirse para números enteros no negativos. Una implementación sólida podría incluir el tratamiento de errores para entradas negativas o la comprobación de tipos. 

Además, para valores grandes de num, la solución recursiva puede provocar un desbordamiento de pila, limitación que trataré con más detalle.

Problemas comunes: Cómo corregir errores de recursión en Python

Aunque la recursividad puede ser una herramienta poderosa, es propensa a algunos problemas comunes, como:

Superar la profundidad máxima de recursión

Python tiene un límite de recursión por defecto de 1000 llamadas. Si una función recursiva se llama a sí misma demasiadas veces, aparecerá RecursionError.

He aquí cómo solucionarlo:

Puedes aumentar la profundidad de la recursión utilizando sys.setrecursionlimit(). Sin embargo, esto no se recomienda a menos que sea necesario, ya que puede provocar un desbordamiento de pila.

import sys  

# Get the current recursion limit
current_limit = sys.getrecursionlimit()
print(f'Current limit: {current_limit}')  

# Set a new recursion limit to 200
new_limit = 200
sys.setrecursionlimit(new_limit)  

# Get the new recursion limit
changed_current_limit = sys.getrecursionlimit()
print(f'Current limit after change: {changed_current_limit}')  

Current limit: 1000
Current limit after change: 200

Falta el caso base

Un caso base omitido o incorrecto hará que la función recurra infinitamente, provocando un desbordamiento de pila.

Para solucionarlo, asegúrate de que tu caso base está bien definido y es alcanzable.

Cómo detener la recursión en Python

La clave para detener la recursividad en Python es definir un caso base adecuado. Sin ella, la recursión nunca terminará y dará lugar a un error.

Por ejemplo, en la función factorial que implementé antes, el caso base era if num == 0, que detiene la recursión. En general, debes asegurarte de que toda función recursiva tiene una condición bajo la cual termina.

Diseñar casos base eficaces requiere una reflexión cuidadosa. Algunas directrices son:

• Identifica la versión más sencilla del problema que pueda resolverse directamente.
• Asegúrate de que todos los caminos recursivos lleguen finalmente a un caso base.
• Prueba los casos de borde por separado para verificar que se gestionan correctamente.
• Considera múltiples casos base si el problema lo requiere.

A veces, las técnicas de programación defensiva son útiles, añadiendo guardias contra entradas no válidas o comprobaciones en tiempo de ejecución para evitar una profundidad de recursión excesiva. Por ejemplo:

def safe_factorial(num, depth=0, max_depth=100):
    # Check if recursion is too deep
    if depth > max_depth:
        raise ValueError("Maximum recursion depth exceeded")
   
    # Base case
    if num <= 0:
        return 1
   
    # Recursive case with depth tracking
    return num * safe_factorial(num - 1, depth + 1, max_depth)

# Calculate factorial of 5 with default depth limits
result = safe_factorial(5)

print(result) 

120

# Calculate factorial of 5 with depth > max_depth
result = safe_factorial(5, depth=20, max_depth=10)

print(result) 

ValueError: Maximum recursion depth exceeded

Este enfoque te permite establecer límites personalizados y proporcionar mensajes de error más significativos que los predeterminados RecursionError.

He aquí otro ejemplo que demuestra una forma diferente de definir los casos base: encontrar el máximo común divisor (MCD) de dos números utilizando la recursividad.

El DGC de dos números x y y puede calcularse mediante el algoritmo de Euclides, con el operador operador módulo %:

• Caso base: Si y == 0, el GCD es x.
• Caso recursivo: En caso contrario, el GCD de x y y es igual al GCD de y y x % y.

def find_gcd(x, y):
    # Base case: if y is 0, the GCD is x
    if y == 0:
        return x
    # Recursive case: GCD of y and x % y
    return find_gcd(y, x % y)

print(find_gcd(48, 18))  

6

Recursión vs. Iteración en Python

Tanto la recursividad como la iteración pueden resolver muchos de los mismos problemas, pero cada una tiene sus pros y sus contras:

• La recursividad suele ser más elegante y fácil de entender, sobre todo en problemas que tienen una estructura recursiva natural (p. ej, recorridos en árbolfactoriales, números de Fibonacci).
• La iteración puede ser más eficaz porque no implica la sobrecarga de múltiples llamadas a funciones y puede evitar problemas relacionados con el desbordamiento de la pila. Las soluciones iterativas suelen ser más eficientes en memoria.

Cuándo utilizar la recursividad:

• Cuando el problema puede dividirse de forma natural en subproblemas más pequeños.
• Para problemas relacionados con estructuras de datos jerárquicas, como los árboles.
• Cuando la solución en forma recursiva es más intuitiva y conduce a un código más limpio.
• Cuando se prioriza la legibilidad del código sobre la optimización del rendimiento.
• Al trabajar con datos de profundidad desconocida (como analizar JSON o XML anidados).

Cuándo utilizar la iteración:

• Para problemas que requieren tareas repetitivas sin dividir el problema en subproblemas más pequeños.
• Para tareas de rendimiento crítico, en las que una recursión profunda podría provocar un uso elevado de memoria.
• Cuando trabajes con grandes conjuntos de datos que puedan superar el límite de recursión.
• Cuando el uso de memoria es una preocupación primordial.
• Para los problemas que son naturalmente secuenciales y no jerárquicos.

Comparemos las implementaciones recursiva e iterativa del mismo problema, calculando la suma de números de 1 a num:

Recursivo:

def sum_recursive(num):
    if num == 1:
        return 1
    else:
        return num + sum_recursive(num - 1)

Iterativo:

def iterative_sum(num):
    total = 0
    for i in range(1, num + 1):
        total += i
    return total

La versión iterativa utiliza un bucle para acumular la suma, mientras que la versión recursiva descompone el problema en sumar n a la suma de números de 1 a num - 1. Aunque ambas soluciones funcionan, la versión iterativa será más eficaz para valores grandes de num, ya que no implica la sobrecarga de múltiples llamadas a funciones.

Algunos problemas que son naturalmente recursivos pueden transformarse en soluciones iterativas utilizando una pila o cola para simular las llamadas recursivas. Esta técnica es especialmente útil cuando se trata de recorrer árboles o grafos.

Ejemplos prácticos de recursión en Python

La recursión puede aplicarse a diversos problemas interesantes:

1. Calcular los números de Fibonacci

La sucesión de Fibonacci se define recursivamente como:

• F(0) = 0
• F(1) = 1
• F(n) = F(n − 1) + F(n − 2)

Esto proporcionará la siguiente secuencia:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...

He aquí cómo podrías ponerlo en práctica:

def compute_fibonacci(num):
    if num <= 0:
        return 0
    elif num == 1:
        return 1
    return compute_fibonacci(num - 1) + compute_fibonacci(num - 2)

print(compute_fibonacci(6))

8

Sin embargo, esta implementación ingenua recalcula los valores varias veces. Un enfoque más eficiente utiliza la memoización, que almacena los resultados calculados previamente (caché) para evitar cálculos redundantes, y reducir significativamente el tiempo de cálculo:

def optimized_fibonacci(num, cache=None):
    if cache is None:
        cache = {}
    if num in cache:
        return cache[num]
    if num <= 1:
        return num
    cache[num] = optimized_fibonacci(num - 1, cache) + optimized_fibonacci(num - 2, cache)
    return cache[num]

Esto puede simplificarse aún más utilizando el decorador lru_cache() del módulo functools:

from functools import lru_cache

@lru_cache(maxsize=None)  # Cache all computed values
def cached_fibonacci(num):
    if num <= 1:
        return num
    return cached_fibonacci(num - 1) + cached_fibonacci(num - 2)

2. Recorrer estructuras de datos anidadas

La recursión también es útil para trabajar con estructuras de datos anidadas, como listas de listas u objetos JSON. Por ejemplo, recorrer una estructura de árbol de directorios o aplanar recursivamente una lista anidada.

def flatten(nested):
    result = []
    for element in nested:
        if isinstance(element, list):
            result.extend(flatten(element))
        else:
            result.append(element)
    return result

nested_structure = [1, [2, 3], [4, [5, 6]]]

print(flatten(nested_structure))  

[1, 2, 3, 4, 5, 6]

3. Algoritmos de ordenación (por ejemplo, ordenación rápida u ordenación por fusión) 

Algoritmos de ordenación como la ordenación rápida y ordenación por fusión se basan en gran medida en la recursividad. En estos algoritmos, el problema se descompone en subproblemas más pequeños, que se ordenan recursivamente.

Aquí tienes una aplicación sencilla de la ordenación rápida:

def quicksort_algo(array):
    if len(array) <= 1:
        return array
    pivot = array[len(array) // 2]
    lower = [item for item in array if item < pivot]
    equal = [item for item in array if item == pivot]
    greater = [item for item in array if item > pivot]
    return quicksort_algo(lower) + equal + quicksort_algo(greater)

array = [220, 33, 400, 150, 16]

print(quicksort_algo(array))

[16, 33, 150, 220, 400]

Conclusión

La recursión es un potente concepto de Python que ayuda a resolver problemas complejos descomponiéndolos en subproblemas más sencillos. Cuando se utiliza correctamente, la recursividad da lugar a un código limpio, conciso y fácil de entender. 

Sin embargo, es esencial definir casos base adecuados y tener en cuenta la profundidad de la recursividad para evitar errores comunes. 

Aunque a veces la recursividad puede ser menos eficaz que la iteración, es una herramienta inestimable para resolver ciertos tipos de problemas, sobre todo los que implican datos jerárquicos o problemas que se prestan naturalmente a soluciones recursivas.

Comprendiendo la recursividad y practicando con ejemplos como factoriales, secuencias de Fibonacci y algoritmos de ordenación, estarás bien equipado para aprovechar la recursividad en tus proyectos de Python.

Si estás interesado en temas más avanzados de Python en los que podrías implementar la recursividad, consulta las siguientes rutas de aprendizaje: Programación en Python, Analista de Datos en Pythony Científico de Datos Asociado en Python