Introducción a la recursión, qué es y para qué se usa

La recursión es una técnica de programación donde una función se llama a sí misma para resolver un problema.

Esta técnica se fundamenta en el principio de "divide y vencerás", donde un problema complejo se descompone en instancias más simples del mismo tipo, hasta llegar a casos tan sencillos que se pueden resolver de manera directa.

En Java, la recursión sirve para resolver problemas que por su naturaleza tienen una estructura repetitiva o anidada. Un método recursivo es aquel que contiene al menos una llamada a sí mismo en su implementación.

Las funciones recursivas se usan mucho para:

• Recorrer estructuras jerárquicas como árboles o grafos
• Implementar algoritmos de ordenamiento eficientes (QuickSort, MergeSort)
• Resolver problemas matemáticos como el cálculo de factoriales o la secuencia de Fibonacci
• Implementar soluciones para problemas de backtracking (laberintos, sudoku)
• Procesar estructuras de datos recursivas (listas enlazadas, árboles binarios)

Un ejemplo puede ser el cálculo del factorial de un número. El factorial de n (denotado como n!) es el producto de todos los enteros positivos desde 1 hasta n.

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

Este ejemplo muestra la esencia de la recursión: para calcular el factorial de n, multiplicamos n por el factorial de (n-1). La función se llama a sí misma con un valor menor, acercándose gradualmente al caso base.

Cuando invocamos factorial(5), el proceso de cálculo se desarrolla de la siguiente manera: 1. factorial(5) = 5 * factorial(4) = 5 * 24 = 120

2. factorial(4) = 4 * factorial(3) = 4 * 6 = 24

3. factorial(3) = 3 * factorial(2) = 3 * 2 = 6

4. factorial(2) = 2 * factorial(1) = 2 * 1 = 2

5. factorial(1) = 1 (caso base)

La recursión puede presentar problemas como el consumo de memoria o desbordamientos de pila (stack overflow) si la profundidad de la recursión es excesiva.

Elementos de la recursión: condición base, caso recursivo, funcionamiento de la pila de llamadas (stack)

Toda función recursiva debe contar con ciertos elementos para funcionar correctamente y evitar problemas como la recursión infinita. Estos componentes esenciales son:

La condición base (o caso base) es el escenario en el que la recursión debe detenerse. Representa la solución directa para el caso más simple del problema, sin necesidad de realizar más llamadas recursivas. Sin una condición base adecuada, la función se llamaría a sí misma indefinidamente hasta producir un error de desbordamiento de pila (StackOverflowError).

Por ejemplo, en el cálculo del factorial:

public static int factorial(int n) {
    // Condición base
    if (n == 0 || n == 1) {
        return 1;
    }
    
    // Caso recursivo
    return n * factorial(n - 1);
}

La condición base ocurre cuando n es 0 o 1, donde sabemos que el factorial es 1.

El caso recursivo define cómo se descompone el problema original en subproblemas más pequeños. Es la parte donde la función se llama a sí misma con parámetros modificados que se acercan progresivamente hacia la condición base. Es muy importante que cada llamada recursiva aproxime el problema al caso base; de lo contrario, se produciría recursión infinita.

En el ejemplo del factorial, el caso recursivo es:

return n * factorial(n - 1);

Esta expresión indica que para calcular el factorial de n, multiplicamos n por el factorial de (n-1), reduciendo así el tamaño del problema en cada llamada.

El funcionamiento de la pila de llamadas (stack) es fundamental para entender la mecánica interna de la recursión. Cada vez que se invoca un método en Java, se crea un nuevo marco de pila (stack frame) que contiene:

• Los parámetros recibidos
• Las variables locales declaradas dentro del método
• La dirección de retorno (dónde continuar la ejecución después de completar la llamada)

Veamos cómo funciona la pila de llamadas al calcular factorial(3):

1. Se invoca factorial(3)

• Se crea un marco de pila para factorial(3)
• Como 3 no es caso base, calculamos 3 * factorial(2)
• Para obtener factorial(2), es necesaria otra llamada recursiva

2. Se invoca factorial(2)

• Se crea un marco de pila para factorial(2) encima del anterior
• Como 2 no es caso base, calculamos 2 * factorial(1)
• Para obtener factorial(1), hacemos otra llamada recursiva

3. Se invoca factorial(1)

• Se crea un marco de pila para factorial(1) encima de los anteriores
• Como 1 es un caso base, devolvemos 1 directamente
• El marco de pila de factorial(1) se elimina

4. Retornamos a factorial(2)

• Ahora sabemos que factorial(1) = 1
• Calculamos 2 * 1 = 2
• Devolvemos 2
• El marco de pila de factorial(2) se elimina

5. Retornamos a factorial(3)

• Ahora sabemos que factorial(2) = 2
• Calculamos 3 * 2 = 6
• Devolvemos 6
• El marco de pila de factorial(3) se elimina

El resultado final es 6.

