Recursión en Python: Funciones Recursivas con Ejemplos Prácticos

La recursión es una técnica de programación donde una función se llama a sí misma para resolver un problema dividiéndolo en subproblemas más pequeños. En esta guía completa aprenderás todo sobre funciones recursivas en Python, desde conceptos básicos hasta patrones avanzados.

¿Qué es la Recursión en Python?

La recursión es un método de resolución de problemas donde la solución depende de soluciones a instancias más pequeñas del mismo problema.

def cuenta_regresiva(n):
    """Función recursiva simple"""
    if n <= 0:  # Caso base
        print("¡Despegue!")
    else:  # Caso recursivo
        print(n)
        cuenta_regresiva(n - 1)  # Llamada recursiva

cuenta_regresiva(5)
# Output:
# 5
# 4
# 3
# 2
# 1
# ¡Despegue!

Componentes esenciales de la recursión:

1. Caso base: Condición que detiene la recursión
2. Caso recursivo: Llamada a la función misma con argumentos modificados
3. Progreso hacia el caso base: Cada llamada debe acercarse al caso base

Anatomía de una Función Recursiva

Toda función recursiva debe tener una estructura clara:

def funcion_recursiva(parametros):
    # 1. Caso base (condición de parada)
    if condicion_base:
        return valor_base

    # 2. Caso recursivo
    # Procesamiento
    resultado = funcion_recursiva(parametros_modificados)

    # 3. Retorno del resultado
    return resultado

Ejemplo: Factorial

El factorial de un número (n!) es un caso clásico de recursión:

def factorial(n):
    """Calcula el factorial de n de forma recursiva"""
    # Caso base
    if n == 0 or n == 1:
        return 1

    # Caso recursivo: n! = n * (n-1)!
    return n * factorial(n - 1)

# Ejemplos
print(factorial(5))  # Output: 120 (5*4*3*2*1)
print(factorial(3))  # Output: 6 (3*2*1)
print(factorial(0))  # Output: 1

¿Cómo funciona internamente?

factorial(5)
  = 5 * factorial(4)
  = 5 * (4 * factorial(3))
  = 5 * (4 * (3 * factorial(2)))
  = 5 * (4 * (3 * (2 * factorial(1))))
  = 5 * (4 * (3 * (2 * 1)))
  = 120

Ejemplos Clásicos de Recursión

1. Secuencia de Fibonacci

Cada número es la suma de los dos anteriores:

def fibonacci(n):
    """Retorna el n-ésimo número de Fibonacci"""
    # Casos base
    if n <= 0:
        return 0
    if n == 1:
        return 1

    # Caso recursivo: F(n) = F(n-1) + F(n-2)
    return fibonacci(n - 1) + fibonacci(n - 2)

# Ejemplos
for i in range(8):
    print(f"fibonacci({i}) = {fibonacci(i)}")

# Output:
# fibonacci(0) = 0
# fibonacci(1) = 1
# fibonacci(2) = 1
# fibonacci(3) = 2
# fibonacci(4) = 3
# fibonacci(5) = 5
# fibonacci(6) = 8
# fibonacci(7) = 13

2. Suma de una Lista

def suma_recursiva(lista):
    """Suma todos los elementos de una lista recursivamente"""
    # Caso base: lista vacía
    if len(lista) == 0:
        return 0

    # Caso recursivo: primer elemento + suma del resto
    return lista[0] + suma_recursiva(lista[1:])

numeros = [1, 2, 3, 4, 5]
print(suma_recursiva(numeros))  # Output: 15

3. Potencia

def potencia(base, exponente):
    """Calcula base^exponente de forma recursiva"""
    # Caso base
    if exponente == 0:
        return 1

    # Caso recursivo: base^n = base * base^(n-1)
    return base * potencia(base, exponente - 1)

print(potencia(2, 5))   # Output: 32
print(potencia(3, 3))   # Output: 27
print(potencia(10, 0))  # Output: 1

El Call Stack (Pila de Llamadas)

Python usa una pila de llamadas para gestionar las llamadas recursivas:

