Recursión y memoización

La idea

Un algoritmo es recursivo cuando se define en términos de sí mismo sobre entradas más pequeñas. Toda recursión bien formada necesita dos ingredientes: uno o varios casos base que se resuelven sin volver a llamarse, y un paso recursivo que reduce estrictamente el tamaño del problema para que la cadena de llamadas termine. El factorial es el ejemplo mínimo, n! = n · (n − 1)! con 0! = 1, y la torre de Hanói el más elegante: para mover n discos de la varilla origen al destino, se mueven n − 1 a la auxiliar, se pasa el disco grande y se traen los n − 1 encima, lo que da exactamente 2ⁿ − 1 movimientos.

La recursión puede ser ruinosa si repite trabajo. Calcular Fibonacci con F(n) = F(n − 1) + F(n − 2) de forma directa ejecuta 2·F(n + 1) − 1 llamadas, un crecimiento exponencial de razón φ ≈ 1,618: para n = 40 son más de trescientos millones de llamadas, aunque solo haya 41 valores distintos que calcular. La memoización guarda cada resultado la primera vez que se obtiene y lo reutiliza después; el número de llamadas baja a 2n − 1 y el coste pasa de O(φⁿ) a O(n). Esta idea, aplicada sistemáticamente, es la programación dinámica.

Cada llamada pendiente ocupa un marco en la pila, de modo que la profundidad de la recursión es también consumo de memoria: recursiones muy profundas provocan desbordamiento de pila. Las recursiones de cola, en las que la llamada recursiva es la última operación, se pueden convertir mecánicamente en bucles. El teorema maestro resuelve de un golpe muchas recurrencias de la forma T(n) = a T(n/b) + f(n): con a = 2, b = 2 y f(n) = n se obtiene el O(n log n) del ordenamiento por mezcla.

Fórmulas clave

• Factorialn! = n · (n − 1)!, 0! = 1
• FibonacciF(n) = F(n − 1) + F(n − 2), F(0) = 0, F(1) = 1
• Llamadas de Fibonacci directoL(n) = 2 F(n + 1) − 1 → O(φⁿ), φ = (1 + √5)/2
• Fibonacci con memoizaciónL(n) = 2n − 1 → O(n)
• Torres de HanóiH(n) = 2 H(n − 1) + 1 = 2ⁿ − 1 movimientos
• Teorema maestroT(n) = a T(n/b) + f(n); si f(n) = Θ(n^log_b a) → T(n) = Θ(n^log_b a · log n)

Dónde se aplica

Los compiladores analizan el código con descenso recursivo, una función por regla gramatical, y los intérpretes de JSON o XML recorren árboles de la misma forma. En bioinformática, el alineamiento de secuencias de ADN se resuelve con programación dinámica (Needleman-Wunsch), que es exactamente una recursión memoizada sobre una tabla. En finanzas, la valoración de opciones con árboles binomiales recorre el árbol hacia atrás reutilizando valores ya calculados, y en gráficos por computadora el trazado de rayos y las estructuras espaciales como los árboles k-d son recursivos por naturaleza.

Con programación (Python)

import math

llamadas = 0
def fib(n):
    global llamadas
    llamadas += 1
    return n if n < 2 else fib(n - 1) + fib(n - 2)

memo, llamadas_memo = {}, 0
def fib_memo(n):
    global llamadas_memo
    llamadas_memo += 1
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]

print("fib(25) directo =", fib(25), " llamadas:", llamadas)
print("fib(25) memoizado =", fib_memo(25), " llamadas:", llamadas_memo)

movimientos = []
def hanoi(n, o, d, aux):
    if n == 0:
        return
    hanoi(n - 1, o, aux, d)
    movimientos.append(f"disco {n}: {o}->{d}")
    hanoi(n - 1, aux, d, o)

hanoi(4, "A", "C", "B")
print("Hanoi con 4 discos:", len(movimientos), "movimientos (2^4 - 1 =", 2 ** 4 - 1, ")")
print(" | ".join(movimientos[:7]), "...")

def fact(n):
    return 1 if n <= 1 else n * fact(n - 1)
print("factoriales:", [fact(k) for k in range(8)])

La versión en JavaScript, editable y ejecutable en el navegador, está en la página interactiva del tema.

Temas relacionados

Algoritmos de ordenamiento · Combinatoria y triángulo de Pascal · Complejidad y notación O grande