Para visualizar mejor el proceso, se puede ver este ejemplo con salidas de depuración:

public static int factorial(int n) {
    System.out.println("Entrando a factorial(" + n + ")");
    
    int resultado;
    if (n == 0 || n == 1) {
        resultado = 1;
        System.out.println("Caso base: factorial(" + n + ") = " + resultado);
    } else {
        resultado = n * factorial(n - 1);
        System.out.println("factorial(" + n + ") = " + n + " * factorial(" + (n-1) + ") = " + resultado);
    }
    
    System.out.println("Saliendo de factorial(" + n + ")");
    return resultado;
}

Al ejecutar factorial(4), veríamos:

Entrando a factorial(4)
Entrando a factorial(3)
Entrando a factorial(2)
Entrando a factorial(1)
Caso base: factorial(1) = 1
Saliendo de factorial(1)
factorial(2) = 2 * factorial(1) = 2
Saliendo de factorial(2)
factorial(3) = 3 * factorial(2) = 6
Saliendo de factorial(3)
factorial(4) = 4 * factorial(3) = 24
Saliendo de factorial(4)

Esta visualización muestra cómo se construye la pila (fase descendente) y luego se desmonta (fase ascendente) a medida que se resuelven los subproblemas.

Cada marco de pila consume memoria, lo que explica por qué la recursión profunda puede provocar un StackOverflowError si se alcanza el límite de la pila de llamadas, que varía según la configuración de la JVM.

Recursión directa e indirecta

La recursión puede ser de distintas formas dependiendo de cómo se realizan las llamadas entre funciones. Las dos variantes principales son la recursión directa y la recursión indirecta.

La recursión directa es el tipo más común y ocurre cuando un método se llama explícitamente a sí mismo dentro de su cuerpo.

public static int contarRegresivo(int n) {
    // Caso base
    if (n <= 0) {
        return 0;
    }
    
    System.out.println(n);
    // Llamada recursiva directa
    return contarRegresivo(n - 1);
}

En este ejemplo, el método contarRegresivo se llama directamente a sí mismo con un valor decreciente, creando una simple cuenta regresiva.

La recursión indirecta (o recursión mutua) se produce cuando un método A llama a un método B, que a su vez llama al método A, formando un ciclo de llamadas. Esta forma de recursión puede involucrar dos o más métodos que se invocan entre sí.

public static boolean esImpar(int n) {
    if (n == 0) {
        return false;  // 0 no es impar
    }
    return esPar(n - 1);
}

public static boolean esPar(int n) {
    if (n == 0) {
        return true;  // 0 es par
    }
    return esImpar(n - 1);
}

En este ejemplo, esImpar llama a esPar, y esPar llama a esImpar, creando un ciclo recursivo indirecto:

1. esImpar(5) llama a esPar(4)

2. esPar(4) llama a esImpar(3)

3. esImpar(3) llama a esPar(2)

4. esPar(2) llama a esImpar(1)

5. esImpar(1) llama a esPar(0)

6. esPar(0) devuelve true (caso base)

7. Cada llamada se resuelve en sentido inverso, determinando que esImpar(5) es true

La recursión indirecta se usa para problemas con una naturaleza alternante o para implementar algoritmos complejos que se dividen naturalmente en subproblemas complementarios.

Un ejemplo práctico de recursión indirecta es el procesamiento de una estructura de árbol con diferentes tipos de nodos:

public void procesarNodoOperador(NodoOperador nodo) {
    // Procesar este nodo operador
    System.out.println("Procesando operador: " + nodo.getOperador());
    
    for (Nodo hijo : nodo.getHijos()) {
        if (hijo instanceof NodoValor) {
            procesarNodoValor((NodoValor) hijo);
        } else if (hijo instanceof NodoOperador) {
            procesarNodoOperador((NodoOperador) hijo);
        }
    }
}

public void procesarNodoValor(NodoValor nodo) {
    // Procesar este nodo valor
    System.out.println("Procesando valor: " + nodo.getValor());
    
    if (nodo.tieneOperadorAnidado()) {
        procesarNodoOperador(nodo.getOperadorAnidado());
    }
}

En este ejemplo, procesarNodoOperador puede llamar a procesarNodoValor y viceversa, dependiendo de la estructura del árbol que se está procesando.

Tanto la recursión directa como la indirecta comparten consideraciones importantes:

• Control de la profundidad: Es crucial asegurar que ambas formas de recursión converjan hacia casos base definidos para evitar desbordamientos de pila.
• Rendimiento: En escenarios con recursión múltiple, como en el cálculo de Fibonacci, pueden producirse cálculos redundantes que afecten al rendimiento:

// Implementación con cálculos redundantes
public static int fibonacciIneficiente(int n) {
    if (n <= 1) return n;
    return fibonacciIneficiente(n-1) + fibonacciIneficiente(n-2);
}

Para mejorar estos casos, se pueden aplicar técnicas de optimización como la memoización, que almacena resultados previamente calculados:

