Ejemplo de recursividad de cola

Para entender cómo funciona la recursividad de cola, calculemos nuevamente el factorial de forma recursiva. En primer lugar, es fácil entender por qué la recursividad definida antes no es una recursividad de cola. ¡Recuerde que calculamos n antes! Definición: ¡calculado n veces (n-1) en cada período activo! valor, sea n = n-1 y continúe este proceso hasta n = 1. Esta definición no es recursiva de cola porque el valor de retorno de cada período de actividad depende del valor de retorno del siguiente período de actividad multiplicado por n, por lo que el marco de pila generado por cada llamada debe permanecer en la pila hasta el regreso de la siguiente subllamada. es el valor determinado. Ahora, consideremos n definido en forma recursiva de cola. proceso de cálculo.

Esta definición acepta un segundo parámetro a, pero por lo demás no hace ninguna diferencia. a (inicializado en 1) mantiene la profundidad del nivel de recursividad. Esto evita la necesidad de multiplicar el valor de retorno por n cada vez, pero hace que a=na y n=n-1 en cada llamada recursiva.

El ejemplo de código 3-2 muestra una función de C facttail que toma un número entero n y calcula el factorial de n en recursividad de cola. facttail usa a para mantener la profundidad de la jerarquía recursiva, pero por lo demás es muy similar a fact. Los lectores pueden notar similitudes entre la implementación concreta de la función y la definición recursiva de cola.

Ejemplo 3-2: Implementación de función para calcular factorial en forma recursiva de cola/*facttail.c*/#includefacttail.h/*facttail*/int?facttail(int?n,?int?a) {/* Calcular factorial en forma recursiva de cola*/if(n?

En primer lugar: la recursividad de cola es un subconjunto de la recursividad lineal y pertenece a la recursividad lineal. Para conceptos específicos, consulte los libros publicados por las principales universidades. El autor se equivocó en este concepto

En segundo lugar, en el segundo ejemplo citado anteriormente, no hay RETURN antes de que se evalúe TailRescuvie(n-1, 1). Esto significa que el proceso recursivo es básicamente el mismo que el primer ejemplo, no ahorra ningún recurso y desperdicia aún más recursos.

De hecho, el compilador optimizará fácilmente la recursión de cola utilizando declaraciones de salto y, de hecho, puede REGRESAR.

La recursividad de cola se refiere a pasar el resultado (o ruta) de la operación actual a la función de nivel inferior en forma de parámetro. La función de nivel profundo no se enfrenta a un problema cada vez más simple, sino a un problema. uno cada vez más complejo. El problema es que los parámetros llevan las rutas de los pasos anteriores. Para los factoriales, más profundo no significa más complejo.

En términos de eficiencia temporal y espacial, la recursividad de cola es casi tan eficiente como la recursividad tradicional. La razón por la que las operaciones recursivas son ineficientes se debe principalmente a las enormes ramas, mientras que las operaciones recursivas de una sola rama, como el factorial, no son ineficientes; La relación entre la profundidad de las operaciones recursivas y el número total de operaciones es aproximadamente exponencial, y los retornos múltiples no causarán pérdidas obvias de rendimiento.

En resumen, cuanto más profunda es la recursividad tradicional, más cerca del objetivo; cuanto más profunda es la recursividad de cola, más se aleja del punto de partida.

La recursividad de cola es adecuada para problemas en los que la operación depende de la ruta de recursividad actual, mientras que la recursividad tradicional es adecuada para problemas en los que la operación depende de una recursividad más profunda.

/****************************************** ************************************************** * ******/

La explicación del segundo autor del segundo ejemplo es algo incompleta. La función de la recursividad de cola es eliminar las deficiencias de devolver los resultados de la capa inferior a la capa superior nuevamente. , Requiere que la capa superior dé Continúe el cálculo antes de obtener el resultado. Si el lector observa atentamente el segundo ejemplo, encontrará que, de hecho, el resultado de cada recursión se almacena en el segundo parámetro a. solo se devolverá el valor de a, pero debido a que es un principio recursivo, aunque aún necesita regresar al nivel superior, a su vez, porque es un principio recursivo, aunque aún necesita regresar al nivel superior para que el resultado se pueda pasar al nivel superior, no es necesario volver a calcularlo. La ventaja de esto es que la memoria no se expandirá debido a la recursividad cada vez que se asigne memoria.

En términos de eficiencia, efectivamente son similares.