def ejemplo_stack(n):
    """Demuestra el call stack"""
    print(f"Entrando con n={n}")

    if n <= 0:
        print("¡Caso base alcanzado!")
        return

    ejemplo_stack(n - 1)  # Llamada recursiva

    print(f"Saliendo con n={n}")

ejemplo_stack(3)

# Output:
# Entrando con n=3
# Entrando con n=2
# Entrando con n=1
# Entrando con n=0
# ¡Caso base alcanzado!
# Saliendo con n=1
# Saliendo con n=2
# Saliendo con n=3

Visualización del stack:

ejemplo_stack(3)
  └─ ejemplo_stack(2)
      └─ ejemplo_stack(1)
          └─ ejemplo_stack(0)  ← Caso base

Recursión con Estructuras de Datos

Recorrer Directorios

import os

def listar_archivos(ruta, nivel=0):
    """Lista archivos y carpetas recursivamente"""
    try:
        elementos = os.listdir(ruta)

        for elemento in elementos:
            ruta_completa = os.path.join(ruta, elemento)
            print("  " * nivel + elemento)

            # Si es directorio, llamada recursiva
            if os.path.isdir(ruta_completa):
                listar_archivos(ruta_completa, nivel + 1)

    except PermissionError:
        print("  " * nivel + "[Permiso denegado]")

# Uso
listar_archivos("./mi_proyecto")

Aplanar Listas Anidadas

def aplanar_lista(lista):
    """Convierte una lista anidada en una lista plana"""
    resultado = []

    for elemento in lista:
        # Si el elemento es una lista, recursión
        if isinstance(elemento, list):
            resultado.extend(aplanar_lista(elemento))
        else:
            resultado.append(elemento)

    return resultado

# Ejemplo
anidada = [1, [2, 3, [4, 5]], 6, [7, [8, 9]]]
print(aplanar_lista(anidada))
# Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Búsqueda en Árbol Binario

class Nodo:
    def __init__(self, valor):
        self.valor = valor
        self.izquierdo = None
        self.derecho = None

def buscar_en_arbol(nodo, objetivo):
    """Busca un valor en un árbol binario recursivamente"""
    # Caso base: árbol vacío
    if nodo is None:
        return False

    # Caso base: valor encontrado
    if nodo.valor == objetivo:
        return True

    # Caso recursivo: buscar en subárboles
    return (buscar_en_arbol(nodo.izquierdo, objetivo) or
            buscar_en_arbol(nodo.derecho, objetivo))

# Crear árbol
raiz = Nodo(10)
raiz.izquierdo = Nodo(5)
raiz.derecho = Nodo(15)
raiz.izquierdo.izquierdo = Nodo(3)
raiz.izquierdo.derecho = Nodo(7)

print(buscar_en_arbol(raiz, 7))   # Output: True
print(buscar_en_arbol(raiz, 20))  # Output: False

Recursión vs Iteración

Muchos problemas recursivos pueden resolverse con bucles:

Factorial Iterativo

# Versión recursiva
def factorial_rec(n):
    if n <= 1:
        return 1
    return n * factorial_rec(n - 1)

# Versión iterativa
def factorial_iter(n):
    resultado = 1
    for i in range(2, n + 1):
        resultado *= i
    return resultado

# Ambas producen el mismo resultado
print(factorial_rec(5))   # Output: 120
print(factorial_iter(5))  # Output: 120

Comparación:

Fibonacci Optimizado con Memoización

La recursión puede optimizarse con memoización (cache de resultados):

# Sin memoización (muy lento para n > 35)
def fib_lento(n):
    if n <= 1:
        return n
    return fib_lento(n - 1) + fib_lento(n - 2)

# Con memoización usando decorador
from functools import lru_cache

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

# Comparación
import time

inicio = time.time()
print(fib_lento(35))
print(f"Sin memo: {time.time() - inicio:.2f}s")  # ~5 segundos

inicio = time.time()
print(fib_rapido(35))
print(f"Con memo: {time.time() - inicio:.4f}s")  # ~0.0001 segundos

Límite de Recursión en Python

Python tiene un límite de recursión por defecto (generalmente 1000):

import sys

