Eliminación de llamadas de cola

Hemos discutido (en recursión de cola ) que una función recursiva es recursiva de cola si la llamada recursiva es lo último que ejecuta la función. 

// An example of tail recursive function
void print(int n)
{
    if (n < 0) 
       return;
    cout << " " << n;
 
    // The last executed statement is recursive call
    print(n-1);
}

// An example of tail recursive function
static void print(int n)
{
    if (n < 0) 
       return;
       
      System.out.print(" " + n);
 
    // The last executed statement
    // is recursive call
    print(n - 1);
}
 
// This code is contributed by rutvik_56

# An example of tail recursive function
def print(n):
     
    if (n < 0):
       return
    
    print(" ", n)
  
    # The last executed statement is recursive call
    print(n - 1)
 
# This code is contributed by sanjoy_62

// An example of tail recursive function
static void print(int n)
{
    if (n < 0) 
       return;
       
      Console.Write(" " + n);
 
    // The last executed statement
    // is recursive call
    print(n - 1);
}
 
// This code is contributed by pratham76

<script>
 
 
// An example of tail recursive function
function print(n)
{
    if (n < 0) 
       return;
    document.write( " " + n);
 
    // The last executed statement is recursive call
    print(n-1);
}
 
 
</script>

También discutimos que una cola recursiva es mejor que una no cola recursiva ya que los compiladores modernos pueden optimizar la cola recursiva. El compilador moderno básicamente realiza la eliminación de llamadas de cola para optimizar el código recursivo de cola . 

Si echamos un vistazo más de cerca a la función anterior, podemos eliminar la última llamada con goto. A continuación se muestran ejemplos de eliminación de llamadas de cola.

// Above code after tail call elimination
void print(int n)
{
start:
    if (n < 0)
       return;
    cout << " " << n;
 
    // Update parameters of recursive call
    // and replace recursive call with goto
    n = n-1
    goto start;
}

QuickSort : un ejemplo más 
QuickSort también es recursivo de cola (tenga en cuenta que MergeSort no es recursivo de cola, esta es también una de las razones por las que QuickSort funciona mejor) 

/* Tail recursive function for QuickSort
 arr[] --> Array to be sorted,
  low  --> Starting index,
  high  --> Ending index */
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[p] is now
           at right place */
        int pi = partition(arr, low, high);
 
        // Separately sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
// See below link for complete running code
// http://geeksquiz.com/quick-sort/

/* Java program to implement the above approach
 
   Tail recursive function for quick sort
   arr[] --> to get the elements
   low --> starting index
   high --> ending index
*/
static void quickSort(int[] arr, int low, int high)
{
    if (low < high)
    {
        /* pi is partitioning index,after the call
        to partition function the arr[p] will be
        at its correct index*/
        int pi = partition(arr, low, high);
 
        // Sort elements before and after
        // the partition separately
        // thus whole array will get sorted eventually
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
 
// This code was contributed by Abhijeet Kumar

// C# program to implement
// the above approach
using System;
 
class GFG{
     
 
/* Tail recursive function for QuickSort
 arr[] --> Array to be sorted,
  low  --> Starting index,
  high  --> Ending index */
static void quickSort(int[] arr, int low, int high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[p] is now
           at right place */
        int pi = partition(arr, low, high);
  
        // Separately sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
}
 
// This code is contributed by code_hunt.

La función anterior se puede reemplazar siguiendo después de la eliminación de llamadas de cola. 

/* QuickSort after tail call elimination
  arr[] --> Array to be sorted,
  low  --> Starting index,
  high  --> Ending index */
void quickSort(int arr[], int low, int high)
{
start:
    if (low < high)
    {
        /* pi is partitioning index, arr[p] is now
           at right place */
        int pi = partition(arr, low, high);
 
        // Separately sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
 
        // Update parameters of recursive call
        // and replace recursive call with goto
        low = pi+1;
        high = high;
        goto start;
    }
}
// See below link for complete running code
// https://ide.geeksforgeeks.org/dbq4yl

Por lo tanto, el trabajo de los compiladores es identificar la recursividad final, agregar una etiqueta al principio y actualizar los parámetros al final, seguido de agregar la última instrucción goto.

Gestión de marcos de pila de funciones en Tail Call Elimination: 
Recursion utiliza una pila para realizar un seguimiento de las llamadas de función. Con cada llamada de función, se inserta un nuevo marco en la pila que contiene variables locales y datos de esa llamada. Digamos que un marco de pila requiere O (1), es decir, espacio de memoria constante, entonces para N memoria de llamada recursiva requerida sería O (N). 

La eliminación de llamadas de cola reduce la complejidad espacial de la recursividad de O(N) a O(1). A medida que se elimina la llamada a la función, no se crean nuevos marcos de pila y la función se ejecuta en un espacio de memoria constante. 

Es posible que la función se ejecute en un espacio de memoria constante porque, en la función recursiva de cola, no hay declaraciones después de la declaración de llamada, por lo que no es necesario preservar el estado y el marco de la función principal. Se llama a la función secundaria y finaliza de inmediato, no tiene que devolver el control a la función principal. 

Como no se realiza ningún cálculo en el valor devuelto y no quedan declaraciones para su ejecución, el marco actual se puede modificar según los requisitos de la llamada de función actual. Por lo tanto, no hay necesidad de conservar marcos de pila de llamadas a funciones anteriores y ejecuciones de funciones en un espacio de memoria constante. Esto hace que la recursión de la cola sea más rápida y amigable con la memoria.

Artículo siguiente:  
QuickSort Tail Call Optimization (reducción del espacio en el peor de los casos para iniciar sesión)
Este artículo es una contribución de Dheeraj Jain . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.