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):

baja: cada llamada espera a la siguientefactorial(4)necesita factorial(3)factorial(3)necesita factorial(2)factorial(2)necesita factorial(1)factorial(1)caso base: devuelve 1 sin llamar a nadiey devuelve, de abajo hacia arriba4 · 6 = 243 · 2 = 62 · 1 = 21cada una termina al recibir su valorcuatro llamadas “esperando” a la vez: eso es la pila; sin caso base, crecería para siempre

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):

f(5)f(4)f(3)f(3)f(2)f(2)f(1)f(2)f(1)f(1)f(0)f(1)f(0)f(1)f(0)ya calculado: memosin memo, 15 llamadas (los subárboles atenuados se recalculan); con memo, 9

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)

  1. potencia(b, e) recursiva (enteros; luego compárala con un ciclo).
  2. suma_digitos(n): 407 → 11, en tres líneas recursivas.
  3. 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.

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.

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):

#ProblemaFaseQué practica
1El juego del OCIoRegional 2018una secuencia donde cada término se define por el anterior
2⭐ Gollum vs GolombNacional 2015una 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)

#ProblemaDificultadQué practica
1Tower of Hanoi (CSES 2165)★★ (—)LA recursión clásica: mover, imprimir, confiar
2New 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?

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 →