Autor Tema: Diferencia entre recursión con cola (tail recursion) y sin cola Java arrays mín  (Leído 895 veces)

System.out.println(User);

  • Sin experiencia
  • *
  • APR2.COM
  • Mensajes: 7
    • Ver Perfil
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:

Código: [Seleccionar]
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:

Código: [Seleccionar]
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  :)
« Última modificación: 17 de Enero 2021, 20:22 por Ogramar »

Ogramar

  • Moderador Global
  • Experto
  • *******
  • Mensajes: 2645
    • Ver Perfil
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:

Código: [Seleccionar]
//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:

Código: [Seleccionar]
//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

System.out.println(User);

  • Sin experiencia
  • *
  • APR2.COM
  • Mensajes: 7
    • Ver Perfil
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.

 

Sobre la educación, sólo puedo decir que es el tema más importante en el que nosotros, como pueblo, debemos involucrarnos.

Abraham Lincoln (1808-1865) Presidente estadounidense.

aprenderaprogramar.com: Desde 2006 comprometidos con la didáctica y divulgación de la programación

Preguntas y respuestas

¿Cómo establecer o cambiar la imagen asociada (avatar) de usuario?
  1. Inicia sesión con tu nombre de usuario y contraseña.
  2. Pulsa en perfil --> perfil del foro
  3. Elige la imagen personalizada que quieras usar. Puedes escogerla de una galería de imágenes o subirla desde tu ordenador.
  4. En la parte final de la página pulsa el botón "cambiar perfil".