¿Cuál es la ventaja de usar la recursión de la cola aquí?

Question 1

Una llamada de función recursiva de cola permite al compilador realizar una optimización especial que normalmente no puede con recursión regular. En una función recursiva de cola, la llamada recursiva es lo último que se ejecuta. En este caso, en lugar de asignar un marco de pila para cada llamada, el compilador puede reelaborar el código para simplemente reutilizar el marco de pila actual, lo que significa que una función recursiva de cola solo usará un solo marco de pila en lugar de cientos o incluso miles.

Esta optimización es posible porque el compilador sabe que una vez que se realiza la llamada recursiva de la cola, no se necesitarán copias previas de variables, porque no hay más código para ejecutar. Si, por ejemplo, una declaración de impresión siguió una llamada recursiva, el compilador necesitaría saber el valor de la variable que se imprimirá después de que las llamadas recursivas se devuelvan y, por lo tanto, el marco de la pila no se puede reutilizar.

Aquí está la página Wiki si desea obtener más información sobre cómo funciona este "ahorro de espacio" y la reutilización de la pila, junto con ejemplos: Llamada de cola

EDITAR: No expliqué cómo se aplica esto a QuickSort, ¿verdad? Bueno, algunos términos se lanzan en ese artículo que hacen que todo sea confuso (y algunos de ellos son simplemente incorrectos). La primera función dada (QuickSort) hace una llamada recursiva a la izquierda, una llamada recursiva a la derecha y luego sale. Observe que la llamada recursiva a la derecha es lo último que sucede en la función. Si el compilador admite la optimización recursiva de la cola (explicada anteriormente), solo las llamadas a la izquierda crean nuevos marcos de pila; Todas las llamadas correctas solo reutilizan el marco actual. Esto puede salvar alguno marcos de pila, pero aún puede sufrir el caso en el que la partición crea una secuencia de llamadas donde la optimización de la recursión de la cola no importa. Además, a pesar de que las llamadas del lado derecho usan el mismo cuadro, las llamadas del lado izquierdo llamaron dentro de Las llamadas del lado derecho todavía usan la pila. En el peor de los casos, la profundidad de la pila es N.

La segunda versión descrita es no Una rápida cola recursiva, sino una rápida que solo la clasificación izquierda se realiza de manera recursiva, y la clasificación correcta se realiza usando el bucle. De hecho, este QuickSort (como lo describió anteriormente otro usuario) no puede tener la optimización de la recursión de la cola aplicada a ella, porque la llamada recursiva no es lo último que se ejecuta. ¿Como funciona esto? Cuando se implementa correctamente, la primera llamada a QuickSort es la misma que una llamada del lado izquierdo en el algoritmo original. Sin embargo, no se llaman llamadas recursivas del lado derecho. ¿Como funciona esto? Bueno, el bucle se encarga de eso: en lugar de clasificar "a la izquierda y luego a la derecha", clasifica la izquierda con una llamada, luego clasifica la derecha clasificando continuamente solo solo el Lefts de la derecha. Es realmente ridículo sonar, pero básicamente es solo clasificar tantas izquierdas que los derechos se convierten en elementos individuales y no necesitan ser ordenados. Esto elimina efectivamente la recursión correcta, lo que hace que la función sea menos recursiva (pseudo recursiva, si lo desea). Sin embargo, la implementación real no elige solo el lado izquierdo cada vez; Elige el lado más pequeño. La idea sigue siendo la misma; Básicamente solo hace una llamada recursiva en un lado en lugar de ambos. Recoger el lado más corto asegurará que la profundidad de la pila nunca pueda ser más grande que Log2 (N), que es la profundidad de un árbol binario adecuado. Esto se debe a que el lado más corto siempre será como máximo la mitad del tamaño de nuestra sección de matriz actual. Sin embargo, la implementación dada por el artículo no garantiza esto, ya que puede sufrir el mismo peor de los casos de "la izquierda es todo el árbol". Este artículo realmente da una buena explicación si está dispuesto a leer más: Selección eficiente y clasificación parcial basada en QuickSort

Question 2

La ventaja, el punto completo de la versión "mixta recursiva/iterativa", es decir, la versión que procesa un subcon-range por recursión y otro subcande por iteración, es que al elegir cuáles de los dos subcanjes se pueden procesar de manera recursiva. garantizar que la profundidad de la recursión nunca excederá log2 N, Independientemente de lo mala que sea la elección de pivote.

Para el TAIL-RECURSIVE-QUICKSORT seudocódigo proporcionado en la pregunta, donde el procesamiento recursivo se realiza primero mediante una llamada recursiva literal, que la llamada recursiva debe recibir la corto subconocente. Que por sí solo se asegurará de que la profundidad de recursión esté limitada por log2 N. Por lo tanto, para lograr la profundidad de recursión, la garantía de que el código tenga absolutamente comparar las longitudes de los subcanaces antes de decidir qué subconma procesar mediante una llamada recursiva.

Una implementación adecuada de ese enfoque puede verse de la siguiente manera (tomar prestado su pseudocódigo como punto de partida)

HALF-RECURSIVE-QUICKSORT(A, p, r)
   while p < r
      q = PARTITION(A, p, r)
      if (q - p < r - q)
        HALF-RECURSIVE-QUICKSORT(A, p, q-1)
        p = q+1
      else
        HALF-RECURSIVE-QUICKSORT(A, q+1, r)
        r = q-1

los TAIL-RECURSIVE-QUICKSORT El pseudocódigo que proporcionó no hace ningún intento de comparar las longitudes de los subcanjes. En tal caso, no proporciona ningún beneficio. Y no, no es realmente "recursivo de la cola". Quicksort no puede reducirse a un algoritmo recursivo de la cola.

