Funciones Recursivas

¿Qué es la recursión?

Imagina que estás en una fila para comprar boletos y quieres saber cuántas personas hay delante de ti. Le preguntas a la persona de enfrente: "¿Cuántas personas hay delante de ti?". Esa persona le pregunta lo mismo a la siguiente, y así sucesivamente. La primera persona de la fila dice "¡Ninguna!" (caso base), y la respuesta se va propagando de regreso: "Una", "Dos", "Tres"...

Eso es recursión: una función que se llama a sí misma para resolver un problema más pequeño, hasta llegar a un caso tan simple que se resuelve directamente.

Anatomía de una función recursiva

Toda función recursiva necesita dos cosas:

1. Caso base: La condición que detiene la recursión. Sin él, la función se llamaría infinitamente.
2. Caso recursivo: La función se llama a sí misma con un problema más pequeño.

void cuentaRegresiva(int n) {
    // Caso base
    if (n == 0) {
        cout << "¡Despegue!" << endl;
        return;
    }

    // Caso recursivo
    cout << n << "..." << endl;
    cuentaRegresiva(n - 1);  // Se llama con n-1 (problema más pequeño)
}

// cuentaRegresiva(3) imprime:
// 3...
// 2...
// 1...
// ¡Despegue!

El ejemplo clásico: factorial

El factorial de $n$ (escrito $n!$) es: $n! = n \times (n-1) \times (n-2) \times ... \times 2 \times 1$

Podemos definirlo recursivamente:

• Caso base: $0! = 1$
• Caso recursivo: $n! = n \times (n-1)!$

long long factorial(int n) {
    if (n == 0) return 1;        // Caso base
    return n * factorial(n - 1);  // Caso recursivo
}

¿Cómo funciona factorial(4)?

factorial(4) = 4 * factorial(3)
                   = 3 * factorial(2)
                          = 2 * factorial(1)
                                 = 1 * factorial(0)
                                        = 1          ← Caso base
                                 = 1 * 1 = 1
                          = 2 * 1 = 2
                   = 3 * 2 = 6
             = 4 * 6 = 24

Cada llamada "espera" a que la siguiente termine, y luego usa el resultado para calcular el suyo.

La pila de llamadas (Call Stack)

Cuando una función se llama a sí misma, la computadora guarda el estado de cada llamada en una pila (stack). Es como apilar platos: el último plato que pones es el primero que quitas.

factorial(4)  ← Esperando resultado de factorial(3)
  factorial(3)  ← Esperando resultado de factorial(2)
    factorial(2)  ← Esperando resultado de factorial(1)
      factorial(1)  ← Esperando resultado de factorial(0)
        factorial(0) → retorna 1  ← Caso base: se resuelve
      factorial(1) → retorna 1 * 1 = 1
    factorial(2) → retorna 2 * 1 = 2
  factorial(3) → retorna 3 * 2 = 6
factorial(4) → retorna 4 * 6 = 24

Más ejemplos de recursión

Fibonacci

La secuencia de Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Cada número es la suma de los dos anteriores.

int fibonacci(int n) {
    if (n <= 1) return n;              // Casos base: fib(0)=0, fib(1)=1
    return fibonacci(n-1) + fibonacci(n-2);  // Caso recursivo
}

Potencia

long long potencia(long long base, int exp) {
    if (exp == 0) return 1;
    return base * potencia(base, exp - 1);
}

Potencia rápida (exponenciación binaria)

Una versión mucho más eficiente: $O(\log n)$ en vez de $O(n)$.

long long potenciaRapida(long long base, int exp, long long mod) {
    if (exp == 0) return 1;
    long long half = potenciaRapida(base, exp / 2, mod);
    long long result = (half * half) % mod;
    if (exp % 2 == 1) {
        result = (result * base) % mod;
    }
    return result;
}

La idea: $2^{10} = (2^5)^2$ y $2^5 = 2 \times (2^2)^2$. Reducimos el exponente a la mitad en cada paso.

Suma de dígitos

int sumaDigitos(int n) {
    if (n < 10) return n;                  // Caso base: un solo dígito
    return (n % 10) + sumaDigitos(n / 10);  // Último dígito + suma del resto
}

// sumaDigitos(1234) = 4 + sumaDigitos(123)
//                   = 4 + 3 + sumaDigitos(12)
//                   = 4 + 3 + 2 + sumaDigitos(1)
//                   = 4 + 3 + 2 + 1 = 10

GCD (Algoritmo de Euclides recursivo)

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

Torres de Hanoi

Un rompecabezas clásico: mover N discos de la torre A a la C, usando B como auxiliar. Regla: nunca poner un disco grande sobre uno pequeño.

void hanoi(int n, char origen, char destino, char auxiliar) {
    if (n == 0) return;

    hanoi(n - 1, origen, auxiliar, destino);
    cout << "Mover disco " << n << " de " << origen << " a " << destino << endl;
    hanoi(n - 1, auxiliar, destino, origen);
}

// hanoi(3, 'A', 'C', 'B');

Recursión vs Iteración

Todo lo que se puede hacer con recursión se puede hacer con ciclos, y viceversa. La pregunta es: ¿cuál es más natural para el problema?

// Factorial iterativo
long long factorialIt(int n) {
    long long resultado = 1;
    for (int i = 2; i <= n; i++) {
        resultado *= i;
    }
    return resultado;
}

Errores comunes

1. Olvidar el caso base

// ❌ Sin caso base: recursión infinita → Stack Overflow
int malo(int n) {
    return n * malo(n - 1);  // Nunca para
}

2. Caso base que nunca se alcanza

// ❌ Si n es negativo, nunca llega a 0
int malo(int n) {
    if (n == 0) return 1;
    return n * malo(n - 1);  // ¿Qué pasa si n = -3?
}

// ✅ Manejar todos los casos
int bueno(int n) {
    if (n <= 0) return 1;
    return n * bueno(n - 1);
}

Ejercicio de práctica

Escribe una función recursiva que invierta un string.

Entrada: "hola" Salida: "aloh"

#include <iostream>
using namespace std;

string invertir(string s) {
    if (s.size() <= 1) return s;
    return invertir(s.substr(1)) + s[0];
}

// invertir("hola") = invertir("ola") + 'h'
//                  = (invertir("la") + 'o') + 'h'
//                  = ((invertir("a") + 'l') + 'o') + 'h'
//                  = (("a" + 'l') + 'o') + 'h'
//                  = "al" + 'o' + 'h'
//                  = "aloh"

int main() {
    string s;
    cin >> s;
    cout << invertir(s) << endl;
    return 0;
}

Siguiente paso

Aprende sobre Memorización para hacer la recursión mucho más eficiente evitando recalcular valores.