public static int fibonacciOptimizado(int n, Map<Integer, Integer> memo) {
    if (memo.containsKey(n)) return memo.get(n);
    if (n <= 1) return n;
    
    int resultado = fibonacciOptimizado(n-1, memo) + fibonacciOptimizado(n-2, memo);
    memo.put(n, resultado);
    return resultado;
}

// Uso
public static void main(String[] args) {
    Map<Integer, Integer> memoria = new HashMap<>();
    System.out.println(fibonacciOptimizado(40, memoria));
}

La memoización reduce drásticamente la complejidad temporal de O(2^n) a O(n), almacenando y reutilizando resultados intermedios.

Recursión de cola: tail recursion

La recursión de cola (tail recursion) es una forma especial de recursión donde la llamada recursiva es la última operación que se ejecuta en el método. La característica distintiva es que no quedan operaciones pendientes después de la llamada recursiva y el método simplemente devuelve el resultado de la llamada recursiva sin realizar cálculos adicionales con él.

Una función se considera recursiva de cola cuando cumple estos criterios:

• La llamada recursiva es la última instrucción ejecutada
• No hay operaciones pendientes tras la llamada recursiva
• El valor devuelto por la llamada recursiva se retorna directamente, sin modificaciones

Si se compara la recursión tradicional con la recursión de cola:

Factorial con recursión tradicional:

// No es recursión de cola
public static int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    // Después de la llamada recursiva, hay que multiplicar por n
    return n * factorial(n - 1);
}

En este caso, después de que factorial(n-1) devuelve su resultado, todavía debemos multiplicarlo por n. Esta operación pendiente hace que no sea una recursión de cola.

Factorial con recursión de cola:

public static int factorialCola(int n) {
    return factorialAuxiliar(n, 1);
}

private static int factorialAuxiliar(int n, int acumulador) {
    if (n == 0 || n == 1) {
        return acumulador;
    }
    // La llamada recursiva es la última operación
    return factorialAuxiliar(n - 1, n * acumulador);
}

En esta implementación, utilizamos un parámetro adicional acumulador que va almacenando el resultado parcial. La función factorialAuxiliar es recursiva de cola porque la última operación es exactamente la llamada recursiva, y su resultado se devuelve directamente sin cálculos posteriores.

La principal ventaja de la recursión de cola es la posibilidad de optimización por parte del compilador. En muchos lenguajes funcionales, los compiladores pueden transformar automáticamente la recursión de cola en un bucle iterativo equivalente, eliminando la sobrecarga de la pila de llamadas. Esto se conoce como "eliminación de la recursión de cola" (tail call elimination).

Es importante señalar que Java no implementa nativamente la optimización de recursión de cola. El compilador de Java no realiza la eliminación de la recursión de cola, por lo que incluso una función recursiva de cola seguirá consumiendo espacio en la pila para cada llamada recursiva.

Veamos cómo transformar manualmente una recursión de cola a una versión iterativa:

// Versión iterativa derivada de la recursión de cola
public static int factorialIterativo(int n) {
    int resultado = 1; // El acumulador inicial
    for (int i = n; i > 0; i--) {
        resultado = resultado * i;
    }
    return resultado;
}

Esta transformación es relativamente directa porque en la recursión de cola, el estado se pasa explícitamente como parámetros, lo que facilita su conversión a variables locales en un bucle.

Otros ejemplos de recursión de cola:

Cálculo de Fibonacci con recursión de cola:

public static long fibonacci(int n) {
    return fibonacciAuxiliar(n, 0, 1);
}

private static long fibonacciAuxiliar(int n, long a, long b) {
    if (n == 0) return a;
    return fibonacciAuxiliar(n - 1, b, a + b);
}

Esta implementación evita los cálculos redundantes de la versión recursiva tradicional y no sufre problemas de desbordamiento de pila incluso para valores grandes de n (dentro de los límites del tipo long).

Búsqueda binaria con recursión de cola:

public static int busquedaBinaria(int[] array, int valor) {
    return busquedaBinariaAuxiliar(array, valor, 0, array.length - 1);
}

private static int busquedaBinariaAuxiliar(int[] array, int valor, int inicio, int fin) {
    if (inicio > fin) {
        return -1; // No encontrado
    }
    
    int medio = inicio + (fin - inicio) / 2;
    
    if (array[medio] == valor) {
        return medio; // Encontrado
    } else if (array[medio] > valor) {
        return busquedaBinariaAuxiliar(array, valor, inicio, medio - 1);
    } else {
        return busquedaBinariaAuxiliar(array, valor, medio + 1, fin);
    }
}

Para convertir una función recursiva normal a recursión de cola, generalmente se sigue este patrón:

1. Crear una función auxiliar con parámetros adicionales (acumuladores) para llevar el estado.

2. La función original llama a la función auxiliar con los valores iniciales para los acumuladores.

3. La función auxiliar implementa la recursión de cola, pasando los resultados intermedios en los acumuladores.