Recursión

📐 Fundamento

Toda función recursiva tiene dos partes:

1. Caso base. Condición(es) en las que la función devuelve directamente, sin recursar.
2. Caso recursivo. Llamadas a sí misma con un problema estrictamente más chico.

Ejemplo canónico — factorial.

$n! = \begin{cases} 1 & \text{si } n = 0 \ n \cdot (n-1)! & \text{si } n > 0 \end{cases}$

def factorial(n):
    if n == 0:           # caso base
        return 1
    return n * factorial(n - 1)    # caso recursivo

Cómo "ver" la ejecución de factorial(4):

factorial(4)
  = 4 * factorial(3)
    = 4 * (3 * factorial(2))
      = 4 * (3 * (2 * factorial(1)))
        = 4 * (3 * (2 * (1 * factorial(0))))
          = 4 * (3 * (2 * (1 * 1)))     ← caso base
        = 4 * (3 * (2 * 1))
      = 4 * (3 * 2)
    = 4 * 6
  = 24

Cada llamada se apila sobre la anterior. La pila crece hasta el caso base, después se "resuelven" en orden inverso.

Las tres preguntas para verificar una recursión:

1. ¿Hay caso base? Sin él, no termina.
2. ¿El caso recursivo se acerca al caso base? Sin esto, tampoco termina.
3. ¿La función es correcta asumiendo que las llamadas internas son correctas? Esto se llama inducción.

Si las tres se cumplen, la función es correcta y termina.

📐 Fundamento

Toda función recursiva se puede convertir en iterativa, y viceversa. La pregunta es cuál es más natural para el problema.

Factorial — iterativo:

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

Más simple, no agota pila. Iterativo gana acá.

Suma de árbol — recursivo:

def suma(arbol):
    """arbol = (valor, [hijos])"""
    valor, hijos = arbol
    return valor + sum(suma(h) for h in hijos)

Iterativo sería un horror (necesitás simular pila). Recursivo gana porque la estructura del problema es recursiva (un árbol contiene subárboles).

Regla práctica

No es ideológico — usá lo que se lea mejor.

📐 Fundamento

Estrategia: dividí el problema, resolvé las partes recursivamente, combiná las soluciones. La búsqueda binaria es un ejemplo.

Mergesort

Ordenar una lista dividiéndola y mezclando.

def mergesort(lista):
    if len(lista) <= 1:
        return lista
    mitad = len(lista) // 2
    izq = mergesort(lista[:mitad])
    der = mergesort(lista[mitad:])
    return merge(izq, der)

def merge(a, b):
    """Mezcla dos listas ordenadas en una ordenada."""
    r = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            r.append(a[i]); i += 1
        else:
            r.append(b[j]); j += 1
    r.extend(a[i:])
    r.extend(b[j:])
    return r

print(mergesort([5, 2, 8, 1, 9, 3]))    # [1, 2, 3, 5, 8, 9]

Tiempo: $O(n \log n)$. Es el algoritmo más usado en bibliotecas estándar (Java, Python sort usa una variante llamada Timsort).

Quicksort (esbozo)

def quicksort(lista):
    if len(lista) <= 1:
        return lista
    pivote = lista[0]
    izq = [x for x in lista[1:] if x < pivote]
    der = [x for x in lista[1:] if x >= pivote]
    return quicksort(izq) + [pivote] + quicksort(der)

Promedio $O(n \log n)$, peor caso $O(n^2)$. Es in-place y rápido en práctica con buena elección de pivote.

📐 Fundamento

Una llamada de cola es cuando lo último que hace una función es llamar a otra (sin operaciones después). Algunos lenguajes la optimizan reusando el mismo frame (no crece la pila).

# Recursión de cola (en lenguajes con TCO):
def factorial(n, acc=1):
    if n == 0:
        return acc
    return factorial(n - 1, n * acc)

En Lisp, Scheme, Erlang, Scala, Haskell — TCO (tail call optimization) convierte eso en bucle. En Python no: cada llamada sigue ocupando frame. Por eso seguís topándote contra el límite.

Guido van Rossum (creador de Python) explicó que omitió TCO a propósito: facilita el debugging (ves el call stack) y prefiere la sintaxis explícita de bucles.

Conclusión: en Python, si querés profundidad arbitraria, convertí a iterativo.

📐 Fundamento

Memoización = recordar resultados. Aplicable a cualquier función pura (mismo input → mismo output).

Manual:

def memoizar(func):
    cache = {}
    def wrapper(*args):
        if args in cache:
            return cache[args]
        r = func(*args)
        cache[args] = r
        return r
    return wrapper

@memoizar
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

@memoizar es un decorador — modifica fib envolviéndola.

Built-in: functools.lru_cache y functools.cache (Python 3.9+).

from functools import cache

@cache
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

Una línea, problema resuelto.

Cuándo usar memoización:

• Función pura (sin side-effects).
• Inputs hashables (los args van a un dict interno).
• Mismo cálculo se hace varias veces.

Si la función tiene side-effects (escribe a disco, modifica globales), memoización los suprime silenciosamente — bug grave.