# Ver el límite actual
print(sys.getrecursionlimit())  # Output: 1000

# Ejemplo que excede el límite
def recursion_infinita(n):
    return recursion_infinita(n + 1)

try:
    recursion_infinita(0)
except RecursionError as e:
    print(f"Error: {e}")
    # Output: Error: maximum recursion depth exceeded

# Modificar el límite (con precaución)
sys.setrecursionlimit(2000)
print(sys.getrecursionlimit())  # Output: 2000

⚠️ Advertencia: Aumentar el límite puede causar crashes si no hay suficiente memoria.

Casos Prácticos de Recursión

1. Validador de Palíndromos

def es_palindromo(texto):
    """Verifica si un texto es palíndromo recursivamente"""
    # Limpiar el texto
    texto = texto.lower().replace(" ", "")

    # Caso base: texto vacío o de un carácter
    if len(texto) <= 1:
        return True

    # Caso recursivo: comparar extremos
    if texto[0] != texto[-1]:
        return False

    return es_palindromo(texto[1:-1])

# Ejemplos
print(es_palindromo("reconocer"))        # True
print(es_palindromo("anita lava la tina"))  # True
print(es_palindromo("python"))           # False

2. Generador de Permutaciones

def permutaciones(elementos):
    """Genera todas las permutaciones de una lista"""
    # Caso base: un solo elemento
    if len(elementos) <= 1:
        return [elementos]

    # Caso recursivo
    perms = []
    for i, elem in enumerate(elementos):
        # Elementos restantes
        resto = elementos[:i] + elementos[i+1:]

        # Permutaciones del resto
        for perm in permutaciones(resto):
            perms.append([elem] + perm)

    return perms

# Ejemplo
letras = ['A', 'B', 'C']
for p in permutaciones(letras):
    print(p)

# Output:
# ['A', 'B', 'C']
# ['A', 'C', 'B']
# ['B', 'A', 'C']
# ['B', 'C', 'A']
# ['C', 'A', 'B']
# ['C', 'B', 'A']

3. Búsqueda Binaria Recursiva

def busqueda_binaria(lista, objetivo, inicio=0, fin=None):
    """Busca un elemento en una lista ordenada recursivamente"""
    if fin is None:
        fin = len(lista) - 1

    # Caso base: elemento no encontrado
    if inicio > fin:
        return -1

    # Punto medio
    medio = (inicio + fin) // 2

    # Caso base: elemento encontrado
    if lista[medio] == objetivo:
        return medio

    # Caso recursivo: buscar en mitad correspondiente
    if lista[medio] > objetivo:
        return busqueda_binaria(lista, objetivo, inicio, medio - 1)
    else:
        return busqueda_binaria(lista, objetivo, medio + 1, fin)

# Ejemplo
numeros = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(busqueda_binaria(numeros, 13))  # Output: 6
print(busqueda_binaria(numeros, 8))   # Output: -1

Errores Comunes y Cómo Evitarlos

1. Olvidar el Caso Base

# ❌ MAL: Recursión infinita
def contar_mal(n):
    print(n)
    contar_mal(n + 1)  # ¡Nunca termina!

# ✅ BIEN: Con caso base
def contar_bien(n, limite):
    if n > limite:  # Caso base
        return
    print(n)
    contar_bien(n + 1, limite)

2. No Avanzar Hacia el Caso Base

# ❌ MAL: No progresa
def suma_mal(lista):
    if len(lista) == 0:
        return 0
    return lista[0] + suma_mal(lista)  # ¡Siempre la misma lista!

# ✅ BIEN: Reduce el problema
def suma_bien(lista):
    if len(lista) == 0:
        return 0
    return lista[0] + suma_bien(lista[1:])  # Lista más pequeña

3. No Retornar el Resultado Recursivo

# ❌ MAL: No retorna el resultado
def factorial_mal(n):
    if n <= 1:
        return 1
    factorial_mal(n - 1)  # Falta el return

# ✅ BIEN: Retorna el resultado
def factorial_bien(n):
    if n <= 1:
        return 1
    return n * factorial_bien(n - 1)

4. Modificar Variables Globales

