La recursión es un concepto fundamental en la programación y las ciencias de la computación. En Python, la recursión se utiliza para resolver problemas dividiéndolos en subproblemas más pequeños del mismo tipo. En este artículo, exploraremos en profundidad el concepto de recursión en Python 3, desde su definición hasta su implementación y optimización.

1. ¿Qué es la Recursión?

La recursión es una técnica de programación en la que una función se llama a sí misma para resolver un problema. Cada llamada a la función recursiva reduce el problema a una versión más simple del mismo hasta que se alcanza una condición base que detiene la recursión.

Ejemplo básico de recursión:

 def cuenta_regresiva(n):
     if n <= 0:  # Condición base
         print("Fin de la cuenta regresiva")
     else:
         print(n)
         cuenta_regresiva(n - 1)  # Llamada recursiva

 cuenta_regresiva(5)

2. Factores Clave de la Recursión

a) Condición Base

Cada función recursiva debe tener una condición base para evitar llamadas infinitas.

b) Llamada Recursiva

La función debe llamarse a sí misma con un argumento modificado, acercándose a la condición base.

c) Pila de Llamadas

Python usa una pila para gestionar las llamadas recursivas. Cada llamada se almacena en la pila hasta que se alcanza la condición base y la ejecución comienza a resolverse en orden inverso.

3. Ejemplos Clásicos de Recursión

a) Factorial de un Número

def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))  # Salida: 120

b) Fibonacci Recursivo

def fibonacci(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(6))  # Salida: 8

4. Optimización de Recursión

Las funciones recursivas pueden volverse ineficientes debido a la repetición de cálculos. Algunas estrategias para optimizar incluyen:

a) Memorización (Memoization)

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_memo(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    return fibonacci_memo(n - 1) + fibonacci_memo(n - 2)

print(fibonacci_memo(6))

b) Recursión de Cola

Python no optimiza la recursión de cola de forma nativa, pero se puede reescribir una función para evitar profundidades innecesarias:

def factorial_tail(n, acum=1):
    if n == 0:
        return acum
    return factorial_tail(n - 1, acum * n)

print(factorial_tail(5))

c) Conversión a Iteración

En algunos casos, las funciones recursivas pueden reformularse como iteraciones para mejorar el rendimiento.

def factorial_iterativo(n):
    resultado = 1
    for i in range(2, n + 1):
        resultado *= i
    return resultado

print(factorial_iterativo(5))

5. Aplicaciones de la Recursión

a) Búsqueda Binaria

def busqueda_binaria(lista, objetivo, izquierda, derecha):
    if izquierda > derecha:
        return -1
    medio = (izquierda + derecha) // 2
    if lista[medio] == objetivo:
        return medio
    elif lista[medio] < objetivo:
        return busqueda_binaria(lista, objetivo, medio + 1, derecha)
    else:
        return busqueda_binaria(lista, objetivo, izquierda, medio - 1)

lista = [1, 3, 5, 7, 9, 11]
print(busqueda_binaria(lista, 7, 0, len(lista) - 1))  # Salida: 3

b) Torres de Hanoi

def hanoi(n, origen, destino, auxiliar):
    if n == 1:
        print(f"Mover disco de {origen} a {destino}")
        return
    hanoi(n - 1, origen, auxiliar, destino)
    print(f"Mover disco de {origen} a {destino}")
    hanoi(n - 1, auxiliar, destino, origen)

hanoi(3, 'A', 'C', 'B')

Conclusión

La recursión es una poderosa herramienta en Python 3 que permite resolver problemas dividiéndolos en subproblemas más pequeños. Sin embargo, su uso debe ser controlado para evitar problemas de rendimiento y desbordamiento de pila. Optimizar la recursión con técnicas como la memorización y la conversión a iteración es clave para mejorar la eficiencia de los algoritmos. Al dominar la recursión, los programadores pueden abordar una amplia variedad de problemas de manera efectiva.

Recursión en Python 3: Un Enfoque Detallado