Recursión en Java

1. Introducción

En este artículo, nos centraremos en un concepto central en cualquier lenguaje de programación: la recursividad.

Explicaremos las características de una función recursiva y mostraremos cómo usar la recursividad para resolver varios problemas en Java.

2. Comprender la recursividad

2.1. La definición

En Java, el mecanismo de llamada a función admite la posibilidad de que un método se llame a sí mismo . Esta funcionalidad se conoce como recursividad .

Por ejemplo, supongamos que queremos sumar los números enteros de 0 a algún valor n :

public int sum(int n) { if (n >= 1) { return sum(n - 1) + n; } return n; }

Hay dos requisitos principales de una función recursiva:

  • Una condición de parada : la función devuelve un valor cuando se satisface una determinada condición, sin una llamada recursiva adicional
  • La llamada recursiva : la función se llama a sí misma con una entrada que está un paso más cerca de la condición de parada

Cada llamada recursiva agregará un nuevo marco a la memoria de pila de la JVM. Entonces, si no prestamos atención a qué tan profundo puede sumergirse nuestra llamada recursiva, puede ocurrir una excepción de falta de memoria.

Este problema potencial se puede evitar aprovechando la optimización de recursividad de cola.

2.2. Recursividad de la cola versus recursividad de la cabeza

Nos referimos a una función recursiva como tail-recursive cuando la llamada recursiva es lo último que ejecuta la función. De lo contrario, se conoce como recursividad de cabeza .

Nuestra implementación anterior de la función sum () es un ejemplo de recursividad de cabeza y se puede cambiar a recursión de cola:

public int tailSum(int currentSum, int n) { if (n <= 1) { return currentSum + n; } return tailSum(currentSum + n, n - 1); }

Con la recursividad de cola, la llamada recursiva es lo último que hace el método, por lo que no queda nada por ejecutar dentro de la función actual.

Por lo tanto, lógicamente no es necesario almacenar el marco de pila de la función actual.

Aunque el compilador puede utilizar este punto para optimizar la memoria, debe tenerse en cuenta que el compilador de Java no se optimiza para la recursividad de cola por ahora .

2.3. Recursión versus iteración

La recursividad puede ayudar a simplificar la implementación de algunos problemas complicados al hacer que el código sea más claro y legible.

Pero como ya hemos visto, el enfoque recursivo a menudo requiere más memoria, ya que la memoria de pila requerida aumenta con cada llamada recursiva.

Como alternativa, si podemos resolver un problema con recursividad, también podemos resolverlo mediante iteración.

Por ejemplo, nuestro método de suma podría implementarse mediante iteración:

public int iterativeSum(int n) { int sum = 0; if(n < 0) { return -1; } for(int i=0; i<=n; i++) { sum += i; } return sum; }

En comparación con la recursividad, el enfoque iterativo podría ofrecer un mejor rendimiento. Dicho esto, la iteración será más complicada y más difícil de entender en comparación con la recursividad, por ejemplo: atravesar un árbol binario.

Hacer la elección correcta entre la recursividad de la cabeza, la recursividad de la cola y un enfoque iterativo depende del problema y la situación específicos.

3. Ejemplos

Ahora, intentemos resolver algunos problemas de forma recursiva.

3.1. Encontrar la N-ésima potencia de diez

Suponga que necesitamos calcular la n -ésima potencia de 10. Aquí nuestra entrada es n. Pensando de forma recursiva, podemos calcular (n-1) -ésima potencia de 10 primero, y multiplicar el resultado por 10.

Luego, para calcular la (n-1) -ésima potencia de 10 será la (n-2) -ésima potencia de 10 y multiplicar ese resultado por 10, y así sucesivamente. Continuaremos así hasta que lleguemos a un punto en el que necesitemos calcular la (nn) -ésima potencia de 10, que es 1.

Si quisiéramos implementar esto en Java, escribiríamos:

public int powerOf10(int n) { if (n == 0) { return 1; } return powerOf10(n-1) * 10; }

3.2. Encontrar el elemento N-ésimo de la secuencia de Fibonacci

Comenzando con 0 y 1 , la Secuencia de Fibonacci es una secuencia de números donde cada número se define como la suma de los dos números que le siguen : 0 1 1 2 3 5 8 13 21 34 55

Entonces, dado un número n , nuestro problema es encontrar el n -ésimo elemento de la secuencia de Fibonacci . Para implementar una solución recursiva, necesitamos averiguar la condición de detención y la llamada recursiva .

Afortunadamente, es muy sencillo.

Llamemos a f (n) el n -ésimo valor de la secuencia. Entonces tendremos f (n) = f (n-1) + f (n-2) (la llamada recursiva ) .

Mientras tanto, f (0) = 0 y f (1) = 1 ( Detener Condición) .

Entonces, es realmente obvio para nosotros definir un método recursivo para resolver el problema:

public int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); }

3.3. Conversión de decimal a binario

Ahora, consideremos el problema de convertir un número decimal en binario. El requisito es implementar un método que reciba un valor entero positivo ny devuelva una representación de cadena binaria .

Un método para convertir un número decimal en binario es dividir el valor entre 2, registrar el resto y continuar dividiendo el cociente entre 2.

Seguimos dividiendo así hasta que obtenemos un cociente de 0 . Luego, escribiendo todos los restantes en orden de reserva, obtenemos la cadena binaria.

Por lo tanto, nuestro problema es escribir un método que devuelva estos residuos en orden de reserva:

public String toBinary(int n) { if (n <= 1 ) { return String.valueOf(n); } return toBinary(n / 2) + String.valueOf(n % 2); }

3.4. Altura de un árbol binario

La altura de un árbol binario se define como el número de aristas desde la raíz hasta la hoja más profunda. Nuestro problema ahora es calcular este valor para un árbol binario dado.

Un enfoque simple sería encontrar la hoja más profunda y luego contar los bordes entre la raíz y esa hoja.

Pero al intentar pensar en una solución recursiva, podemos reformular la definición de la altura de un árbol binario como la altura máxima de la rama izquierda de la raíz y la rama derecha de la raíz, más 1 .

Si la raíz no tiene rama izquierda ni rama derecha, su altura es cero .

Aquí está nuestra implementación:

public int calculateTreeHeight(BinaryNode root){ if (root!= null) { if (root.getLeft() != null || root.getRight() != null) { return 1 + max(calculateTreeHeight(root.left), calculateTreeHeight(root.right)); } } return 0; }

Por tanto, vemos que algunos problemas se pueden solucionar con recursividad de una forma realmente sencilla.

4. Conclusión

En este tutorial, hemos introducido el concepto de recursividad en Java y lo hemos demostrado con algunos ejemplos simples.

La implementación de este artículo se puede encontrar en Github.