Recursividad explicada desde cero: cómo pensar una función recursiva y 8 ejercicios resueltos en Java y Python

Publicado el 12/11/2026 por Equipo CodeMe Academy

Una función recursiva es una función que se llama a sí misma para resolver una versión más pequeña del mismo problema. Para que funcione necesita dos partes: un caso base, que se resuelve directamente sin volver a llamarse, y un caso recursivo, que reduce el problema y confía en que la llamada a sí misma resuelva el resto. Si falta el caso base o el caso recursivo no se acerca a él, la función se llama sin fin hasta que el programa revienta con un StackOverflowError en Java o un RecursionError en Python.

La recursividad aparece en Programación de primero de DAM y DAW, en Fundamentos de Programación y Estructuras de Datos en la universidad, y en cualquier ejercicio de árboles. Es el tema en el que más alumnos nos dicen "entiendo la solución pero no sabría hacerla". El problema casi nunca es la sintaxis: es intentar seguir mentalmente todas las llamadas a la vez. Aquí tienes cómo se ejecuta de verdad, un método de tres preguntas para escribir cualquier función recursiva y ocho ejercicios de examen resueltos, de menos a más difíciles.

Cómo se ejecuta una función recursiva

Cada vez que llamas a una función, el programa guarda en la pila de llamadas (call stack) un bloque con sus parámetros y sus variables locales. Cuando la función termina, ese bloque se quita y el programa sigue justo donde se hizo la llamada. Con la recursividad pasa exactamente lo mismo: cada llamada tiene su propio n, aunque se llame igual.

static long factorial(int n) {
    if (n <= 1) {
        return 1;                  // caso base
    }
    return n * factorial(n - 1);   // caso recursivo
}

Así se ejecuta factorial(4):

Paso	Pila (la llamada de arriba es la activa)	Qué pasa
1	`factorial(4)`	4 no es ≤ 1, necesita `factorial(3)` y espera
2	`factorial(3)` / `factorial(4)`	necesita `factorial(2)` y espera
3	`factorial(2)` / `factorial(3)` / `factorial(4)`	necesita `factorial(1)` y espera
4	`factorial(1)` / ...	caso base: devuelve `1`
5	`factorial(2)` / ...	recibe 1, devuelve `2 * 1 = 2`
6	`factorial(3)` / `factorial(4)`	recibe 2, devuelve `3 * 2 = 6`
7	`factorial(4)`	recibe 6, devuelve `4 * 6 = 24`

La recursividad tiene dos fases: la ida, en la que se van apilando llamadas sin calcular nada, y la vuelta, en la que cada llamada termina su multiplicación con el resultado de la de arriba. Saber en qué fase ocurre cada instrucción es lo que resuelve las preguntas de "¿qué imprime?".

La pregunta de "¿qué imprime?" que siempre cae

static void f(int n) {
    if (n == 0) {
        return;
    }
    System.out.print(n + " ");
    f(n - 1);
    System.out.print(n + " ");
}

f(3) imprime 3 2 1 1 2 3. El primer print está antes de la llamada, así que se ejecuta en la ida (3, 2, 1). El segundo está después, así que se ejecuta en la vuelta, cuando cada llamada recupera el control, en orden inverso (1, 2, 3).

Si mueves todo el código antes de la llamada, el orden es el natural. Si lo mueves después, sale al revés. Así se imprime un número al revés, se recorre una lista desde el final o se recorre un árbol en postorden.

El método de las tres preguntas

Para escribir una función recursiva no intentes seguir todas las llamadas en la cabeza. Responde estas tres preguntas en papel, por este orden:

¿Cuál es el caso más pequeño, y qué devuelvo en él? Una cadena vacía, un número de una cifra, un array de un elemento, n == 0. Ese es el caso base.
Si alguien me diera resuelto el problema un poco más pequeño, ¿cómo lo uso para resolver el mío? Aquí está el truco: confía en que la llamada recursiva funciona. Si tienes la suma de los dígitos de 1234 / 10 = 123, para tener la de 1234 solo te falta sumar 1234 % 10 = 4.
¿Cada llamada se acerca de verdad al caso base? Si el caso base es n == 0 y llamas con n - 2, un n impar se lo salta y se pasa a los negativos.

Los ocho ejercicios de abajo están resueltos aplicando siempre esas tres preguntas.

Ejercicio 1: suma de los dígitos de un número

Enunciado. Escribe una función recursiva que devuelva la suma de los dígitos de un número entero no negativo. sumaDigitos(1234) debe devolver 10.

