La recursividad en Java es una de las técnicas de programación más elegantes y, al mismo tiempo, más temidas por quienes se inician en el desarrollo de software. Su principio es engañosamente sencillo: un método que se invoca a sí mismo para resolver versiones cada vez más pequeñas de un mismo problema. Sin embargo, dominar la recursividad requiere comprender cómo funciona la pila de llamadas (call stack), cuándo aplicar esta técnica frente a la iteración convencional y qué patrones de diseño recursivo existen para problemas clásicos como el cálculo del factorial, la sucesión de Fibonacci o el recorrido de estructuras de datos jerárquicas.
En esta guía completa exploraremos la recursividad desde sus fundamentos teóricos hasta ejercicios resueltos de dificultad progresiva. Cada concepto se acompaña de código Java ejecutable con la salida esperada, tablas comparativas y notas de buena práctica que permitirán al lector aplicar la recursividad con confianza en proyectos reales.
🔄 ¿Qué es la recursividad?
En matemáticas y en informática, la recursividad (o recursión) es el proceso por el cual una entidad se define en términos de sí misma. Trasladado a la programación en Java, se dice que un método es recursivo cuando contiene una o más invocaciones a sí mismo dentro de su cuerpo.
El ejemplo más intuitivo proviene de las matemáticas. La función factorial se define recursivamente así:
- Caso base: 0! = 1
- Caso recursivo: n! = n × (n − 1)! para n > 0
Esta definición contiene los dos ingredientes que todo método recursivo necesita: una condición de parada (caso base) que devuelve un resultado directo sin más llamadas, y una llamada recursiva (caso recursivo) que reduce el problema hacia ese caso base. Si falta la condición de parada o la reducción no converge, el programa entra en una recursión infinita que agota la memoria de la pila y lanza un StackOverflowError.
🧬 Anatomía de un método recursivo
Todo método recursivo en Java se compone de tres partes bien diferenciadas que conviene identificar antes de escribir una sola línea de código:
| Parte | Función | Ejemplo (factorial) |
|---|---|---|
| Caso base | Detiene la recursión. Devuelve un valor conocido. | if (n == 0) return 1; |
| Caso recursivo | Invoca al propio método con un argumento más cercano al caso base. | return n * factorial(n - 1); |
| Progreso hacia el caso base | Garantiza que cada llamada reduce el tamaño del problema. | n - 1 se acerca a 0 |
Veamos cómo se traduce la definición matemática del factorial a un método Java completo:
public class Factorial {
/**
* Calcula el factorial de un número entero no negativo
* de forma recursiva.
*
* @param n número del que se desea obtener el factorial
* @return n!
*/
public static long factorial(int n) {
// Caso base
if (n == 0) {
return 1;
}
// Caso recursivo: n! = n × (n-1)!
return n * factorial(n - 1);
}
public static void main(String[] args) {
for (int i = 0; i <= 10; i++) {
System.out.println(i + "! = " + factorial(i));
}
}
}
// Salida esperada:
// 0! = 1
// 1! = 1
// 2! = 2
// 3! = 6
// 4! = 24
// 5! = 120
// 6! = 720
// 7! = 5040
// 8! = 40320
// 9! = 362880
// 10! = 3628800
long en lugar de int porque el factorial crece muy rápido. A partir de 13! el resultado supera el rango de int (2.147.483.647). Para valores mayores de 20! se necesitaría BigInteger.📚 La pila de llamadas y el flujo de ejecución
Para comprender realmente la recursividad, es imprescindible entender cómo la pila de llamadas (call stack) gestiona cada invocación. Cada vez que un método se llama a sí mismo, la JVM crea un nuevo marco de pila (stack frame) que almacena los parámetros locales, las variables y la dirección de retorno. Cuando el caso base se alcanza, los marcos se van resolviendo en orden inverso (LIFO: Last In, First Out).
Ilustremos el proceso con factorial(4):
Fase de AVANCE (apilando marcos):
──────────────────────────────────
factorial(4) → espera resultado de factorial(3)
factorial(3) → espera resultado de factorial(2)
factorial(2) → espera resultado de factorial(1)
factorial(1) → espera resultado de factorial(0)
factorial(0) → CASO BASE → devuelve 1
Fase de RETORNO (desapilando marcos):
─────────────────────────────────────
factorial(0) devuelve 1
factorial(1) devuelve 1 × 1 = 1
factorial(2) devuelve 2 × 1 = 2
factorial(3) devuelve 3 × 2 = 6
factorial(4) devuelve 4 × 6 = 24 ← RESULTADO FINAL
En total se crean cinco marcos de pila (de factorial(4) a factorial(0)). Para un valor n genérico, la profundidad será n + 1. Esto implica que la recursividad consume memoria proporcional a la profundidad de las llamadas, algo que debe tenerse muy en cuenta al diseñar soluciones recursivas.
java.lang.StackOverflowError. Si el problema lo requiere, se puede aumentar con la opción -Xss (por ejemplo, -Xss4m), aunque lo ideal es replantear el algoritmo.⭐ Ejemplos clásicos de recursividad
Existen varios problemas que se consideran canónicos para estudiar la recursividad. Cada uno ilustra un aspecto diferente de esta técnica.
🔹 Sucesión de Fibonacci
La sucesión de Fibonacci se define como: F(0) = 0, F(1) = 1, y para n ≥ 2, F(n) = F(n − 1) + F(n − 2). La implementación recursiva directa es muy clara pero enormemente ineficiente, como veremos en la sección de memoización.
public class Fibonacci {
/** Fibonacci recursivo puro (ineficiente para n grande). */
public static long fibonacci(int n) {
if (n <= 0) return 0; // Caso base 1
if (n == 1) return 1; // Caso base 2
return fibonacci(n - 1) + fibonacci(n - 2); // Caso recursivo
}
public static void main(String[] args) {
for (int i = 0; i <= 10; i++) {
System.out.print(fibonacci(i) + " ");
}
}
}
// Salida esperada:
// 0 1 1 2 3 5 8 13 21 34 55
fibonacci(40) se realizan más de mil millones de llamadas. En la sección de memoización veremos cómo reducir esto a O(n).🔹 Torres de Hanói
El problema de las Torres de Hanói consiste en mover n discos de una torre origen a una torre destino, usando una torre auxiliar, con la restricción de que nunca un disco grande puede quedar sobre uno más pequeño. La solución recursiva es extraordinariamente elegante: para mover n discos, primero se mueven los n − 1 superiores a la torre auxiliar, luego se mueve el disco mayor al destino, y finalmente se mueven los n − 1 discos de la auxiliar al destino.
public class TorresHanoi {
/**
* Mueve n discos desde la torre origen hasta la torre destino.
*
* @param n número de discos
* @param origen nombre de la torre origen
* @param destino nombre de la torre destino
* @param auxiliar nombre de la torre auxiliar
*/
public static void mover(int n, String origen, String destino, String auxiliar) {
if (n == 1) {
System.out.println("Mover disco 1 de " + origen + " a " + destino);
return;
}
// 1. Mover n-1 discos de origen a auxiliar, usando destino como puente
mover(n - 1, origen, auxiliar, destino);
// 2. Mover el disco mayor al destino
System.out.println("Mover disco " + n + " de " + origen + " a " + destino);
// 3. Mover n-1 discos de auxiliar a destino, usando origen como puente
mover(n - 1, auxiliar, destino, origen);
}
public static void main(String[] args) {
int discos = 3;
System.out.println("Solución para " + discos + " discos:");
mover(discos, "A", "C", "B");
}
}
// Salida esperada:
// Solución para 3 discos:
// Mover disco 1 de A a C
// Mover disco 2 de A a B
// Mover disco 1 de C a B
// Mover disco 3 de A a C
// Mover disco 1 de B a A
// Mover disco 2 de B a C
// Mover disco 1 de A a C
Las Torres de Hanói requieren exactamente 2n − 1 movimientos. Con 3 discos son 7 movimientos; con 10 discos, 1.023; con 64 discos (el número de la leyenda original), el número de movimientos supera los 18 trillones.
🔹 Búsqueda binaria recursiva
La búsqueda binaria es un algoritmo de tipo divide y vencerás que localiza un elemento en un array ordenado dividiendo repetidamente el rango de búsqueda a la mitad. Su naturaleza recursiva es directa:
public class BusquedaBinaria {
/**
* Busca un valor en un array ordenado de forma recursiva.
*
* @return índice del valor encontrado, o -1 si no existe
*/
public static int buscar(int[] array, int valor, int inicio, int fin) {
// Caso base: rango vacío
if (inicio > fin) {
return -1;
}
int medio = inicio + (fin - inicio) / 2;
if (array[medio] == valor) {
return medio; // Encontrado
} else if (valor < array[medio]) {
return buscar(array, valor, inicio, medio - 1); // Mitad izquierda
} else {
return buscar(array, valor, medio + 1, fin); // Mitad derecha
}
}
public static void main(String[] args) {
int[] datos = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int objetivo = 23;
int resultado = buscar(datos, objetivo, 0, datos.length - 1);
System.out.println("Elemento " + objetivo + " encontrado en índice: " + resultado);
}
}
// Salida esperada:
// Elemento 23 encontrado en índice: 5
🔀 Tipos de recursividad
No toda recursividad es igual. Según cómo se estructura la llamada recursiva, se distinguen varias categorías importantes:
| Tipo | Descripción | Ejemplo |
|---|---|---|
| Directa | El método se llama a sí mismo directamente. | factorial(n - 1) |
| Indirecta (mutua) | El método A llama al método B, que a su vez llama al método A. | Funciones esPar() / esImpar() |
| De cola (tail recursion) | La llamada recursiva es la última operación del método. Permite optimización por parte del compilador. | return factorial(n - 1, n * acc); |
| Múltiple | El método realiza dos o más llamadas recursivas en una misma invocación. | fibonacci(n-1) + fibonacci(n-2) |
| Anidada | El argumento de la llamada recursiva es otra llamada recursiva. | ackermann(m-1, ackermann(m, n-1)) |
▶️ Recursividad de cola con acumulador
La recursividad de cola (tail recursion) es una forma especial en la que la llamada recursiva es la última instrucción del método y su resultado se devuelve directamente, sin operaciones adicionales. Algunos compiladores y entornos pueden optimizar este patrón eliminando los marcos de pila innecesarios (aunque la JVM de Java no realiza esta optimización automáticamente, conocer el patrón sigue siendo valioso para escribir código más claro y para otros lenguajes de la JVM como Scala o Kotlin).
public class FactorialCola {
/** Versión con recursividad de cola usando acumulador. */
public static long factorial(int n, long acumulador) {
if (n == 0) {
return acumulador; // El acumulador contiene el resultado
}
return factorial(n - 1, n * acumulador); // Llamada de cola
}
/** Método envolvente para facilitar la llamada. */
public static long factorial(int n) {
return factorial(n, 1);
}
public static void main(String[] args) {
System.out.println("10! = " + factorial(10));
}
}
// Salida esperada:
// 10! = 3628800
▶️ Recursividad indirecta (mutua)
En la recursividad indirecta, dos o más métodos se invocan mutuamente. Un ejemplo clásico (aunque poco eficiente) es determinar si un número es par o impar:
public class ParidadRecursiva {
public static boolean esPar(int n) {
if (n == 0) return true;
return esImpar(n - 1);
}
public static boolean esImpar(int n) {
if (n == 0) return false;
return esPar(n - 1);
}
public static void main(String[] args) {
System.out.println("4 es par: " + esPar(4)); // true
System.out.println("7 es par: " + esPar(7)); // false
}
}
// Salida esperada:
// 4 es par: true
// 7 es par: false
⚖️ Recursividad frente a iteración
Todo algoritmo recursivo puede reescribirse de forma iterativa y viceversa. La elección entre una u otra depende del problema concreto, la legibilidad del código y los requisitos de rendimiento.
| Criterio | Recursividad | Iteración |
|---|---|---|
| Legibilidad | Más clara para problemas con estructura recursiva natural (árboles, grafos). | Más clara para recorridos lineales simples. |
| Memoria | Consume memoria en la pila proporcional a la profundidad de recursión. | Generalmente usa memoria constante O(1). |
| Velocidad | Overhead por la creación y destrucción de marcos de pila. | Generalmente más rápida por menor overhead. |
| Riesgo de desbordamiento | Sí, con StackOverflowError si la profundidad es excesiva. |
No aplica (usa el heap para datos). |
| Problemas ideales | Divide y vencerás, backtracking, estructuras jerárquicas. | Recorridos secuenciales, acumulaciones simples. |
for o while será más eficiente y legible.Veamos la misma tarea — sumar los dígitos de un número — resuelta de ambas formas:
public class SumaDigitos {
// --- Versión RECURSIVA ---
public static int sumaRecursiva(int n) {
if (n == 0) return 0;
return (n % 10) + sumaRecursiva(n / 10);
}
// --- Versión ITERATIVA ---
public static int sumaIterativa(int n) {
int suma = 0;
while (n > 0) {
suma += n % 10;
n /= 10;
}
return suma;
}
public static void main(String[] args) {
int numero = 9473;
System.out.println("Suma recursiva de dígitos de " + numero + ": " + sumaRecursiva(numero));
System.out.println("Suma iterativa de dígitos de " + numero + ": " + sumaIterativa(numero));
}
}
// Salida esperada:
// Suma recursiva de dígitos de 9473: 23
// Suma iterativa de dígitos de 9473: 23
🧠 Memoización: optimizar la recursividad
La memoización (memoization) es una técnica de optimización que almacena los resultados de las llamadas recursivas ya calculadas para evitar repetir cómputos innecesarios. Es especialmente poderosa en problemas con subproblemas solapados, donde la misma llamada recursiva se repite muchas veces.
El caso más ilustrativo es Fibonacci. Sin memoización, fibonacci(5) genera el siguiente árbol de llamadas:
fib(5)
/ \
fib(4) fib(3) ← fib(3) se calcula 2 veces
/ \ / \
fib(3) fib(2) fib(2) fib(1) ← fib(2) se calcula 3 veces
/ \
fib(2) fib(1)
/ \
fib(1) fib(0)
Con memoización, cada valor se calcula solo una vez y se almacena en una estructura de datos (un array o un HashMap). El resultado: complejidad O(n) en tiempo y O(n) en espacio.
import java.util.HashMap;
import java.util.Map;
public class FibonacciMemo {
private static Map<Integer, Long> cache = new HashMap<>();
public static long fibonacci(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
// Si ya se calculó, devolver el valor almacenado
if (cache.containsKey(n)) {
return cache.get(n);
}
// Calcular, almacenar y devolver
long resultado = fibonacci(n - 1) + fibonacci(n - 2);
cache.put(n, resultado);
return resultado;
}
public static void main(String[] args) {
System.out.println("fibonacci(10) = " + fibonacci(10));
System.out.println("fibonacci(40) = " + fibonacci(40));
System.out.println("fibonacci(50) = " + fibonacci(50));
}
}
// Salida esperada:
// fibonacci(10) = 55
// fibonacci(40) = 102334155
// fibonacci(50) = 12586269025
fibonacci(50) requeriría más de 1013 llamadas recursivas. Con memoización, solo se necesitan 50 cálculos únicos. La diferencia entre minutos de ejecución y microsegundos.🏗️ Ejemplo integrador: explorador recursivo de directorios
Uno de los usos más prácticos de la recursividad en aplicaciones reales es el recorrido de estructuras jerárquicas. Un sistema de archivos (carpetas que contienen subcarpetas que contienen subcarpetas...) es inherentemente recursivo. El siguiente programa recorre un directorio completo mostrando su estructura con indentación, y calcula estadísticas como el número total de archivos y el tamaño acumulado.
import java.io.File;
public class ExploradorDirectorios {
private int totalArchivos = 0;
private int totalCarpetas = 0;
private long tamanoTotal = 0;
/**
* Recorre recursivamente un directorio e imprime su estructura.
*
* @param directorio carpeta a explorar
* @param nivel profundidad actual (para indentación)
*/
public void explorar(File directorio, int nivel) {
if (!directorio.isDirectory()) {
System.out.println("Error: " + directorio.getPath() + " no es un directorio.");
return;
}
String indentacion = " ".repeat(nivel);
File[] contenido = directorio.listFiles();
if (contenido == null) return; // Sin permisos
for (File elemento : contenido) {
if (elemento.isDirectory()) {
totalCarpetas++;
System.out.println(indentacion + "📁 " + elemento.getName() + "/");
explorar(elemento, nivel + 1); // LLAMADA RECURSIVA
} else {
totalArchivos++;
tamanoTotal += elemento.length();
System.out.println(indentacion + "📄 " + elemento.getName()
+ " (" + elemento.length() + " bytes)");
}
}
}
public void mostrarEstadisticas() {
System.out.println("\n--- Estadísticas ---");
System.out.println("Carpetas: " + totalCarpetas);
System.out.println("Archivos: " + totalArchivos);
System.out.printf("Tamaño: %.2f KB%n", tamanoTotal / 1024.0);
}
public static void main(String[] args) {
String ruta = args.length > 0 ? args[0] : ".";
File raiz = new File(ruta);
ExploradorDirectorios explorador = new ExploradorDirectorios();
System.out.println("📁 " + raiz.getAbsolutePath() + "/");
explorador.explorar(raiz, 1);
explorador.mostrarEstadisticas();
}
}
// Ejemplo de salida (variará según el directorio):
// 📁 /home/usuario/proyecto/
// 📁 src/
// 📄 Main.java (2048 bytes)
// 📄 Utils.java (1536 bytes)
// 📁 docs/
// 📄 README.md (512 bytes)
// 📄 build.xml (768 bytes)
//
// --- Estadísticas ---
// Carpetas: 2
// Archivos: 4
// Tamaño: 4.75 KB
Este ejemplo ilustra perfectamente por qué la recursividad brilla en problemas jerárquicos: el código para procesar un nivel es idéntico al de cualquier otro nivel, y la profundidad real de la estructura de directorios queda gestionada automáticamente por la pila de llamadas.
🚫 Errores frecuentes con recursividad
A continuación se documentan los errores más habituales al trabajar con recursividad en Java, junto con sus causas y soluciones.
🔹 Error 1: Falta de caso base
// Sin caso base: recursión infinita → StackOverflowError
public static int factorial(int n) {
return n * factorial(n - 1); // ¿Cuándo se detiene?
}
public static int factorial(int n) {
if (n == 0) return 1; // Caso base explícito
return n * factorial(n - 1);
}
🔹 Error 2: El caso recursivo no progresa hacia el caso base
// n nunca se reduce: recursión infinita
public static int cuenta(int n) {
if (n == 0) return 0;
return 1 + cuenta(n); // ¡Debería ser cuenta(n - 1)!
}
🔹 Error 3: No considerar argumentos negativos
public static long factorial(int n) {
if (n < 0) {
throw new IllegalArgumentException("n debe ser >= 0, recibido: " + n);
}
if (n == 0) return 1;
return n * factorial(n - 1);
}
factorial(-3) sin validación, la recursión nunca alcanzará el caso base n == 0 y se producirá un StackOverflowError.✏️ Ejercicios resueltos
Pon a prueba lo aprendido con estos ejercicios de dificultad progresiva. Intenta resolverlos antes de consultar la solución.
Ejercicio 1: Potencia recursiva
Escribe un método recursivo potencia(int base, int exponente) que calcule baseexponente sin usar Math.pow(). Considera que el exponente es siempre ≥ 0.
Ejercicio 2: Invertir una cadena recursivamente
Escribe un método recursivo invertir(String cadena) que devuelva la cadena invertida. Por ejemplo, invertir("Java") debe devolver "avaJ".
Ejercicio 3: Máximo común divisor (MCD) por el algoritmo de Euclides
Implementa recursivamente el algoritmo de Euclides para calcular el máximo común divisor de dos enteros positivos: mcd(a, b) = mcd(b, a % b) con caso base mcd(a, 0) = a.
❓ Preguntas frecuentes sobre Recursividad en Java
Las dudas más comunes respondidas de forma clara y directa.
💬 Foro de discusión
¿Tienes dudas sobre Recursividad en Java? Comparte tu pregunta con la comunidad.
Todavía no hay mensajes. ¡Sé el primero en participar!