Tabla de contenidos
La recursividad es una técnica muy empleada para resolver problemas en programación. Es la capacidad de una función de llamarse a sí misma. Dicho de otro modo, una función recursiva es aquella que está definida en función de sí misma, y se llamará a sí misma hasta que se cumpla una condición.
La recursión es una herramienta muy potente de resolución de problemas. Muchos algoritmos se pueden expresar más fácilmente usando una formulación recursiva. Incluso, hay muchos problemas cuyas soluciones más eficientes se obtienen con algoritmos recursivos.
Es importante tener cuidado al utilizar la recursividad, ya que una función recursiva puede consumir mucha memoria si se llama a sí misma muchas veces y puede ser menos eficiente que una solución iterativa. Sin embargo, en algunos casos, la recursividad puede proporcionar una solución clara y concisa a un problema.
Métodos recursivos
En programación, un método es un bloque de instrucciones que se encarga de realizar una determinada tarea. Los métodos se componen de:
- Cabecera: un nombre para identificarlo, y datos externos(parámetros).
- Cuerpo: instrucciones que se van a ejecutar.
static void saludar(int n) { //cabecera
for(int i = 0; i < n; i++) //cuerpo
System.out.println("Hola"); //cuerpo
}
La cabecera es la primera línea, en ella declaramos un método que se llama saludar( ) y recibe como dato externo(parámetro) un entero(int).
Este método tiene un bucle que realizará tantas iteraciones como el valor del parámetro «n«, y en cada una de las iteraciones mostrará por pantalla la palabra «Hola«.
A continuación, invocamos al método a partir de su nombre. En la invocación debemos proporcionarle los datos que el método necesita, en este caso un entero(3).
saludar(3); //invocamos al método pasando un 3 como parámetro
Finalmente se ejecutan las instrucciones de dentro del método, utilizando el entero que le hemos pasado como parámetro al invocarlo. En este ejemplo se mostrará la palabra «Hola» tantas veces como el valor introducido como parámetro, 3 veces.
Funcionamiento de un método recursivo
Un método recursivo, es un método que en algún punto del código se invoca a sí mismo. Esta técnica puede ser peligrosa. Si no se aplica de forma correcta, puede dar lugar a invocaciones sucesivas de forma indefinida sobre el método, esto se traduce en una lógica circular similar a los bucles infinitos.
Para solucionar este problema, la clave está en que el método se invoca a sí mismo con una instancia distinta(de menor complejidad). Esto provocará en algún momento una invocación recursiva sobre un problema que se puede resolver de forma trivial, a este caso se le denomina «caso base«.
Veamos ahora el ejemplo anterior pero con un método recursivo:
static void saludar(int n) {
if(n > 1) {
System.out.println("Hola");
saludar(n-1);
}
}
En este ejemplo se mostrará la palabra «Hola» tantas veces como el valor introducido como parámetro, exactamente igual que antes. La diferencia radica en que ahora no hemos utilizado ningún bucle. Aquí se llegará al caso base cuando «n» sea menor que 1. En ese caso ya no se realizará ninguna llamada recursiva adicional, y el método finaliza.
El funcionamiento del método es el siguiente:
Tenemos una condición que comprueba si el valor pasado como parámetro es mayor que uno. En ese caso, mostramos «Hola», y hacemos una invocación recursiva, pero pasando como parámetro el valor de «n» restando 1, esto lo que implica es que en algún momento «n» será 0 y las invocaciones recursivas terminarán.
Veamos un ejemplo adicional para entender mejor este comportamiento.
El factorial de un número
Hay un programa muy significativo que se suele utilizar para explicar la recursividad. Se trata de obtener el factorial de un número «n». El factorial de un número (n!), se define como el producto de los n primeros números enteros. Por ejemplo, el factorial de 4 se resuelve de la siguiente forma:
4! = 4 x 3 x 2 x 1 = 24
Esto nos permite escribir n! como n veces (n-1)!, veamos ejemplos adicionales:
4! = 4 x 3!
3! = 3 x 2!
2! = 2 x 1!
1! = 1 x 0!
0! = 1
Si todo lo anterior, lo combinamos con el caso más simple, 0! = 1, podemos extraer la siguiente expresión:
Aquí se pueden diferenciar dos casos:
- El caso base, es el que se puede resolver trivialmente.
- El caso general, es el que resuelve recursivamente, empleando una invocación al mismo algoritmo para casos más sencillos.
- Caso base, cuando n vale 0.
- Caso general, cuando n es mayor que 0.
El siguiente método recursivo en JAVA resuelve el factorial de ‘n’:
static int factorial(int n) {
if(n == 0) return 1; //caso base
else return n*factorial(n-1); //caso general
}
El caso base de un método recursivo permite detener la recursión (no se hace ninguna llamada en él), por lo que resulta imprescindible.
En las llamadas recursivas del caso general alguno de los parámetros debe modificar su valor para que finalmente, tras un número finito de llamadas, se alcance el caso base. En el ejemplo del factorial, se realiza la llamada recursiva sobre n-1, por lo tanto en algún momento n llegará a valer 0, en ese momento llegaremos al caso base, y con ello terminan las llamadas recursivas.
Además, en métodos recursivos hay algo muy importante que debemos tener en cuenta, la recursión hace un uso intensivo de la pila de llamadas. Si no sabes de qué hablo, te explico en detalle la pila de llamadas en este vídeo. Luego puedes comprobar si lo has entendido bien, con el ejercicio de este otro vídeo.
A parte de esto, si no te ha quedado del todo claro el concepto de recursividad, te lo explico con más detalle en el siguiente vídeo de mi canal de YouTube.
Demasiada recursión es peligrosa
Es muy importante darse cuenta de que la recursión no siempre es apropiada. Una regla que debemos seguir es que nunca se debe usar la recursión para sustituir un bucle simple. Esto se debe al alto consumo de recursos que se hacen de la pila de llamadas. Dicha pila se aloja en memoria RAM, y para dispositivos con poca capacidad de memoria, puede no ser una buena solución.
Pero además, en los algorimos recursivos pueden aparecer problemas más complejos que no son tan evidentes. Veamos el ejemplo de los números de Fibonacci de forma recursiva.
Lo primero para entender la recursividad, es entender la recursividad.
Los números de Fibonacci
Los primeros números de Fibonacci se definen de la siguiente forma:
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
El i-ésimo número de fibonacci es igual a la suma de los dos anteriores. Los números de Fibonacci tienen una gran cantidad de propiedades. Existe incluso, una revista, The Fibonacci Quarterly, con el objetivo de publicar teoremas que impliquen a los números de Fibonacci.
Puesto que los números de Fibonacci se definen recursivamente, parece natural crear un método recursivo que lo resuelva. Este método, que se puede ver más abajo, y funciona sin ningún problema de forma teórica, sin embargo, pero tiene un gran problema.
En una ordenador rápido se tarda muchísimo tiempo en calcular Fibonacci de 50. Esto se traduce en una cantidad sin sentido de tiempo, ya que realmente se deben hacer solamente 49 sumas. El problema es que este método recursivo realiza muchos cálculos repetidos. Para calcular fibonacci(n) , calculamos recursivamente fibonacci(n-l) . Cuando la llamada recursiva termina, calculamos fibonacci(n-2) usando otra llamada recursiva. Pero en realidad ya se había calculado fibonacci(n -2) cuando hemos calculado fibonacci(n -1) , luego la llamada a fibonacci(n-2) de nuevo está repetida, y por ello, de nuevo se traduce en un calculo innecesario.
//obtener el número de fibonacci de n
static int fibonacci(int n) {
if(n <= 1) return n; //caso base
else return fibonacci(n-1) + fibonacci(n-2); //caso general
}
Normalmente, hacer dos llamadas a un método en lugar de una, suele duplicar el tiempo de ejecución de un programa, pero en este caso la situación es mucho peor, la llamada a fibonacci(n -1) como las llamadas a fibonacci(n -2) hacen a su vez llamadas a fibonacci(n-3), 10 que significa que hay en realidad tres llamadas a fibonacci(n -3 ) . A partir de ahí, la situación se vuelve todavía peor: las llamadas a fibonacci(n-2) y a fibonacci(n-3) producen llamadas a fibonacci(n-4) , cinco en total. Obtenemos por tanto un efecto que se acumula de forma brutal: cada llamada recursiva produce más y más trabajo redundante.
En consecuencia, el número de llamadas recursivas es incluso mayor que el número de Fibonacci que queremos calcular. Por ejemplo, para N = 40, el resultado es 102.334.155, mientras que el número total de llamadas recursivas es mayor que 300 millones. No nos debemos sorprender si al calcular fibonacci(50) el ordenador no es capaz de terminar, ya que un procesador actual podría tardar 10000 años en obtenerlo y necesitar más de 1×103 hexabytes de memoria RAM para poder almacenar semejante pila de llamadas.
A continuación se puede observar el crecimiento del número de llamadas recursivas.
Divide y vencerás
Una técnica importante de resolución de problemas que hace uso de la recursión es la técnica de divide y vencerás. Los algoritmos divide y vencerás son algoritmos recursivos que constan de dos partes:
- Dividir: se resuelven recursivamente problemas más pequeños (excepto, por supuesto , los casos base).
- Vencer: la solución al problema original se consigue a partir de las soluciones a los subproblemas.
Tradicionalmente, las rutinas en las que el algoritmo contiene al menos dos llamadas recursivas se llaman algoritmos divide y vencerás, al contrario que las rutinas cuyo texto contiene solamente una llamada recursiva. En consecuencia, las rutinas recursivas vistas hasta el momento en este capítulo, no son algoritmos divi-de y vencerás. Además, los subproblemas deben ser disjuntos (más exactamente, esencialmente sin superposiciones) para evitar los costes excesivos que ya se vie-ron en el cálculo recursivo de los números de Fibonacci. En esta sección presen-taremos un ejemplo del paradigma divide y vencerás: veremos cómo usar la re-cursión para resolver el problema de la obtención de la subsecuencia de suma máxima. A continuación presentamos el análisis de esta solución recursiva, de-mostrando que su tiempo de ejecución es O(N log N). Aunque ya vimos un algo-ritmo lineal para resolver este problema, lo que presentamos ahora es un ejemplo representativo de una gran variedad de aplicaciones, incluyendo los algoritmos de ordenación, como mergesort y quicksort, estudiados en el Capítulo 8. Resulta por tanto muy importante estudiar esta técnica. Para terminar, discutiremos la forma general del tiempo de ejecución de una amplia variedad de algoritmos divide y vencerás.
Búsqueda binaria
Pasemos a ver el algoritmo de búsqueda binaria de forma recursiva.
En una búsqueda binaria, se realiza la búsqueda de un elemento en un vector ordenado. En primer lugar se examina el elemento del centro. Si dicho elemento es el que buscamos, ya hemos terminado. En caso contrario, si el elemento que estamos buscando es menor que el elemento del centro, buscamos en la mitad izquierda del vector, y si es mayor, buscamos en la mitad derecha. Esto, siempre que queden elementos, de lo contrario, el elemento buscado no se encuentra en el vector. A continuación podemos ver un método en JAVA que realiza este proceso.
static boolean busquedaBinaria(int[] numeros, int numeroBuscado, int limiteInferior, int limiteSuperior) {
if (limiteInferior > limiteSuperior)
return false;
int mitad = (limiteInferior + limiteSuperior) / 2;
if (numeros[mitad] < numeroBuscado)
return busquedaBinaria(numeros, numeroBuscado, mitad + 1, limiteSuperior);
else if (numeros[mitad] > numeroBuscado)
return busquedaBinaria(numeros, numeroBuscado, limiteInferior, mitad - 1);
else
return true;
}
En primer lugar se debe tener en cuenta que los 2 parámetros finales se deben inicializar siempre a 0 y a .length-1. De hecho la forma más correcta para implementar el método sería a través de un método intermedio, como por ejemplo:
static void mostrarBusquedaBinaria(int[] numeros, int numeroBuscado) {
if (busquedaBinaria(numeros, numeroBuscado, 0, numeros.length - 1))
System.out.println("El número " + numeroBuscado + " está en el Array.");
else
System.out.println("El número " + numeroBuscado + " NO está en el Array.");
}
En el método recursivo busquedaBinaria( ), el caso base lo tenemos en las líneas 3 y 4 del primer método, en ese caso se trata de un Array vacío. En caso contrario, obtenemos el punto central del Array y lo comparamos, si coindice, lo hemos encontrado. Si no coincide, hacemos la búsqueda por la izquierda o por la derecha dependiendo del valor del centro. Si dicho valor central es menor que el buscado, analizamos de mitad hasta el final, en cambio, si el valor del centro es mayor que el buscado, analizamos desde la mitad hasta el inicio.
El algoritmo de ordenación rápida Quicksort
Otro algoritmo muy estudiado Divide y Vencerás es el método de ordenación rápida Quicksort. Este algoritmo es en promedio uno de los algoritmos de ordenación más rápidos que existen.
Funciona dividiendo el Array a ordenar en dos subaArrays más pequeños y ordenando cada uno de ellos de forma recursiva. A continuación se explica cómo funciona el algoritmo quicksort de forma detallada:
Seleccionar un elemento del Array como pivote. Este elemento se conoce como el elemento pivote y suele seleccionarse de forma aleatoria o tomando el primer, el último o el elemento medio del Array.
Reordenar el Array de forma que todos los elementos menores que el pivote queden a su izquierda y todos los elementos mayores queden a su derecha. Este proceso se conoce como partición del Array.
Aplicar el mismo proceso de forma recursiva a cada uno de los subArrays obtenidos en el paso anterior hasta que cada subArray contenga solo un elemento.
El resultado final será un Array completamente ordenado.
Aquí tienes un ejemplo de código que implementa el algoritmo quicksort en JAVA:
public static void quicksort(int A[], int izq, int der) {
int pivote = A[izq]; // tomamos primer elemento como pivote
int i = izq; // i realiza la búsqueda de izquierda a derecha
int j = der; // j realiza la búsqueda de derecha a izquierda
int aux;
while(i < j){ // mientras no se crucen las búsquedas
while(A[i] <= pivote && i < j) i++; // busca elemento mayor que pivote
while(A[j] > pivote) j--; // busca elemento menor que pivote
if (i < j) { // si no se han cruzado
aux = A[i]; // los intercambia
A[i] = A[j];
A[j] = aux;
}
}
A[izq] = A[j]; // se coloca el pivote en su lugar de forma que tendremos
A[j] = pivote; // los menores a su izquierda y los mayores a su derecha
if(izq < j-1) quicksort(A, izq, j-1); // ordenamos subarray izquierdo
if(j+1 < der) quicksort(A, j+1, der); // ordenamos subarray derecho
}
Para utilizar el algoritmo quicksort, solo necesita llamar a la función `quicksort` con el Array a ordenar y los índices del primer y último elemento del Array. La función `quicksort` se encargará de particionar el Array y aplicar el proceso de forma recursiva a cada uno de los subArrays hasta que el Array completo esté ordenado. Es importante tener en cuenta que el rendimiento del algoritmo quicksort depende en gran medida de la elección del elemento pivote. Si siempre se elige el mismo elemento como pivote (por ejemplo, el primer elemento del Array), el algoritmo puede ser muy ineficiente en el peor de los casos (por ejemplo, si el arreglo está ordenado de forma descendente). Por eso, es importante elegir el elemento pivote de forma aleatoria o tomando el elemento medio del Array para mejorar el rendimiento del algoritmo.
Si te interesa el tema, te dejo el enlace a un vídeo de mi canal de YouTube donde explico con más detalle el funcionamiento del algoritmo.
Algoritmos de vuelta atrás
Existen otros tipo de algoritmos muy utilizados en recursión, entre ellos, podemos destacar los algoritmos de vuelta atrás. Este tipo de algoritmos se utilizan para probar de forma sistemática todas las posibles soluciones de un problema.
Los algoritmos de vuelta atrás, también conocidos como algoritmos de retroceso o backtracking, son una técnica de búsqueda utilizada para encontrar soluciones a problemas que pueden ser divididos en subproblemas más pequeños. Estos algoritmos funcionan revisando todas las posibles soluciones y haciendo «vuelta atrás» cuando encuentran una solución inválida, en lugar de continuar explorando esa rama.
Un ejemplo típico de un problema que se puede resolver con un algoritmo de vuelta atrás es el problema de las ocho reinas, en el que se debe colocar ocho reinas en un tablero de ajedrez de forma que ninguna reina ataque a otra. Para resolver este problema, podemos utilizar un algoritmo de vuelta atrás que pruebe todas las posibles combinaciones de colocación de reinas y haga «vuelta atrás» cuando encuentre una combinación inválida (es decir, cuando dos reinas estén en la misma fila, columna o diagonal).
Para implementar un algoritmo de vuelta atrás, es necesario seguir los siguientes pasos:
Definir la estructura de datos que se utilizará para almacenar la solución parcial. Esto puede ser una lista, un vector o cualquier otra estructura de datos adecuada para el problema en cuestión.
Implementar una función de retroceso que tome la solución parcial y haga «vuelta atrás» en un paso dado. Esta función debe eliminar el último elemento agregado a la solución parcial y debe devolver la solución parcial actualizada.
Implementar una función de búsqueda que utilice la función de retroceso para probar todas las posibles soluciones. Esta función debe comenzar con una solución parcial vacía y agregar elementos uno por uno, llamando a la función de retroceso cada vez que se encuentre una solución inválida.
Ejecutar la función de búsqueda y devolver la primera solución válida encontrada.
Es importante tener en cuenta que los algoritmos de vuelta atrás pueden ser muy ineficientes para problemas grandes debido a la gran cantidad de soluciones inválidas que se deben explorar. Sin embargo, son muy útiles para problemas de tamaño moderado y pueden ser una buena opción cuando no existe un algoritmo más eficiente disponible.
A continuación se muestra una implementación del algoritmo de vuelta atrás para resolver el problema de las ocho reinas en JAVA.
public class EightQueens {
// Tamaño del tablero
private static final int N = 8;
// Matriz para almacenar la solución
private static int[][] board = new int[N][N];
// Función de retroceso
private static void backtrack(int row) {
// Si se han colocado todas las reinas, se ha encontrado una solución válida
if (row == N) {
printSolution();
return;
}
// Probar todas las posibles posiciones en la fila actual
for (int col = 0; col < N; col++) {
// Si es seguro colocar la reina en esta posición, hacerlo y continuar con la siguiente fila
if (isSafe(row, col)) {
board[row][col] = 1;
backtrack(row + 1);
// Hacer "vuelta atrás" y eliminar la reina de la posición actual
board[row][col] = 0;
}
}
}
// Comprobar si es seguro colocar una reina en la posición (row, col)
private static boolean isSafe(int row, int col) {
// Comprobar si hay alguna reina en la misma columna
for (int i = 0; i < row; i++) {
if (board[i][col] == 1) {
return false;
}
}
// Comprobar si hay alguna reina en la misma diagonal hacia arriba a la izquierda
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 1) {
return false;
}
}
// Comprobar si hay alguna reina en la misma diagonal hacia arriba a la derecha
for (int i = row, j = col; i >= 0 && j < N; i--, j++) {
if (board[i][j] == 1) {
return false;
}
}
// Si no se ha encontrado ninguna reina en la misma columna, fila o diagonal, es seguro colocar la reina aquí
return true;
}
// Imprimir la solución encontrada
private static void printSolution() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
public static void main(String[] args) {
backtrack(0);
}
}
Para utilizar este código, solo se necesita llamar a la función backtrack con el índice de la fila donde desea comenzar a colocar las reinas. La función backtrack se encargará de probar todas las posibles combinaciones de colocación de reinas y hacer «vuelta atrás» cuando encuentre una combinación inválida.
Por ejemplo, para encontrar una solución al problema de las ocho reinas, puede llamar a la función backtrack de la siguiente manera:
public static void main(String[] args) {
backtrack(0);
}
Esto comenzará a probar todas las posibles combinaciones de colocación de reinas en la primera fila del tablero y, a medida que avance, irá probando todas las combinaciones posibles en cada una de las filas siguientes. Cuando se encuentre una solución válida, se imprimirá en pantalla y se detendrá la ejecución. Si no se encuentra ninguna solución, la función backtrack simplemente regresará sin hacer nada.
Los algoritmos de vuelta atrás son todos recursivos?
No necesariamente. Los algoritmos de vuelta atrás pueden ser implementados de forma iterativa o recursiva. La implementación recursiva se basa en la llamada recursiva de la función de búsqueda cada vez que se agrega un elemento a la solución parcial, mientras que la implementación iterativa se basa en el uso de un bucle para explorar todas las posibles soluciones.
La implementación recursiva puede ser más fácil de entender y escribir, ya que sigue de cerca la estructura del problema y permite la división del problema en subproblemas más pequeños de forma natural. Sin embargo, puede ser menos eficiente que la implementación iterativa debido a la overhead adicional de la llamada recursiva y el uso de la pila de llamadas.
La implementación iterativa, por otro lado, puede ser más eficiente debido a que evita el overhead de la llamada recursiva y el uso de la pila de llamadas. Sin embargo, puede ser más difícil de entender y escribir, ya que requiere una mayor cantidad de código para controlar la exploración de las posibles soluciones y hacer «vuelta atrás» cuando se encuentra una solución inválida.
Ejercicios resueltos recursividad
Estás empezando con la recursión y te está costando de entender? Si es así, lo mejor es ver distintos tipos de ejercicios resueltos.
A continuación te dejo una serie de ejercicios resueltos adicionales de recursividad en JAVA, algunos de ellos se explican con detalle en el vídeo de arriba.