# ❌ MAL: Usa variable global
total = 0

def suma_global(lista):
    global total
    if len(lista) == 0:
        return total
    total += lista[0]
    return suma_global(lista[1:])

# ✅ BIEN: Parámetro acumulador
def suma_acumulador(lista, acumulador=0):
    if len(lista) == 0:
        return acumulador
    return suma_acumulador(lista[1:], acumulador + lista[0])

Buenas Prácticas con Recursión

1. Usar Recursión para Problemas Naturalmente Recursivos

# Bueno para: estructuras jerárquicas
def calcular_tamano_directorio(ruta):
    """Calcula el tamaño total de un directorio"""
    import os
    tamano = 0

    for elemento in os.listdir(ruta):
        ruta_completa = os.path.join(ruta, elemento)

        if os.path.isfile(ruta_completa):
            tamano += os.path.getsize(ruta_completa)
        elif os.path.isdir(ruta_completa):
            tamano += calcular_tamano_directorio(ruta_completa)

    return tamano

2. Documentar Claramente los Casos

def quicksort(lista):
    """
    Ordena una lista usando quicksort.

    Casos:
    - Base: Lista vacía o de un elemento → ya ordenada
    - Recursivo: Particionar alrededor de un pivote
    """
    # Caso base
    if len(lista) <= 1:
        return lista

    # Caso recursivo
    pivote = lista[len(lista) // 2]
    menores = [x for x in lista if x < pivote]
    iguales = [x for x in lista if x == pivote]
    mayores = [x for x in lista if x > pivote]

    return quicksort(menores) + iguales + quicksort(mayores)

print(quicksort([3, 6, 8, 10, 1, 2, 1]))
# Output: [1, 1, 2, 3, 6, 8, 10]

3. Considerar Alternativas Iterativas para Rendimiento

# Recursivo (elegante pero lento)
def suma_rec(n):
    if n == 0:
        return 0
    return n + suma_rec(n - 1)

# Iterativo (más eficiente)
def suma_iter(n):
    total = 0
    for i in range(n + 1):
        total += i
    return total

# O mejor aún, usar fórmula matemática
def suma_formula(n):
    return n * (n + 1) // 2

# Los tres dan el mismo resultado
print(suma_rec(100))      # 5050
print(suma_iter(100))     # 5050
print(suma_formula(100))  # 5050

Recursión de Cola (Tail Recursion)

La recursión de cola ocurre cuando la llamada recursiva es la última operación:

# No es recursión de cola (operación después de la recursión)
def factorial_normal(n):
    if n <= 1:
        return 1
    return n * factorial_normal(n - 1)  # Multiplicación después

# Recursión de cola (con acumulador)
def factorial_cola(n, acumulador=1):
    if n <= 1:
        return acumulador
    return factorial_cola(n - 1, n * acumulador)  # Última operación

print(factorial_normal(5))    # 120
print(factorial_cola(5))      # 120

Nota: Python no optimiza automáticamente la recursión de cola, pero el patrón puede ser más claro.

Pepitas de conocimiento:

La recursión es una herramienta poderosa en Python que permite:

✅ Resolver problemas complejos dividiéndolos en subproblemas
✅ Trabajar con estructuras jerárquicas (árboles, grafos)
✅ Implementar algoritmos elegantes (quicksort, búsqueda binaria)
✅ Simplificar código para problemas naturalmente recursivos

Recuerda:

• Siempre define un caso base claro
• Asegúrate de avanzar hacia el caso base
• Considera el límite de recursión de Python
• Evalúa si una solución iterativa es más apropiada
• Usa memoización para optimizar recursiones costosas

Profundiza en Python

Si quieres dominar la recursión y otros conceptos avanzados de Python, te recomiendo mi libro Python a fondo, donde encontrarás:

• Capítulos dedicados a algoritmos recursivos
• Técnicas de optimización avanzadas
• Casos de uso en el mundo real
• Ejercicios prácticos con soluciones

Artículos relacionados:

• Funciones en Python: Guía Completa
• Lambdas en Python: Funciones Anónimas
• Map, Filter y Reduce en Python