Fundamentos

Recursión sin misticismo

Respuesta corta: una función recursiva resuelve un problema llamándose a sí misma sobre una versión más pequeña del mismo problema, y se detiene en un caso base lo bastante pequeño para responder directamente. Dos partes, siempre: caso base y paso recursivo.

Las dos partes

#include <iostream>
using namespace std;

long long factorial(int n) {
    if (n <= 1) return 1;        // caso base: responde directo
    return n * factorial(n - 1); // paso recursivo: problema menor
}

int main() {
    cout << factorial(5) << endl;   // 120
    return 0;
}

Quita el caso base y la función se llama para siempre hasta que el programa se queda sin pila. Ese fallo tiene nombre: desbordamiento de pila.

Qué pasa de verdad, paso a paso

La recursión no es magia — es una pila de llamadas pausadas. Cada llamada espera a la de abajo:

factorial(4)
  necesita 4 * factorial(3)
    necesita 3 * factorial(2)
      necesita 2 * factorial(1)
        factorial(1) devuelve 1        ← caso base alcanzado
      devuelve 2 * 1 = 2
    devuelve 3 * 2 = 6
  devuelve 4 * 6 = 24

La cadena se construye bajando y se despliega subiendo. Por eso el caso base debe ser alcanzable — si no, la cadena nunca empieza a desplegarse.

Recursión visible: cuenta atrás

#include <iostream>
using namespace std;

void cuenta(int n) {
    if (n == 0) {           // caso base
        cout << "despegue" << endl;
        return;
    }
    cout << n << " ";
    cuenta(n - 1);          // paso recursivo
}

int main() {
    cuenta(5);
    return 0;
}

La impresión ocurre antes de la llamada, así que los números salen descendentes. Mueve el cout después de la llamada y salen ascendentes — ese único reordenamiento es la diferencia entre «antes del descenso» y «después del retorno».

Cuándo la recursión es la herramienta natural

Siempre que el problema se defina en términos de sí mismo. Torres de Hanói es el ejemplo más limpio: mover n discos = apartar n−1, mover el grande, devolver n−1.

#include <iostream>
using namespace std;

void hanoi(int n, int desde, int hasta, int via) {
    if (n == 0) return;
    hanoi(n - 1, desde, via, hasta);
    cout << "mover " << n << " de " << desde << " a " << hasta << endl;
    hanoi(n - 1, via, hasta, desde);
}

int main() {
    hanoi(3, 1, 3, 2);
    return 0;
}

Síguelo a mano una vez. Fíjate en que no necesitas tener toda la secuencia en la cabeza para fiarte del código — solo necesitas creer que las dos llamadas menores funcionan. Ese es el movimiento mental que exige la recursión, y el problema Torres de Hanói lo entrena.

Recursión frente a bucle

Toda recursión puede reescribirse como un bucle con una pila explícita o un acumulador. Cuál usar:

Los costes

• Espacio de pila. Cada llamada pendiente ocupa un marco. Profundidad 1.000.000 revienta; profundidad 40 no es nada.
• Recálculo. El Fibonacci recursivo ingenuo se llama dos veces por nivel — unas 2^n llamadas. Fibonacci muestra el arreglo (llevar dos valores).
• El caso base debe ser alcanzable. Un paso que se salta la base (n -= 2 cuando la base comprueba n == 0) también desborda.

Preguntas de entrevista

1. ¿Qué es un desbordamiento de pila? Demasiadas llamadas anidadas; la pila de llamadas se queda sin espacio. Casi siempre un caso base ausente o inalcanzable.
2. ¿Cómo convertirías esta recursión en un bucle? Identifica el acumulador y la dirección; para recursión con forma de árbol necesitas una pila explícita.
3. ¿Por qué el Fibonacci ingenuo es exponencial? Porque recalcula los mismos subproblemas — el caso clásico de memoización o DP de abajo hacia arriba.

Practica: Torres de Hanói, Todas las permutaciones, Fibonacci. Lee después: pila frente a heap explica dónde viven realmente esas llamadas pausadas.