Si realiza una búsqueda en Google en los términos "Qsort loguy Higuy", encontrará fácilmente numerosos casos de otra implementación popular de Quicksort (estilo de biblioteca estándar) basado en la misma idea de usar recursión solo para una de las dos subconjoces . Esa implementación para plataformas de 32 bits utiliza una pila explícita de profundidad máxima de ~ 32 específicamente porque puede garantizar que la profundidad de recursión nunca será más alta que eso. (Del mismo modo, las plataformas de 64 bits solo necesitarán una profundidad de pila de ~ 64).

los QUICKSORT La versión que realiza dos llamadas recursivas literal es significativamente peor en ese sentido, ya que la mala elección repetitiva de pivote puede hacer que alcance una profundidad de recursión muy alta, hasta N En el peor de los casos. Con dos llamadas recursivas, no puede garantizar que la profundidad de la recursión esté limitada por log2 N. Un compilador inteligente podría reemplazar la llamada a la baja a QUICKSORT con iteración, es decir, gira tu QUICKSORT en tu TAIL-RECURSIVE-QUICKSORT, pero no será lo suficientemente inteligente como para realizar la comparación de longitud de subcan-rango.

Question 3

Ventaja de usar la recursión de la cola: = para que el compilador optimice el código y lo convierta a un código no recursivo.

La ventaja del código no recursivo sobre uno recursivo: = El código no recursivo requiere menos memoria para ejecutar que uno recursivo. Esto se debe a los marcos de pila inactiva que consume la recursión.

Aquí viene la parte interesante:- Aunque los compiladores pueden Teórico realizar esa optimización, en la práctica no. Incluso los compiladores generalizados como Dot-Net y Java no realizan esa optimización.

Un problema que enfrentan todas las optimizaciones de código es el sacrificio en la capacidad de depuración. El código optimizado ya no corresponde al código fuente, por lo que las trazas de pila y los detalles de excepción no se pueden entender fácilmente. El código de alto rendimiento o las aplicaciones científicas son una cosa, pero para la mayoría de las aplicaciones de consumo se requiere la depuración incluso después del lanzamiento. Por lo tanto, las optimizaciones no se hacen enérgicamente.

por favor mira:

Question 4

Parece que hay una confusión de vocabulario aquí.

La primera versión es recursiva de la cola, porque la última declaración es una llamada recursiva:

QUICKSORT(A, p, r)
  q = PARTITION(A, p, r)
  QUICKSORT(A, p, q-1)
  QUICKSORT(A, q+1, r)

Si aplica la optimización de la recursión de la cola, que es convertir la recursión en un bucle, obtiene la segunda, que ya no es recursiva de la cola:

TAIL-RECURSIVE-QUICKSORT(A, p, r)
  while p < r
    q = PARTITION(A, p, r)
    TAIL-RECURSIVE-QUICKSORT(A, p, q-1)
    p = q+1

El beneficio de esto es que generalmente necesitará menos memoria de pila. ¿Porqué es eso? Para entender, imagine que desea ordenar una matriz con 31 artículos. En el caso altamente improbable de que todas las particiones sean perfectas, es decir, dividen la matriz justo en el medio, su profundidad de recursión sería 4. De hecho, la primera división produciría dos particiones de 15 elementos, la segunda dos particiones de 7 elementos, El tercero uno de los dos de 3 elementos, y después del cuarto todo está ordenado.

Pero las particiones rara vez son tan perfectas. Como resultado, no todas las recursiones son igualmente profundas. En nuestro ejemplo, puede tener algunos que tienen solo tres niveles de profundidad y algunos que son 7 o más (el peor de los casos es 30). Al eliminar la mitad de las recursiones, tiene una oportunidad justa de que su profundidad de recursión máxima sea menor.

Como señaló Andreyt, a menudo se comparan los rangos para asegurarse de que la partición más grande siempre se procese de forma iterativa y la más pequeña recursivamente. Eso garantiza la profundidad de recursión más pequeña posible para una estrategia de selección de entrada y pivote dada.

Pero este no siempre es el caso. A veces, las personas quieren obtener resultados lo antes posible, o quieren encontrar y ordenar solo los primeros n elementos. En estos casos, siempre quieren ordenar la primera partición antes de la segunda. Incluso en esta situación, eliminar la recursión de la cola generalmente mejora el uso de la memoria y nunca lo empeora.

Question 5

No sé exactamente si este es el lugar correcto para hacer esta duda o debería haber publicado una nueva pregunta, pero tengo una duda bastante similar.



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

¿Es esta cola recursiva?

Question 6

La recursión de la cola es la optimización realizada por los compiladores modernos llamados eliminación de llamadas de cola. Cuando la función de la persona que llama/principal no tiene que hacer nada en las etapas de relajación después de que las llamadas de los niños hayan terminado, lo último es la llamada de recursión en sí misma, entonces el compilador moderno usa el GoTo y las etiquetas para la optimización.

Ejemplo: Nuestra versión -> Imprime N a 1

void fun(int n){
if(n==0)
return;
printf("%d\n",n);
fun(n-1)
}

Después de la optimización->

void fun(int n){
start:
if(n==0)
return;
printf("%d\n",n);
n=n-1;
goto start;
}

Ventajas de esta optimización: 1. Utiliza muy pocos marcos de pila para llamadas recursivas de la cola 2.Consume menos memoria 3.No necesita guardar el registro de activación del procedimiento, esto reduce la sobrecarga de la función. 3. No más falla de segmentación es C/C ++ y el desbordamiento de la pila en Java.