Foros aprenderaprogramar.com
Aprender a programar => C, C++, C#, Java, Visual Basic, HTML, PHP, CSS, Javascript, Ajax, Joomla, MySql y más => Mensaje iniciado por: System.out.println(User); en 09 de Noviembre 2020, 17:20
-
Muy buenas. El otro día se me pidió un ejercicio, en el que debía realizar un método que devolviese el número más pequeño dentro de un array, llamando a dicha función desde el bloque main y pudiendo emplear la función Math.min. Además, tenía que hacerlo mediante recursión de cola (tail recursion).
Entrego a la profesora dicho código:
static int minArrayRecursiva1 (int[] arr)
{
return minArrayAux1 (arr, 0);
}
static int minArrayAux1 (int[] arr, int ind)
{
if (ind == arr.length - 1)
{
return arr[ind];
}
else
{
return Math.min (arr[ind], minArrayAux1 (arr, ind + 1));
}
}
Pero, mi sorpresa fue cuando me dijo que el código era correcto, pero la recursión empleada era sin cola. Y me enseña su versión del código:
static int minArrayRecursiva2 (int[] arr)
{
return minArrayAux2 (arr, 1, arr[0]);
}
static int minArrayAux2 (int[] arr, int ind, int min)
{
if (ind == arr.length)
{
return min;
}
else
{
return minArrayAux2 (arr, ind + 1, Math.min (min, arr[ind]));
}
}
Dado esto, claramente no he comprendido muy bien el concepto de recursión de cola y sin cola. Me lo explicaron con el "clásico" ejemplo de calcular el factorial de un número, pero aplicado a este método, no lo veo muy claro.
Yo tenía entendido que una recursión es de cola si se emplea un método auxiliar o mediante 'wrapping', para que la última llamada del método "principal" sea a sí misma.
Agradecería si alguien me pudiese aclarar este concepto y su aplicación.
¡Gracias!
Un saludo :)
-
Buenas, he estado mirando este tema y lo interpreto como expongo a continuación.
Un ejemplo de recursión de cola típico es el cálculo del GCD (Greatest common divisor) o Máximo común divisor:
//Entrada: Los enteros x e y, de forma que x >= y e y > 0
int gcd(int x, int y)
{
if (y == 0)
return x;
else
return gcd(y, x % y);
}
Y un ejemplo de recursión incremental o no de cola sería el cálculo del factorial de un número:
//Entrada: n es un entero de forma que n >= 1
int fact(int n)
{
if (n == 1)
return 1;
else
return n * fact(n - 1);
}
<<Funciones de recursión de cola son funciones que finalizan con una llamada recursiva que no crea ninguna operación deferida.>>
En el caso del GCD, la construcción se forma llamando repetidamente a la función GCD, pero no queda ninguna operación pendiente de realizarse una vez se llegue al caso base. Cuando se llega al caso base, se devuelve la solución y se termina la recursión.
En el caso del factorial, la construcción se forma llamando a una operación: n * fact(n - 1). En cada recursión, no se conoce el fact(n-1), por lo que queda una operación pendiente de realizarse. Cuando se llega al caso base, se devuelve el factorial de 1 que es 1, y a partir de ahí hay que ir rehaciendo resultados hacia atrás que habían quedado pospuestos debido a que no se podían calcular.
Salu2
-
Muchas gracias por tu respuesta, Ogramar.
Con los ejemplos que has puesto, ya lo veo mucho mejor. Justo eso que has comentado, lo de la última llamada y las operaciones pendientes, era lo que me confundía.
Un saludo.