Este tutorial en profundidad sobre la recursividad en Java explica qué es la recursividad con ejemplos, tipos y conceptos relacionados. También cubre la recursividad frente a la iteración:
En nuestros anteriores tutoriales de Java, hemos visto el enfoque iterativo en el que declaramos un bucle y luego recorremos una estructura de datos de forma iterativa tomando un elemento cada vez.
También hemos visto el flujo condicional donde de nuevo mantenemos una variable de bucle y repetimos un trozo de código hasta que la variable de bucle cumple la condición. Cuando se trata de llamadas a funciones, exploramos el enfoque iterativo para llamadas a funciones también.
En este tutorial, hablaremos de un enfoque diferente de la programación, es decir, el enfoque recursivo.
¿Qué es la recursión en Java?
La recursividad es un proceso por el cual una función o un método se llama a sí mismo una y otra vez. Esta función que se llama una y otra vez directa o indirectamente se denomina "función recursiva".
Veremos varios ejemplos para entender la recursividad. Ahora veamos la sintaxis de la recursividad.
Sintaxis de recursión
Cualquier método que implemente la Recursión tiene dos partes básicas:
- Llamada a un método que puede llamarse a sí mismo, es decir, recursivo
- Una precondición que detendrá la recursión.
Tenga en cuenta que una precondición es necesaria para cualquier método recursivo ya que, si no rompemos la recursividad entonces seguirá ejecutándose infinitamente y dará lugar a un desbordamiento de pila.
La sintaxis general de la recursividad es la siguiente:
methodName (T parameters...) { if (precondition == true) //precondición o condición base { return result; } return methodName (T parameters...); //llamada recursiva } Tenga en cuenta que la condición previa también se denomina condición base. En la siguiente sección hablaremos más sobre la condición base.
Comprender la recursión en Java
En esta sección, intentaremos comprender el proceso de recursión y ver cómo se lleva a cabo. Aprenderemos sobre la condición base, el desbordamiento de pila, y veremos cómo se puede resolver un problema concreto con recursión y otros detalles similares.
Condición básica de recursión
Al escribir el programa recursivo, primero debemos proporcionar la solución para el caso base. A continuación, expresamos el problema mayor en términos de problemas más pequeños.
Como ejemplo, podemos tomar un problema clásico de cálculo del factorial de un número. Dado un número n, tenemos que encontrar un factorial de n denotado por ¡n!
Ahora vamos a implementar el programa para calcular el factorial n (¡n!) utilizando la recursividad.
public class Main{ static int fact(int n) { if (n == 1) // condición base return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("¡10! = " + result); } } Salida
En este programa, podemos ver que la condición (n<=1) es la condición base y cuando se alcanza esta condición, la función devuelve 1. La parte else de la función es la llamada recursiva. Pero cada vez que se llama al método recursivo, n se decrementa en 1.
Por lo tanto, podemos concluir que en última instancia el valor de n se convertirá en 1 o menos que 1 y en este punto, el método devolverá el valor 1. Esta condición base se alcanzará y la función se detendrá. Tenga en cuenta que el valor de n puede ser cualquier cosa, siempre y cuando satisfaga la condición base.
Resolución de problemas mediante recursión
La idea básica que subyace al uso de la recursividad es expresar el problema mayor en términos de problemas más pequeños. Además, necesitamos añadir una o más condiciones base para poder salir de la recursividad.
Esto ya se demostró en el ejemplo factorial anterior. En este programa, expresamos el factorial n (¡n!) en términos de valores más pequeños y teníamos una condición base (n <=1) de forma que cuando n llega a 1, podemos abandonar el método recursivo.
Error de desbordamiento de pila en la recursión
Sabemos que cuando se llama a cualquier método o función, el estado de la función se almacena en la pila y se recupera cuando la función retorna. La pila se utiliza también para el método recursivo.
Pero en el caso de la recursividad, puede ocurrir un problema si no definimos la condición base o cuando la condición base de alguna manera no se alcanza o no se ejecuta. Si esta situación ocurre entonces puede surgir el desbordamiento de pila.
Consideremos el siguiente ejemplo de notación factorial.
Aquí hemos dado una condición base errónea, n==100.
public class Main { static int fact(int n) { if (n == 100) // condición base que resulta en desbordamiento de pila return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("¡10! = " + result); } } Así que cuando n> 100 el método devolverá 1, pero la recursión no se detendrá. El valor de n seguirá disminuyendo indefinidamente ya que no hay otra condición para detenerlo. Esto continuará hasta que la pila se desborde.
Otro caso será cuando el valor de n <100. En este caso, también el método nunca ejecutará la condición base y dará lugar a un desbordamiento de pila.
Ejemplos de recursión en Java
En esta sección, implementaremos los siguientes ejemplos utilizando la recursividad.
#1) Series de Fibonacci mediante recursión
La serie de Fibonacci viene dada por,
1,1,2,3,5,8,13,21,34,55,…
La secuencia anterior muestra que el elemento actual es la suma de los dos elementos anteriores. Además, el primer elemento de la serie de Fibonacci es 1.
Así, en general, si n es el número actual, entonces viene dado por la suma de (n-1) y (n-2). Como el elemento actual se expresa en términos de elementos anteriores, podemos expresar este problema mediante recursión.
A continuación se presenta el programa para implementar la serie de Fibonacci:
public class Main { /método para calcular la serie fibonacci static int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); } public static void main(String[] args) { int number = 10; //imprime los 10 primeros números de la serie fibonacci System.out.println ("Serie Fibonacci: Primeros 10 números:"); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + " ");} } } Salida
#2) Comprobar si un número es un palíndromo utilizando la recursión
Un palíndromo es una secuencia que es igual cuando la leemos de izquierda a derecha o de derecha a izquierda.
Dado un número 121, vemos que cuando lo leemos de izquierda a derecha y de derecha a izquierda, es igual. Por lo tanto, el número 121 es un palíndromo.
Tomemos otro número, 1242. Cuando lo leemos de izquierda a derecha es 1242 y cuando lo leemos de derecha a izquierda se lee como 2421. Por lo tanto esto no es un palíndromo.
Implementamos el programa de palíndromos invirtiendo los dígitos de los números y comparamos recursivamente el número dado con su representación invertida.
El siguiente programa implementa el programa para comprobar el palíndromo.
import java.io.*; import java.util.*; public class Main { //comprueba si num contiene sólo un dígito public static int oneDigit(int num) { if ((num>= 0) && (num <10)) return 1; else return 0; } //función de utilidad del palíndromo public static int isPalindrome_util (int num, int revNum) throws Exception { //condición base; return if num=0 if (num == 0) { return revNum; } else { //callfunción de utilidad recursiva revNum = isPalindrome_util(num / 10, revNum); } // Comprueba si el primer dígito de num y revNum son iguales if (num % 10 == revNum % 10) { // en caso afirmativo, revNum se moverá con num return revNum / 10; } else { // exit throw new Exception(); } } } /método para comprobar si un número dado es palíndromo usando la función de utilidad palíndromo public static int isPalindrome(int num) throwsException { if (num <0) num = (-num); int revNum = (num); return isPalindrome_util(num, revNum); } public static void main(String args[]) { int n = 1242; try { isPalindrome(n); System.out.println("Sí, el número dado " + n + " es un palíndromo."); } catch (Exception e) { System.out.println("No, el número dado " + n + " no es un palíndromo."); } n = 1221; try { isPalindrome(n);System.out.println("Sí, el número dado " + n + " es un palíndromo."); } catch (Exception e) { System.out.println("No, el número dado " + n + " no es un palíndromo."); } } } Salida
#3) Recursión inversa de cadenas Java
Dada una cadena "Hola" tenemos que invertirla para que la cadena resultante sea "olleH".
Para ello se utiliza la recursividad. Empezando por el último carácter de la cadena, imprimimos recursivamente cada carácter hasta agotar todos los caracteres de la cadena.
El siguiente programa utiliza la recursividad para invertir una cadena dada.
class String_Reverse { //método recursivo para invertir una cadena dada void reverseString(String str) { //condición base; devuelve si la cadena es nula o con 1 o menos caracteres if ((str==null)} } } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("La cadena dada: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("La cadena invertida: "); obj.reverseString(inputstr); } } Salida
#4) Búsqueda binaria Recursión Java
Un algoritmo de búsqueda binaria es un famoso algoritmo de búsqueda. En este algoritmo, dada una matriz ordenada de n elementos, buscamos en esta matriz el elemento clave dado. Al principio, dividimos la matriz en dos mitades encontrando el elemento medio de la matriz.
A continuación, en función de si la clave es media, limitamos la búsqueda a la primera o segunda mitad de la matriz. De este modo, se repite el mismo proceso hasta encontrar la ubicación de los elementos clave.
Aquí implementaremos este algoritmo utilizando la recursividad.
import java.util.*; class Binary_Search { // búsqueda binaria recursiva int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { //calcular el medio del array int mid = left + (right - left) / 2; // si la clave está en el medio, devolver mid if (numArray[mid] == clave) devolver mid; // si clave clave) devolver binarySearch(numArray, left, mid - 1, clave); // si no, buscar recursivamente en elsubmatriz derecha return binarySearch(numArray, mid + 1, right, key); } // no hay elementos en la matriz, devuelve -1 return -1; } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //declara e imprime la matriz int numArray[] = { 4,6,12,16,22}; System.out.println("La matriz dada : " + Arrays.toString(numArray)); int len = numArray.length; //longitud de la matrizint clave = 16; //clave a buscar int resultado = ob.binarySearch(numArray, 0, len - 1, clave); if (resultado == -1) System.out.println("Elemento " + clave + " no presente"); else System.out.println("Elemento " + clave + " encontrado en el índice " + resultado); } } Salida
#5) Encontrar el Valor Mínimo en un Array Usando Recursión
Utilizando la recursividad también podemos encontrar el valor mínimo de la matriz.
El programa Java para encontrar el valor mínimo en la matriz se da a continuación.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //devuelve el primer elemento si sólo hay un elemento o el mínimo de los elementos del array return (n == 1) ? numArray[i] : Math.min(numArray[i], getMin(numArray,i + 1 , n - 1)); } public static void main(String[] args) { int numArray[] = { 7,32,64,2,10,23 }; System.out.println("Array Dado : " + Arrays.toString(numArray)); int n =numArray.length; System.out.print("Elemento mínimo de la matriz: " + getMin(numArray, 0, n) + "\n"); } Salida
Estos son algunos de los ejemplos de recursividad. Aparte de estos ejemplos, muchos otros problemas del software pueden implementarse utilizando técnicas recursivas.
Tipos de recursión
La recursividad es de dos tipos según el momento en que se llame al método recursivo.
Lo son:
#nº 1) Recursión de cola
Cuando la llamada al método recursivo es la última sentencia ejecutada dentro del método recursivo, se denomina "Recursión de Cola".
En la recursividad de cola, la sentencia de llamada recursiva suele ejecutarse junto con la sentencia de retorno del método.
La sintaxis general de la recursividad de cola se indica a continuación:
methodName ( T parameters...){ { if (base_condition == true) { return result; } return methodName (T parameters ...) //recursión de cola } #2) Recursión de la cabeza
Recursividad de cabeza es cualquier enfoque recursivo que no sea una recursividad de cola. Así que incluso la recursividad general es recursividad de cabeza.
La sintaxis de la recursividad de la cabeza es la siguiente:
methodName (T parameters...){ if (some_condition == true) { return methodName (T parameters...); } return result; } Recursión e iteración en Java
| Recursión | Iteración |
|---|---|
| La recursión es un proceso en el que un método se llama a sí mismo repetidamente hasta que se cumple una condición base. | La iteración es un proceso mediante el cual un fragmento de código se ejecuta repetidamente durante un número finito de veces o hasta que se cumple una condición. |
| Es la aplicación para funciones. | Es aplicable a los bucles. |
| Funciona bien para códigos de menor tamaño. | Funciona bien para códigos de mayor tamaño. |
| Utiliza más memoria, ya que cada llamada recursiva se carga en la pila. | Comparativamente se utiliza menos memoria. |
| Difícil de depurar y mantener | Más fácil de depurar y mantener |
| Provoca un desbordamiento de pila si no se especifica o no se alcanza la condición base. | Puede ejecutarse infinitamente pero en última instancia se detendrá la ejecución con cualquier error de memoria |
| La complejidad temporal es muy alta. | La complejidad temporal es relativamente baja. |
Preguntas frecuentes
P #1) ¿Cómo funciona la recursión en Java?
Contesta: En la recursividad, la función recursiva se llama a sí misma repetidamente hasta que se cumple una condición base. La memoria de la función llamada se coloca en la pila en la parte superior de la memoria de la función llamante. Para cada llamada de función, se realiza una copia independiente de las variables locales.
Q #2) ¿Por qué se utiliza la recursividad?
Contesta: La recursión se utiliza para resolver aquellos problemas que pueden descomponerse en otros más pequeños y el problema completo puede expresarse en términos de un problema más pequeño.
La recursividad también se utiliza para aquellos problemas que son demasiado complejos para resolverlos mediante un enfoque iterativo. Además de los problemas para los que la complejidad temporal no es un problema, utilice la recursividad.
Q #3) ¿Cuáles son las ventajas de la recursividad?
Contesta:
Entre las ventajas de la recursividad se incluyen:
- La recursión reduce las llamadas redundantes a funciones.
- La recursividad nos permite resolver problemas fácilmente en comparación con el enfoque iterativo.
P #4) ¿Cuál es mejor - Recursión o Iteración?
Contesta: La recursividad realiza llamadas repetidas hasta que se alcanza la función base, por lo que existe una sobrecarga de memoria, ya que se introduce en la pila una memoria para cada llamada a una función.
Por otro lado, la iteración no tiene mucha sobrecarga de memoria. La ejecución por recursión es más lenta que el enfoque iterativo. La recursión reduce el tamaño del código, mientras que el enfoque iterativo lo agranda.
Q #5) ¿Cuáles son las ventajas de la recursión sobre la iteración?
Contesta:
- La recursividad hace que el código sea más claro y corto.
- La recursión es mejor que el enfoque iterativo para problemas como la Torre de Hanoi, los recorridos en árbol, etc.
- Como cada llamada a una función tiene memoria en la pila, la recursividad utiliza más memoria.
- El rendimiento de la recursión es más lento que el del enfoque iterativo.
Conclusión
La recursividad es un concepto muy importante en software, independientemente del lenguaje de programación. La recursividad se utiliza sobre todo para resolver problemas de estructuras de datos, como torres de Hanoi, recorridos en árbol, listas enlazadas, etc. Aunque ocupa más memoria, la recursividad simplifica y aclara el código.
En este tutorial hemos explorado todo lo referente a la Recursión. También hemos implementado numerosos ejemplos de programación para una mejor comprensión del concepto.