Mostrar Mensajes
61
C, C++, C#, Java, Visual Basic, HTML, PHP, CSS, Javascript, Ajax, Joomla, MySql y más / Re: Diferencia entre recursión con cola (tail recursion) y sin cola Java arrays mín
« en: 17 de Enero 2021, 20:36 »
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:
Y un ejemplo de recursión incremental o no de cola sería el cálculo del factorial de un número:
<<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
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
RSS