Caso base: si el número tiene una cifra (n < 10), la suma es el propio número.
Caso recursivo: la última cifra es n % 10, y el resto del número es n / 10.
n / 10 siempre tiene una cifra menos, así que llega a n < 10.

static int sumaDigitos(int n) {
    if (n < 10) {
        return n;
    }
    return n % 10 + sumaDigitos(n / 10);
}

def suma_digitos(n):
    if n < 10:
        return n
    return n % 10 + suma_digitos(n // 10)

En Python se usa // para la división entera. Con / el resultado es un decimal y la función no termina nunca de forma correcta.

Ejercicio 2: potencia rápida

Enunciado. Calcula base elevado a exp (entero no negativo) de forma recursiva, haciendo menos de exp multiplicaciones.

La versión directa (base * potencia(base, exp - 1)) hace exp llamadas. Pero si sabes cuánto vale base^(exp/2), basta con elevarlo al cuadrado: 2^10 = (2^5)^2.

static double potencia(double base, int exp) {
    if (exp == 0) {
        return 1;
    }
    double mitad = potencia(base, exp / 2);
    if (exp % 2 == 0) {
        return mitad * mitad;
    }
    return mitad * mitad * base;
}

potencia(2, 10) llama a potencia(2, 5), potencia(2, 2), potencia(2, 1) y potencia(2, 0): cinco llamadas en vez de once. El número de llamadas crece con el logaritmo de exp, es decir, la función es O(log n).

El error típico. Escribir return potencia(base, exp / 2) * potencia(base, exp / 2);. Da el resultado correcto, pero hace dos llamadas en cada paso y vuelve a ser O(n). Guarda el resultado en una variable y úsalo dos veces.

Ejercicio 3: invertir una cadena

Enunciado. Devuelve la cadena al revés usando recursividad. invertir("hola") devuelve "aloh".

Caso base: una cadena vacía o de un carácter ya está invertida.
Caso recursivo: invierte todo menos el primer carácter y pon el primer carácter al final.
s.substring(1) es un carácter más corta en cada llamada.

static String invertir(String s) {
    if (s.length() <= 1) {
        return s;
    }
    return invertir(s.substring(1)) + s.charAt(0);
}

def invertir(s):
    if len(s) <= 1:
        return s
    return invertir(s[1:]) + s[0]

Ejercicio 4: palíndromo con índices

Enunciado. Di si una cadena es un palíndromo de forma recursiva, sin crear subcadenas nuevas en cada llamada.

En vez de recortar la cadena, se pasan dos índices que avanzan desde los extremos. Es un patrón que se usa mucho en el examen: una función "pública" con la firma sencilla que llama a una auxiliar con parámetros extra.

static boolean esPalindromo(String s) {
    return esPalindromo(s, 0, s.length() - 1);
}

private static boolean esPalindromo(String s, int i, int j) {
    if (i >= j) {
        return true;                       // 0 o 1 caracteres en medio
    }
    if (s.charAt(i) != s.charAt(j)) {
        return false;
    }
    return esPalindromo(s, i + 1, j - 1);
}

Aquí hay dos casos base: cuando los índices se cruzan (sí es palíndromo) y cuando los extremos son distintos (no lo es). Es muy habitual: el caso base no es solo "el problema más pequeño", también puede ser "ya sé la respuesta sin seguir".

Ejercicio 5: máximo de un array

Enunciado. Devuelve el mayor elemento de un array de enteros no vacío usando recursividad.

static int maximo(int[] v) {
    return maximo(v, v.length);
}

// Máximo de las n primeras posiciones del array
private static int maximo(int[] v, int n) {
    if (n == 1) {
        return v[0];
    }
    return Math.max(v[n - 1], maximo(v, n - 1));
}

La clave es definir bien qué significa el parámetro extra. Aquí n significa "cuántos elementos miro, empezando por el principio". Escríbelo en un comentario: la mitad de los fallos de recursividad con arrays son por no tener claro si un índice es inclusivo o exclusivo.

Ejercicio 6: búsqueda binaria

Enunciado. Busca un valor en un array ordenado y devuelve su posición, o -1 si no está.

static int buscar(int[] v, int x) {
    return buscar(v, x, 0, v.length - 1);
}

private static int buscar(int[] v, int x, int ini, int fin) {
    if (ini > fin) {
        return -1;                     // el tramo está vacío: no está
    }
    int medio = (ini + fin) / 2;
    if (v[medio] == x) {
        return medio;
    }
    if (x < v[medio]) {
        return buscar(v, x, ini, medio - 1);
    }
    return buscar(v, x, medio + 1, fin);
}

def buscar(v, x, ini=0, fin=None):
    if fin is None:
        fin = len(v) - 1
    if ini > fin:
        return -1
    medio = (ini + fin) // 2
    if v[medio] == x:
        return medio
    if x < v[medio]:
        return buscar(v, x, ini, medio - 1)
    return buscar(v, x, medio + 1, fin)

Cada llamada descarta la mitad del array, así que con un millón de elementos basta con unas veinte llamadas. Es O(log n).

El error típico. Llamar con medio en vez de medio - 1 o medio + 1. Cuando el tramo tiene dos elementos, medio puede no cambiar nunca y la función se llama a sí misma sin fin.

Ejercicio 7: Fibonacci, y por qué la versión directa es lentísima

Enunciado. Calcula el término n de la sucesión de Fibonacci (0, 1, 1, 2, 3, 5, 8...), donde cada término es la suma de los dos anteriores.

static long fib(int n) {
    if (n < 2) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

Es correcta, pero muy lenta: fib(40) ya se nota, en Python tarda decenas de segundos, y fib(50) puede tardar minutos incluso en Java. El motivo es que cada llamada hace dos llamadas, y se repite el mismo trabajo una y otra vez: fib(5) calcula fib(3) dos veces y fib(2) tres veces. Para fib(40) se hacen más de 300 millones de llamadas. El coste crece de forma exponencial.

La solución es memorización: guardar cada resultado la primera vez que se calcula y reutilizarlo.

static long fib(int n, long[] memo) {
    if (n < 2) {
        return n;
    }
    if (memo[n] != 0) {
        return memo[n];
    }
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

// Uso: fib(40, new long[41])

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Ahora cada valor se calcula una sola vez y el coste es O(n). Esta idea, guardar resultados de subproblemas para no repetirlos, es la base de la programación dinámica, que verás en asignaturas de algoritmia en la universidad.

Ejercicio 8: permutaciones (backtracking)

Enunciado. Muestra todas las permutaciones de los caracteres de una cadena sin repetidos. Para "abc": abc, acb, bac, bca, cab, cba.

Aquí la recursividad no se usa para reducir un número, sino para probar opciones: en cada llamada eliges qué letra va en la siguiente posición, y la llamada recursiva coloca el resto.

static void permutar(String prefijo, String resto) {
    if (resto.isEmpty()) {
        System.out.println(prefijo);
        return;
    }
    for (int i = 0; i < resto.length(); i++) {
        permutar(prefijo + resto.charAt(i),
                 resto.substring(0, i) + resto.substring(i + 1));
    }
}

// Uso: permutar("", "abc");

def permutar(prefijo, resto):
    if not resto:
        print(prefijo)
        return
    for i in range(len(resto)):
        permutar(prefijo + resto[i], resto[:i] + resto[i + 1:])

prefijo es lo que ya has decidido y resto, las letras que quedan por colocar. Cuando no queda ninguna, tienes una permutación completa. Con n letras hay n! permutaciones, así que con 10 letras ya son más de tres millones y medio.

Este esquema (elegir, llamar, deshacer y probar la siguiente opción) es el backtracking, y con pequeños cambios resuelve subconjuntos, combinaciones, el problema de las N reinas o los laberintos.

Recursividad o bucle: cuándo usar cada uno

Todo lo que se hace con recursividad se puede hacer con bucles, y al revés. La pregunta es cuál se lee mejor.

Problema	Mejor con	Por qué
Factorial, suma de dígitos, recorrer un array	Bucle	Es una repetición lineal; la recursividad gasta pila sin aportar claridad
Búsqueda binaria	Cualquiera	Las dos versiones son cortas y claras
Árboles (recorridos, altura, buscar en un árbol binario)	Recursividad	La estructura es recursiva: un árbol es un nodo con subárboles
Divide y vencerás (mergesort, quicksort)	Recursividad	Se parte el problema en mitades que se resuelven igual
Backtracking (permutaciones, N reinas, laberintos)	Recursividad	Con bucles hay que gestionar una pila a mano

En el examen, si el enunciado dice "de forma recursiva", no uses bucles para la parte que pide recursión: aunque funcione, te lo pueden puntuar como mal. Los árboles y la ordenación los tienes en la guía de Estructuras de Datos.

Los errores que más vemos en clase

No poner caso base, o ponerlo después de la llamada. El caso base tiene que comprobarse antes de llamar a la función otra vez. Si va después, nunca se llega a él.

Que el caso recursivo no se acerque al caso base. f(n) que llama a f(n), o a f(n - 2) cuando el caso base es n == 0 y n puede ser impar.

Olvidar el return en la llamada recursiva. En Java no compila si el método devuelve algo y falta un return, pero en Python sí funciona... y la función devuelve None:

def suma_digitos(n):
    if n < 10:
        return n
    n % 10 + suma_digitos(n // 10)   # falta return: devuelve None

Modificar el parámetro en vez de pasar uno nuevo. f(n--) pasa el valor antiguo de n (por cómo funciona el post-decremento) y la función nunca avanza. Escribe siempre f(n - 1).

Usar recursividad con entradas enormes. Python corta por defecto a unas 1000 llamadas anidadas con RecursionError. Java aguanta entre unos miles y unas decenas de miles, según el tamaño de la pila, antes del StackOverflowError. Para recorrer listas de cien mil elementos, usa un bucle.

Si te sale un StackOverflowError y no sabes por qué, pon un punto de interrupción en la primera línea de la función y mira cómo cambia el parámetro en cada llamada. Tienes el método en cómo depurar código paso a paso.

Cómo practicar la recursividad

Traza en papel antes de ejecutar. Dibuja la pila como en la tabla del factorial. Después de cinco o seis ejercicios trazados a mano dejarás de necesitarlo, pero al principio es lo que hace que lo entiendas.

Resuelve cada ejercicio dos veces: con bucle y con recursividad. Así ves qué parte del bucle se convierte en caso base (la condición de parada) y cuál en caso recursivo (el cuerpo).

Después de cada ejercicio, pregúntate cuántas llamadas hace. Una por nivel (lineal), una por cada mitad (logarítmica) o dos por nivel (exponencial). Es justo lo que te preguntarán en la universidad cuando veas complejidad.

Practica variaciones. Contar cuántas veces aparece un dígito en un número, sumar un array, comprobar si un array está ordenado, contar vocales, pasar un número a binario. Todas siguen el mismo esquema.

Cuándo pedir ayuda

Si haces los ocho ejercicios sin mirar y aciertas las preguntas de "¿qué imprime?" trazando la pila, vas bien. Merece la pena pedir ayuda cuando:

Entiendes las soluciones pero no sabrías escribir el caso recursivo de un problema nuevo.
Te salen StackOverflowError o resultados None y no sabes por qué.
Tienes que hacer recursividad sobre árboles o backtracking para una práctica de la universidad y no sabes ni plantearla.

En nuestras clases de programación para universidad, las clases para DAM y DAW y las clases de Java o Python trabajamos la recursividad sobre los ejercicios de tu asignatura: los trazamos juntos, los escribes tú y repetimos con variaciones hasta que el caso recursivo te salga solo. Son clases online uno a uno a 25 € la hora, sin matrícula ni permanencia.

Preguntas frecuentes

¿Qué es la recursividad en programación?

Es una técnica en la que una función se llama a sí misma para resolver una versión más pequeña del mismo problema. Necesita un caso base, que se resuelve sin volver a llamarse, y un caso recursivo, que reduce el problema y se acerca al caso base en cada llamada.

¿Qué es el caso base de una función recursiva?

Es la situación en la que la función devuelve un resultado directamente, sin llamarse otra vez: n == 0, una cadena vacía, un array de un elemento. Sin caso base, la función se llama sin fin y el programa termina con un desbordamiento de pila.

¿Por qué me sale StackOverflowError?

Porque la función se llama a sí misma demasiadas veces sin terminar. Casi siempre es porque falta el caso base, porque el caso recursivo no se acerca a él (por ejemplo, llamar con n en vez de n - 1) o porque la entrada es tan grande que la pila no da para tantas llamadas.

¿Es mejor la recursividad o un bucle?

Para repeticiones lineales (sumar, contar, recorrer) es mejor un bucle: es igual de claro y no gasta pila. La recursividad es mejor cuando el problema tiene estructura recursiva, como los árboles, el divide y vencerás o el backtracking.

¿Cómo se calcula la complejidad de una función recursiva?

Contando cuántas llamadas se hacen y cuánto trabajo hace cada una. Si cada llamada hace una sola llamada con n - 1, es O(n). Si reduce el problema a la mitad, O(log n). Si hace dos llamadas con n - 1 y n - 2, como Fibonacci sin memorización, el coste crece de forma exponencial. En la universidad esto se formaliza con ecuaciones de recurrencia.

¿En qué asignaturas se da recursividad?

En Programación de primero de DAM y DAW, en Fundamentos de Programación y Estructuras de Datos en Ingeniería Informática, y después en asignaturas de algoritmia (divide y vencerás, backtracking, programación dinámica). Tienes el contexto de cada una en Fundamentos de Programación en la universidad y las asignaturas más difíciles de Ingeniería Informática.