informatica - recursividad en java

La diferencia entre recursión de cabeza y cola

Question

Esta pregunta ya tiene una respuesta aquí:

• ¿Qué es la recursión de cola? 26 respuestas

Estoy tratando de obtener la diferencia entre estas 2 estrategias recursivas.

La definición que me dijeron es la siguiente:

Recursión de cola: una llamada es recursiva de cola si no hay que hacer nada después de que se devuelve la llamada, es decir, cuando se devuelve la llamada, el valor devuelto se devuelve inmediatamente de la función de llamada.

Recursión de cabecera: una llamada es recursiva de cabecera cuando la primera declaración de la función es la llamada recursiva.

Answer 1

En la head recursion , la llamada recursiva, cuando ocurre, se produce antes que otro procesamiento en la función (piense que sucede en la parte superior, o cabeza, de la función).

En la tail recursion , es lo contrario: el procesamiento se produce antes de la llamada recursiva. La elección entre los dos estilos recursivos puede parecer arbitraria, pero la elección puede hacer toda la diferencia.

Una función con una ruta con una sola llamada recursiva al comienzo de la ruta usa lo que se llama recursión de cabeza. La función factorial de una exposición anterior utiliza la recursión de la cabeza. Lo primero que hace una vez que determina que se necesita recursión es llamarse a sí mismo con el parámetro decrementado. Una función con una sola llamada recursiva al final de una ruta está utilizando la recursión de cola. Refiera este articulo

Ejemplo de recursión:

public void tail(int n)         |     public void head(int n)
{                               |     {
    if(n == 1)                  |         if(n == 0)
        return;                 |             return;
    else                        |         else
        System.out.println(n);  |             head(n-1);
                                |
    tail(n-1);                  |         System.out.println(n);
}                               |     }

Si la llamada recursiva se produce al final de un método, se denomina tail recursion . La recursión de la cola es similar to a loop . El method executes all the statements before jumping into the next recursive call .

Si la llamada recursiva se produce al beginning of a method, it is called a head recursion . El method saves the state before jumping into the next recursive call .