Recursividad es el proceso de definir algo en términos desí mismo. Como se relaciona con la programación Java, la recursividad es el atributo que permite que un método se llame a sí mismo. Se dice que un método que se llama a sí mismo es recursivo y Java admite la recursividad.
Al principio esto puede parecer un bucle sin fin,y parece que nuestro método nunca terminará. Esto puede ser cierto en algunos casos, pero en la práctica podemos verificar si cierta condición es verdadera y, en ese caso, salir (volver) de nuestro método. El caso en el que terminamos nuestra recursividad se llama caso base. Además, al igual que en un bucle, debemos cambiar algún valor y avanzar progresivamente más cerca de nuestro caso base.
Cada recursión debe tener las siguientes características:
- Un caso base simple para el que tenemos una solución y un valor de retorno.
- Una forma de acercar nuestro problema al caso base. es decir, una forma de cortar parte del problema para obtener un problema algo más simple.
- Una llamada recursiva que devuelve el problema más simple al método.
Ventajas
Lo principal de los métodos recursivos es que pueden serSe utiliza para crear versiones más claras y simples de varios algoritmos que sus parientes iterativos. Por ejemplo, el algoritmo de ordenación QuickSort es bastante difícil de implementar de forma iterativa.
Desventajas
Las versiones recursivas de muchas rutinas pueden ejecutar unpoco más lento que el equivalente iterativo debido a la sobrecarga agregada de las llamadas a funciones adicionales. Muchas llamadas recursivas a un método pueden causar un desbordamiento de la pila. Debido al almacenamiento de parámetros y variables locales, es posible que la pila se agote. Si esto ocurre, el sistema de tiempo de ejecución de Java provocará una excepción. Sin embargo, probablemente no tendrá que preocuparse por esto a menos que una rutina recursiva se vuelva loca.
Por ejemplo:
int myFactorial(int integer) {
if( integer == 1) {
return 1;
}
else {
return(integer*(myFactorial(integer-1);
}
}La recursividad de la cola se define cuando ocurrela llamada recursiva se encuentra al final de la instrucción recursiva. Este no es el caso con mi solución factorial anterior. Es útil notar cuándo un algoritmo usa la recursión de cola porque en tal caso, el algoritmo generalmente se puede reescribir para usar la iteración en su lugar. De hecho, el compilador convertirá (o al menos debería) el programa recursivo en uno iterativo. Esto elimina el problema potencial del desbordamiento de la pila.
Este no es el caso con la recurrencia de la cabeza, o cuandola función se llama recursivamente en diferentes lugares como en la solución Towers of Hanoi. Por supuesto, incluso en estos casos también podríamos eliminar la recursividad utilizando nuestra propia pila y simulando esencialmente cómo funcionaría la recursividad.
En mi ejemplo de factorial arriba del compiladortendrá que llamar a la función recursiva antes de hacer la multiplicación porque tiene que resolver el valor (retorno) de la función antes de que pueda completar la multiplicación. Por lo tanto, el orden de ejecución será la recursión “principal”, es decir, la recursión ocurre antes de otras operaciones.
Para convertir esto en recursión de cola, necesitamos obtenertoda la multiplicación terminó y se resolvió antes de llamar recursivamente a la función. Necesitamos forzar el orden de operación para que no esperemos la multiplicación antes de regresar. Si hacemos esto, el marco de la pila se puede liberar.
Anteriormente ha visto nuestro programa Java para calcular el factorial de un entero.
La forma correcta de hacer un factorial recursivo de cola es esta:
int factorial(int number) {
if(number == 0) {
return 1;
}
factorial_i(number, 1);
}
int factorial_i(int currentNumber, int sum) {
if(currentNumber == 1) {
return sum;
} else {
return factorial_i(currentNumber - 1, sum*currentNumber);
}
}Tenga en cuenta que en la devolución de llamadafactorial_i (número actual - 1, suma * número actual); Ambos parámetros se pueden resolver de inmediato. Podemos calcular qué es cada parámetro sin esperar a que regrese una llamada de función recursiva. Este no es el caso con la versión anterior de factorial. Esta racionalización permite al compilador minimizar el uso de la pila como se explicó anteriormente.
También puede tomar el número del usuario como argumento de línea de comando.
Programa de recursión de Java
class Factorial{
int fact(int n){
int result;
if ( n ==1)
return 1;
result = fact (n-1) * n;
return result;
}
}
class Recursion{
public static void main (String args[]){
Factorial f =new Factorial();
System.out.println("Factorial of 3 is " + f.fact(3));
System.out.println("Factorial of 4 is " + f.fact(4));
System.out.println("Factorial of 5 is " + f.fact(5));
}
}Salida
Explicación del código y salida de Java
Si no está familiarizado con los métodos recursivos, entonces la operación de hecho() Puede parecer un poco confuso. Así es como funciona. Cuando hecho() se llama con un argumento de 1, la función devuelve 1; de lo contrario, devuelve el producto de hecho (n-1) * n. para evaluar esta expresión, hecho() se llama con n-1. Este proceso se repite hasta norte es igual a 1 y las llamadas al método comienzan a regresar.
Para comprender mejor cómo hecho() el método funciona, veamos un breve ejemplo. Cuando calcula el factorial de 3, la primera llamada a hecho() provocará una segunda llamada con un argumento de 2. Esta invocación provocará hecho() ser llamado por tercera vez con un argumento de 2. Esta llamada devolverá 1, que luego se llamará por tercera vez con un argumento de 1. Esta llamada devolverá 1, que luego se multiplica por 2 (el valor de norte en la segunda invocación). Este resultado (que es 2) se devuelve a la invocación original de hecho() y multiplique por 3 (el valor original de norte). Esto produce la respuesta, 6. Puede que le resulte interesante insertar println () declaraciones en hecho() que mostrará a qué nivel está cada llamada y cuáles son las respuestas intermedias.
Cuando un método se llama a sí mismo, nuevas variables localesy los parámetros se asignan al almacenamiento en la pila, y el código del método se ejecuta con estas nuevas variables desde el principio. Una llamada recursiva no hace una nueva copia del método. Solo los argumentos son nuevos. A medida que regresa cada llamada recursiva, las antiguas variables y parámetros locales se eliminan de la pila y la ejecución se reanuda en el punto de la llamada dentro del método.
A continuación aprenderemos cómo lidiar con Matriz en Java.
Vea más tutoriales útiles y pautas definitivas sobre programación Java aquí.
Comentarios