09 · Recursión
Buscar soluciones eficientes · Ruta de Aprendizaje
Antes de empezar. Funciones y condiciones: 00 - Programar desde cero; vectores para recordar resultados: 03 - Arreglos y búsqueda lineal. Para comparar costos, 07 - Cuánto se demora tu programa.
🎯 Objetivos
Al terminar este módulo sabes:
- Escribir funciones recursivas con caso base y paso recursivo.
- Ver el árbol de llamadas y estimar cuántas son.
- Reconocer el problema de recalcular (y su cura: recordar).
📖 La lección
Una función que se llama a sí misma
Supón que doble(x) devuelve 2*x. Si escribes 2 * doble(3), primero necesitas el resultado de doble(3)
y después haces la multiplicación pendiente. Una función recursiva conserva
trabajo pendiente de la misma manera, pero llama a otra ejecución de sí misma
con datos más pequeños. Cada ejecución tiene sus propios parámetros.
Toda recursión tiene dos piezas: el caso base (dónde se detiene) y el paso recursivo (cómo se reduce a un problema más chico):
El factorial n! es el producto 1·2·…·n; por convenio, 0! = 1.
Por ejemplo, 4! = 4·3! = 24. Esta implementación usa long long y
admite 0 <= n <= 20: después, el resultado deja de caber.
long long factorial(int n) {
if (n <= 1) return 1; // caso base: dónde se detiene
return n * factorial(n - 1); // paso recursivo: el problema más chico
}Sin caso base, las llamadas se apilan hasta reventar la pila (stack
overflow — un RTE clásico). Cada llamada pendiente vive en la pila de
llamadas esperando a las de más abajo. Así se ve factorial(4):
Si el diagrama no cabe, deslízalo horizontalmente.
Léelo en dos tiempos: primero bajan las llamadas, cada una detenida en
mitad de su return esperando el valor que le falta; cuando la de abajo
responde 1, las demás terminan en cadena, de la más nueva a la más vieja.
Qué queda pendiente al llamar
Cada llamada tiene su propio n y recuerda dónde continuar. Este programa hace visible la ida y la vuelta:
#include <iostream>
using namespace std;
void visitar(int n) {
if (n == 0) return;
cout << "entra " << n << "\n";
visitar(n - 1);
cout << "sale " << n << "\n";
}
int main() { visitar(2); }Salida: entra 2, entra 1, sale 1, sale 2, en ese orden. Mientras corre visitar(1), la llamada con n=2 espera en la línea posterior a su llamada recursiva. El n de la llamada nueva no reemplaza al anterior. Hay tres llamadas en total (incluido n=0), y como máximo tres activas a la vez. En un árbol con varias ramas, el total puede ser mucho mayor que la profundidad.
El árbol de llamadas (y su lado oscuro)
Fibonacci empieza con F(0) = 0, F(1) = 1 y continúa con
F(n) = F(n-1) + F(n-2): 0, 1, 1, 2, 3, 5, 8….
La versión recursiva directa se ve inocente, pero cada llamada abre otras dos:
un árbol que crece exponencialmente y recalcula lo mismo una y otra vez.
Primero contemos las llamadas de esa versión directa:
long long llamadas_lento = 0;
long long fib_lento(int n) {
llamadas_lento++;
if (n <= 1) return n;
return fib_lento(n - 1) + fib_lento(n - 2); // recalcula lo mismo mil veces
}
Cuando dos llamadas preguntan por el mismo n, sus respuestas serán iguales.
Podemos guardar la primera y reutilizarla. memo[n] conserva esa respuesta;
−1 significa «aún no calculada», un valor que Fibonacci nunca devuelve para n no negativo.
long long llamadas_rapido = 0;
vector<long long> memo(95, -1); // -1 significa "todavía no lo calculo"
long long fib_rapido(int n) {
llamadas_rapido++;
if (n <= 1) return n;
if (memo[n] != -1) return memo[n]; // ya lo calculamos: reutilizar
return memo[n] = fib_rapido(n - 1) + fib_rapido(n - 2);
}Con n = 30, fib_lento hace 2.692.537 llamadas y fib_rapido… 59.
Para ver por qué, dibuja el árbol de un caso chico, fib(5):
Si el diagrama no cabe, deslízalo horizontalmente.
Cuenta los nodos: 15 llamadas para n = 5, y cada +1 de n multiplica el árbol
por ~1,6 (crece igual que los propios números de Fibonacci) — por eso fib(30)
pasa de los dos millones. La memoización corta cada
subárbol repetido apenas asoma (los atenuados): quedan 9, o sea 2n − 1, y con
n = 30 eso es 59.
Los valores de Fibonacci caben en long long de 64 bits hasta F(92).
El tamaño del vector no evita el desbordamiento: usa 0 <= n <= 92.
La versión lenta solo es práctica para valores pequeños. Al repetir una
comparación de llamadas, reinicia los contadores y la memoización.
Ese truco de “anotar lo ya resuelto” se llama memoización, y en las siguientes clases se convierte en la puerta de entrada a la programación dinámica. La ficha con el patrón completo —incluidos los dos errores que más cuestan— es Recursión y memoización.
Cuándo pensar recursivo
Cuando el problema se define naturalmente en términos de sí mismo: potencias
(b^e = b·b^(e-1)), sumas de dígitos, recorrer estructuras anidadas, y —
generar todas las combinaciones de algo
(backtracking). La profundidad segura depende de la memoria de pila y del tamaño de cada llamada; no hay un número universal. Si la profundidad puede crecer con una entrada grande, conviene una versión iterativa.
Ejercicios de dedos (sin juez)
potencia(b, e)recursiva (enteros; luego compárala con un ciclo).suma_digitos(n): 407 → 11, en tres líneas recursivas.- Corre el contador de fib con n = 20, 25, 30 y mira cómo escala cada versión.
🏋️ Práctica
Práctica directa: Seguir una llamada
Modifica visitar(2) para ejecutar visitar(3). La salida debe ser entra 3, entra 2, entra 1, sale 1, sale 2, sale 3, una por línea.
Idea para comprobar tu solución
Cada llamada conserva su n y continúa tras la llamada hija. El caso n=0 retorna sin imprimir.
Variación: Seguir el retorno
Define una función que sume los dígitos de un entero no negativo: para 507 debe devolver 12 y para 0 debe devolver 0.
Una pista, si la necesitas
Separa el último dígito del número que queda.
Contrastar el razonamiento
Usa el caso base 0. Para otro n, devuelve n%10 más la respuesta para n/10. Las llamadas para 507 pasan por 50, 5 y 0; los retornos son 0, 5, 5 y 12.
Aplicar en problemas
Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.
Problemas OCI reales, en español (cada nota trae el link a su mirror):
| # | Problema | Fase | Qué practica |
|---|---|---|---|
| 1 | El juego del OCIo | Regional 2018 | una secuencia donde cada término se define por el anterior |
| 2 | ⭐ Gollum vs Golomb | Nacional 2015 | una recurrencia de verdad — y por qué a veces conviene desenrollarla en un ciclo |
Los dos se definen igual que fib: en términos de sí mismos. Reconocer esa
forma es el músculo de este módulo; escribirla con recursión o con un ciclo
viene después.
Más aplicaciones (en inglés)
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | Tower of Hanoi (CSES 2165) | ★★ (—) | LA recursión clásica: mover, imprimir, confiar |
| 2 | New Year Transportation (500A) | ★★ (1000) | seguir saltos (recursivo o iterativo, tú eliges) |
| 3 | ⭐ Reto local: fib(50) con memoización | ★★★ | sin memo no termina nunca; con memo, instantáneo |
Un ejemplo para pensar
En fib_lento(4), tanto la rama que calcula fib_lento(3) como la otra
rama necesitan fib_lento(2). Si usamos memoización, ¿desaparece toda
llamada repetida o cambia el trabajo que hace esa llamada?
Recordar evita expandir otra vez el mismo subproblema
La primera llamada a
fib_rapido(2)calculafib(1) + fib(0) = 1y guarda el resultado. La siguiente llamada afib_rapido(2)sí ocurre, pero retorna el 1 guardado sin abrir esas dos ramas. Se reduce el trabajo porque cada estado guardado se desarrolla una sola vez; consultar un estado conocido sigue siendo una llamada.
El siguiente módulo introduce aritmética y algoritmos numéricos. La Ruta de Aprendizaje muestra cómo combinar estos fundamentos con los temas que corresponden a cada competencia.
← 08 - Búsqueda binaria · Ruta de Aprendizaje · 10 - Algoritmos numéricos y aritmética modular →