Una función recursiva es aquella que se invoca a sí misma durante su ejecución. Este concepto es fundamental en programación para resolver problemas que pueden descomponerse en subproblemas similares. En sistemas operativos, por ejemplo, se utiliza para recorrer directorios o gestionar permisos de archivos de manera jerárquica.

Para garantizar un comportamiento correcto, las funciones recursivas deben cumplir con ciertas características:

• Incluir un caso base o condición de terminación clara.
• Reducir progresivamente la complejidad del problema en cada invocación.

Sin embargo, la recursión puede generar ineficiencias, como el desbordamiento de pila, ya que cada llamada crea un marco en la pila de ejecución. Si las capas de recursión son demasiado profundas, se agota la memoria asignada.

A continuación, se muestra un ejemplo de cálculo factorial mediante recursión:

def calcular_factorial(numero):
    if numero == 1:
        return 1
    else:
        return numero * calcular_factorial(numero - 1)

# Ejemplo de uso
resultado1 = calcular_factorial(5)
resultado2 = calcular_factorial(6)
print(resultado1)  # Salida: 120
print(resultado2)  # Salida: 720

Para ilustrra el proceso, el factorial de 5 se desglosa así:

calcular_factorial(5)                        # Primera invocación
5 * calcular_factorial(4)                    # Segunda invocación
5 * (4 * calcular_factorial(3))              # Tercera invocación
5 * (4 * (3 * calcular_factorial(2)))        # Cuarta invocación
5 * (4 * (3 * (2 * calcular_factorial(1))))  # Quinta invocación (caso base)
5 * (4 * (3 * (2 * 1)))                     # Retorno desde la quinta invocación
5 * (4 * (3 * 2))                           # Retorno desde la cuarta invocación
5 * (4 * 6)                                 # Retorno desde la tercera invocación
5 * 24                                      # Retorno desde la segunda invocación
120                                         # Retorno final

La recursión se detiene cuando el valor llega a 1.

La ventaja principal de la recursión es la claridad lógica, ya que permite expresar soluciones de forma concisa. No obstante, presenta desventajas como la dificultad para depurar y el alto consumo de recursos, lo que puede afectar el rendimiento.

Otro ejemplo clásico es la sucesión de Fibonacci:

def generar_fibonacci(valor1, valor2):
    if valor1 == 0:
        print(valor1, valor2)
    valor_siguiente = valor1 + valor2
    print(valor_siguiente)
    generar_fibonacci(valor2, valor_siguiente)

# Iniciar la secuencia
generar_fibonacci(0, 1)

Este código produce la serie de Fibonacci imprimiendo cada término. Es crucial recordar que la profundidad excesiva puede causar un desbordamiento de pila.

Para mitigar este problema, existe la optimización de cola recursiva, donde la llamada recursiva es la última operación en la función. Por ejemplo, se puede reescribir la función factorial:

def factorial_optimizado(n):
    return calcular_factorial_iterativo(n, 1)

def calcular_factorial_iterativo(num, acumulado):
    if num == 1:
        return acumulado
    return calcular_factorial_iterativo(num - 1, num * acumulado)

# Ejemplo
print(factorial_optimizado(5))  # Salida: 120

En esta versión, la llamada recursiva se realiza con todos los cálculos previos completados, lo que teóricamente permite la optimización de pila. Sin embargo, en Python, el intérprete no implementa esta optimización, por lo que el riesgo de desbordamiento persiste.

Python establece un límite máximo de recursión, generalmente alrededor de 1000 capas, para prevenir el agotamiento de memoria. Este valor puede ajustarse mediante el módulo sys:

import sys
sys.setrecursionlimit(1500)  # Ajustar el límite a 1500

No se recomienda modificar este valor a menos que sea estrictamente necesario, ya que depende de la capacidad del sistema.

Un caso práctico de recursión es la navegación por un menú jerárquico. Considérese una estructura de datos anidada que representa ubicaciones geográficas:

estructura_menu = {
    'Madrid': {
        'Centro': {
            'Sol': {'Tienda': {}},
            'Gran Via': {'Cine': {}}
        },
        'Norte': {'Chamartin': {}}
    },
    'Barcelona': {
        'Eixample': {'Sagrada Familia': {}}
    }
}

def explorar_menu(datos, pila_niveles=None):
    if pila_niveles is None:
        pila_niveles = [datos]
    while pila_niveles:
        nivel_actual = pila_niveles[-1]
        for clave in nivel_actual:
            print(clave)
        entrada = input("Seleccione una opción (o 's' para salir): ").strip()
        if entrada == 's':
            break
        elif entrada in nivel_actual and nivel_actual[entrada]:
            pila_niveles.append(nivel_actual[entrada])
        elif entrada == 'r':
            pila_niveles.pop()

explorar_menu(estructura_menu)

Este código permite navegar por los niveles del menú utilizando una pila para rastrear la posición actual, emulando un enfoque recursivo con control iterativo. Se puede adaptar para usar recursión directa, pero se debe manejar cuidadosamente la profundidad.