Recursión y memoización

Tema: Programación Dinámica · temarios: Syllabus OCI · Syllabus IOI

📍 Dónde se aprende: módulo 09 de la Ruta de Aprendizaje.

El problema: una solución recursiva repite trabajo

Una función recursiva resuelve un problema llamándose sobre casos más pequeños. Por ejemplo, la sucesión de Fibonacci se define con F(0)=0, F(1)=1 y F(n)=F(n−1)+F(n−2) para n≥2. Es una buena primera recurrencia para entender cómo guardar resultados, aunque Fibonacci también admite soluciones más eficientes en memoria que la que estudiaremos aquí.

Calcular F(5) por expansión directa exige F(4) y F(3). A su vez, F(4) vuelve a pedir F(3). Resolvemos varias veces exactamente la misma pregunta.

F(5)F(4)F(3)F(3)F(2)Misma pregunta F(3)Expandir una vez; las siguientes llamadas recuperan la respuesta

Si el diagrama no cabe, deslízalo horizontalmente.

La memoización guarda la respuesta de una llamada para reutilizarla. El estado es la información que identifica esa pregunta: aquí basta n, porque F(n) siempre tiene el mismo resultado.

Guardar respuestas sin cambiar la recurrencia

Lo que pide el cálculo de F(5)Qué sucede
F(4), luego F(3), luego F(2)aún no están guardados: seguir bajando
F(1) y F(0)casos base: devolver 1 y 0
Terminar F(2)guardar 1
Terminar F(3)sumar F(2)+F(1) y guardar 2
Terminar F(4)reutilizar F(2) y guardar 3
Terminar F(5)reutilizar F(3) y guardar 5

Una llamada repetida todavía ocurre, pero ahora consulta una casilla y retorna. No vuelve a expandir todo su árbol de dependencias. El resultado es el mismo: guardar F(n) después de resolver sus dependencias conserva la definición original.

Implementación: uno y dos parámetros

// Top-down: la recurrencia tal cual, más un arreglo que recuerda lo ya resuelto.
vector<long long> memo;                  // -1 = "todavía no lo calculo"
 
long long fib(int n) {
    if (n <= 1) return n;                // caso base
    if (memo[n] != -1) return memo[n];   // ya resuelto: devolver la copia
    return memo[n] = fib(n - 1) + fib(n - 2);
}
// uso: memo.assign(n + 1, -1);  cout << fib(n);
 
// Con dos dimensiones es el mismo patrón. La referencia (&) evita repetir el
// índice tres veces; ver la ficha Punteros y referencias, en Relacionados.
vector<vector<long long>> memo2;
 
long long caminos(int i, int j) {        // caminos en una grilla hasta (i, j)
    if (i == 0 || j == 0) return 1;      // por el borde hay uno solo
    long long& m = memo2[i][j];
    if (m != -1) return m;
    return m = caminos(i - 1, j) + caminos(i, j - 1);
}
// uso: memo2.assign(n + 1, vector<long long>(m + 1, -1));

Para Fibonacci, ejecuta memo.assign(6,-1) y después fib(5): devuelve 5. El −1 significa «sin calcular» y no es una respuesta válida de Fibonacci. La memoria debe tener al menos n+1 casillas. Esta implementación admite n≥0 y, con long long de 64 bits, resultados hasta F(92); F(93) ya no cabe.

Los n+1 estados de Fibonacci tienen trabajo constante cada uno, así que el tiempo es O(n). La tabla y la profundidad máxima de llamadas usan O(n) memoria. La expansión sin recordar respuestas realiza una cantidad exponencial de llamadas. Memoizar reduce repeticiones, pero no la profundidad de la primera bajada.

Derivar un estado con dos coordenadas

Ahora contamos caminos desde (0,0) hasta (i,j) moviéndonos solo abajo o a la derecha, sin obstáculos. El último movimiento llegó desde (i−1,j) o desde (i,j−1). Esos casos son distintos y cubren todas las posibilidades:

caminos(i,j) = caminos(i−1,j) + caminos(i,j−1).

En el borde i=0 o j=0 hay un solo camino recto. Para destino (2,2), memo2.assign(3, vector<long long>(3,-1)) prepara la tabla y caminos(2,2) devuelve 6. Las cantidades por coordenada son:

i / j012
0111
1123
2136

Hay O((i+1)(j+1)) estados y trabajo constante por estado. La profundidad máxima es O(i+j). Los índices deben ser no negativos, la tabla suficientemente grande y los conteos deben caber en long long. long long& m es una referencia a una casilla: asignar a m actualiza memo2[i][j].

Cuándo una clave de memoización es suficiente

Dos llamadas con la misma clave deben tener la misma respuesta. Si la pregunta también depende de capacidad restante, objetos disponibles o restricciones, esa información tiene que estar en el estado o permanecer fija durante todo el cálculo. Al cambiar los datos del problema, reinicia la memoria.

Elige un centinela fuera del conjunto de resultados, o usa un arreglo separado de «calculado». Si −1 puede ser una respuesta, esta comprobación confundirá ese resultado con uno pendiente y repetirá trabajo. Inicializar por error la tabla en cero, en cambio, hace que la función devuelva resultados falsos ya marcados como calculados.

La versión top-down calcula desde la pregunta original hacia sus dependencias. La versión bottom-up llena los estados en un orden que tenga resueltas esas dependencias. Mochila 0-1 y DP de intervalos muestran cómo elegir ese orden.