Memorización (Memoization)

El problema de la recursión ingenua

Recordemos la función de Fibonacci recursiva:

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

Para calcular fib(5), la función hace estas llamadas:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1) = 1
│   │   │   └── fib(0) = 0
│   │   └── fib(1) = 1
│   └── fib(2)          ← ¡Ya lo calculamos!
│       ├── fib(1) = 1
│       └── fib(0) = 0
└── fib(3)               ← ¡Ya lo calculamos!
    ├── fib(2)           ← ¡Ya lo calculamos!
    │   ├── fib(1) = 1
    │   └── fib(0) = 0
    └── fib(1) = 1

¡fib(2) se calcula 3 veces y fib(3) se calcula 2 veces! Para fib(50), hay miles de millones de llamadas repetidas. El tiempo es $O(2^n)$: ¡imposible!

Analogía: Es como si cada vez que necesitas saber cuánto es $7 \times 8$, hicieras toda la multiplicación desde cero, en lugar de simplemente recordar que es 56.

La solución: memorizar

La idea es simple: antes de calcular algo, verifica si ya lo calculaste. Si sí, usa el resultado guardado. Si no, calcúlalo y guárdalo para el futuro.

long long memo[101];  // Arreglo para guardar resultados
bool calculado[101];  // Para saber si ya se calculó

long long fib(int n) {
    if (n <= 1) return n;
    if (calculado[n]) return memo[n];  // Si ya lo calculamos, retornarlo

    memo[n] = fib(n-1) + fib(n-2);    // Calcular
    calculado[n] = true;               // Marcar como calculado
    return memo[n];
}

Versión más limpia con -1 como "no calculado"

long long memo[101];

void init() {
    memset(memo, -1, sizeof(memo));  // Llenar todo con -1
}

long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];  // Ya calculado

    return memo[n] = fib(n-1) + fib(n-2);  // Calcular y guardar
}

¿Qué cambió?

Ahora el árbol de llamadas se "poda":

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1) = 1
│   │   │   └── fib(0) = 0
│   │   └── fib(1) = 1
│   └── fib(2) = 1  ← ¡Ya guardado! O(1)
└── fib(3) = 2      ← ¡Ya guardado! O(1)

De $O(2^n)$ pasamos a $O(n)$: cada valor se calcula exactamente una vez.

Cuándo usar memorización

La memorización funciona cuando se cumplen dos condiciones:

1. Subproblemas repetidos: El mismo subproblema se resuelve múltiples veces.
2. Estructura óptima: La solución del problema se construye a partir de soluciones de subproblemas.

Esto es la base de la Programación Dinámica (que veremos más adelante).

Ejemplo: subir escaleras

Problema: Puedes subir una escalera de 1 o 2 escalones a la vez. ¿De cuántas formas puedes subir N escalones?

n=1: 1 forma (1)
n=2: 2 formas (1+1, 2)
n=3: 3 formas (1+1+1, 1+2, 2+1)
n=4: 5 formas

Sin memorización (lento):

int formas(int n) {
    if (n <= 1) return 1;
    return formas(n-1) + formas(n-2);
}

Con memorización (rápido):

int memo[100001];

int formas(int n) {
    if (n <= 1) return 1;
    if (memo[n] != -1) return memo[n];
    return memo[n] = formas(n-1) + formas(n-2);
}

Ejemplo: caminos en una cuadrícula

Problema: En una cuadrícula de $m \times n$, ¿cuántos caminos hay desde la esquina superior izquierda hasta la inferior derecha, si solo puedes moverte hacia abajo o hacia la derecha?

int memo[101][101];

int caminos(int m, int n) {
    if (m == 1 || n == 1) return 1;
    if (memo[m][n] != -1) return memo[m][n];
    return memo[m][n] = caminos(m-1, n) + caminos(m, n-1);
}

int main() {
    memset(memo, -1, sizeof(memo));
    cout << caminos(3, 3) << endl;  // 6
    return 0;
}

Memorización con map (para estados más complejos)

Cuando los estados no son simples índices enteros, puedes usar un map:

map<pair<int,int>, long long> memo;

long long resolver(int a, int b) {
    if (/* caso base */) return /* valor */;

    auto key = make_pair(a, b);
    if (memo.count(key)) return memo[key];

    return memo[key] = /* cálculo recursivo */;
}

De recursión con memo a iteración (bottom-up)

La memorización es top-down (empiezas del problema grande y descompones). Puedes convertirla a bottom-up (empiezas de los problemas pequeños y construyes):

// Fibonacci top-down (recursivo con memo)
long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n-1) + fib(n-2);
}

// Fibonacci bottom-up (iterativo)
long long fibIterativo(int n) {
    vector<long long> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

Ambos son $O(n)$, pero el iterativo evita el overhead de la recursión y el riesgo de stack overflow.

Ejercicio de práctica

Usa memorización para calcular el coeficiente binomial $C(n, k) = \binom{n}{k}$ usando la relación: $C(n, k) = C(n-1, k-1) + C(n-1, k)$, con $C(n, 0) = C(n, n) = 1$.

#include <iostream>
#include <cstring>
using namespace std;

long long memo[101][101];

long long C(int n, int k) {
    if (k == 0 || k == n) return 1;
    if (memo[n][k] != -1) return memo[n][k];
    return memo[n][k] = C(n-1, k-1) + C(n-1, k);
}

int main() {
    memset(memo, -1, sizeof(memo));

    int n, k;
    cin >> n >> k;
    cout << C(n, k) << endl;

    return 0;
}

Siguiente paso

Aprende sobre la Complejidad de la Recursión para analizar cuánto tiempo y memoria usa tu función recursiva.