pilas - Recursividad de la cola en C++
recursividad pilas y colas (6)
La recisión de la cola en C ++ tiene el mismo aspecto que C o cualquier otro idioma.
void countdown( int count ) {
if ( count ) return countdown( count - 1 );
}
La recursividad de cola (y la llamada de cola en general) requiere borrar el marco de pila de la persona que llama antes de ejecutar la llamada de cola. Para el programador, la recursividad de cola es similar a un ciclo, con return reducido para funcionar como goto first_line; . Sin embargo, el compilador necesita detectar lo que estás haciendo, y si no lo hace, todavía habrá un marco de pila adicional. La mayoría de los compiladores lo admiten, pero escribir un loop o goto suele ser más fácil y menos arriesgado.
Las llamadas de cola no recursivas pueden permitir la ramificación aleatoria (como goto a la primera línea de alguna otra función), que es una instalación más única.
Tenga en cuenta que en C ++, no puede haber ningún objeto con un destructor no trivial en el alcance de la declaración de return . La limpieza del final de la función requeriría que el destinatario vuelva a la persona que llama, eliminando la llamada final.
También tenga en cuenta (en cualquier idioma) que la recurrencia de cola requiere que todo el estado del algoritmo pase a través de la lista de argumentos de función en cada paso. (Esto se desprende del requisito de que el marco de pila de la función se elimine antes de que comience la siguiente llamada ... no se pueden guardar datos en variables locales). Además, no se puede aplicar ninguna operación al valor de retorno de la función antes de devolverla .
int factorial( int n, int acc = 1 ) {
if ( n == 0 ) return acc;
else return factorial( n-1, acc * n );
}
¿Puede alguien mostrarme una función recursiva simple en C ++?
¿Por qué es mejor la recursividad de cola, si es que es?
¿Qué otros tipos de recursión existen además de la recursividad de la cola?
La recurrencia de cola es un caso especial de una llamada de cola. Una llamada de cola es donde el compilador puede ver que no hay operaciones que deban realizarse al regresar de una función llamada, esencialmente convirtiendo el retorno de la función llamada en su propia cuenta. El compilador a menudo puede hacer algunas operaciones de corrección de pila y luego saltar (en lugar de llamar) a la dirección de la primera instrucción de la función llamada .
Una de las mejores cosas al respecto, además de eliminar algunas llamadas de devolución, es que también se reduce el uso de la pila. En algunas plataformas o en el código del sistema operativo, la pila puede ser bastante limitada y en máquinas avanzadas como las CPU x86 en nuestros equipos de escritorio, la disminución del uso de la pila de esta manera mejorará el rendimiento de la memoria caché de datos.
La recursividad de cola es cuando la función llamada es la misma que la función de llamada. Esto se puede convertir en bucles, que es exactamente lo mismo que el salto en la optimización de la llamada final mencionada anteriormente. Como esta es la misma función (llamada y llamada), hay menos correcciones de pila que deben realizarse antes del salto.
A continuación, se muestra una forma común de hacer una llamada recursiva, que sería más difícil para un compilador convertirse en un bucle:
int sum(int a[], unsigned len) {
if (len==0) {
return 0;
}
return a[0] + sum(a+1,len-1);
}
Esto es tan simple que muchos compiladores probablemente podrían resolverlo de todos modos, pero como puede ver, hay una adición que debe ocurrir después de que el retorno de la suma llamada devuelve un número, por lo que no es posible una optimización simple de la cola.
Si lo hiciste:
static int sum_helper(int acc, unsigned len, int a[]) {
if (len == 0) {
return acc;
}
return sum_helper(acc+a[0], len-1, a+1);
}
int sum(int a[], unsigned len) {
return sum_helper(0, len, a);
}
Usted podría aprovechar las llamadas en ambas funciones siendo llamadas de cola. Aquí el trabajo principal de la función suma es mover un valor y borrar una posición de registro o pila. El sum_helper hace todos los cálculos.
Como mencionó C ++ en su pregunta, mencionaré algunas cosas especiales sobre eso. C ++ esconde algunas cosas de ti que C no oculta. De estos destructores son lo principal que se interpondrá en el camino de la optimización de la cola de llamadas.
int boo(yin * x, yang *y) {
dharma z = x->foo() + y->bar();
return z.baz();
}
En este ejemplo, la llamada a baz no es realmente una llamada de cola porque z debe ser destruida después del regreso de baz. Creo que las reglas de C ++ pueden dificultar la optimización incluso en los casos en que la variable no se necesita para la duración de la llamada, como por ejemplo:
int boo(yin * x, yang *y) {
dharma z = x->foo() + y->bar();
int u = z.baz();
return qwerty(u);
}
z puede tener que ser destruido después del regreso de qwerty aquí.
Otra cosa sería la conversión de tipo implícito, que también puede ocurrir en C, pero puede ser más complicado y común en C ++. Por ejemplo:
static double sum_helper(double acc, unsigned len, double a[]) {
if (len == 0) {
return acc;
}
return sum_helper(acc+a[0], len-1, a+1);
}
int sum(double a[], unsigned len) {
return sum_helper(0.0, len, a);
}
Aquí, la llamada de suma a sum_helper no es una llamada final porque sum_helper devuelve un doble y la suma tendrá que convertir eso en un int.
En C ++ es bastante común devolver una referencia de objeto que puede tener todo tipo de interpretaciones diferentes, cada una de las cuales podría ser una conversión de tipo diferente, por ejemplo:
bool write_it(int it) {
return cout << it;
}
Aquí hay una llamada hecha a cout.operator << como la última declaración. cout devolverá una referencia a sí mismo (por lo que puede unir muchas cosas juntas en una lista separada por <<), que luego forzará a que se evalúe como bool, lo que termina llamando a otro de los métodos de cout, operator bool ( ) Este cout.operator bool () podría llamarse como una llamada final en este caso, pero el operador << no pudo.
EDITAR:
Una cosa que vale la pena mencionar es que una de las principales razones de que la optimización de la cola de llamada en C es posible es que el compilador sabe que la función llamada almacenará su valor de retorno en el mismo lugar donde la función llamante debería asegurarse de que su valor de retorno sea guardado en.
La recursividad de cola es un truco para lidiar con dos problemas al mismo tiempo. El primero es ejecutar un ciclo cuando es difícil saber el número de iteraciones que se deben realizar.
Aunque esto puede resolverse con recursión simple, surge el segundo problema, que es el del desbordamiento de pila debido a que la llamada recursiva se ejecuta demasiadas veces. La llamada final es la solución, cuando se acompaña de una técnica de "cálculo y transporte".
En CS básica, aprende que un algoritmo de computadora necesita tener una condición invariante y de terminación. Esta es la base para construir la recursividad de cola.
- Toda la computación ocurre en el argumento que pasa.
- Todos los resultados deben pasar a las llamadas a funciones.
- La llamada final es la última llamada y ocurre al finalizar.
Para decirlo simplemente, no debe haber ningún cálculo en el valor de retorno de su función .
Tomemos, por ejemplo, el cálculo de una potencia de 10, que es trivial y puede escribirse mediante un bucle.
Debería verse algo así como
template<typename T> T pow10(T const p, T const res =1)
{
return p ? res: pow10(--p,10*res);
}
Esto le da una ejecución, por ejemplo 4:
ret, p, res
-, 4,1
-, 3,10
-, 2,100
-, 1,1000
-, 0,10000
10000, -, -
Está claro que el compilador solo tiene que copiar valores sin cambiar el puntero de la pila y cuando la llamada final ocurre solo para devolver el resultado.
La recursividad de cola es muy importante porque puede proporcionar evaluaciones de tiempo de compilación ya preparadas, por ejemplo, lo anterior se puede hacer para ser.
template<int N,int R=1> struct powc10
{
int operator()() const
{
return powc10<N-1, 10*R>()();
}
};
template<int R> struct powc10<0,R>
{
int operator()() const
{
return R;
}
};
esto se puede usar como powc10<10>()() para calcular la décima potencia en tiempo de compilación.
La mayoría de los compiladores tienen un límite de llamadas anidadas, por lo que ayuda el truco de la cola. Evidentemente, no hay bucles de metaprogramación, por lo que debemos recurrir a la recursión.
Una función recursiva de cola simple:
unsigned int f( unsigned int a ) {
if ( a == 0 ) {
return a;
}
return f( a - 1 ); // tail recursion
}
La recursividad de cola es básicamente cuando:
- solo hay una sola llamada recursiva
- esa llamada es la última declaración en la función
Y no es "mejor", excepto en el sentido de que un buen compilador puede eliminar la recursión, transformándola en un bucle. Esto puede ser más rápido y seguramente ahorrará en el uso de la pila. El compilador de GCC puede hacer esta optimización.
Wikipedia tiene un artículo decente sobre la recursividad de la cola . Básicamente, la recursividad de cola es mejor que la recursión regular porque es trivial optimizarla en un ciclo iterativo, y los ciclos iterativos son generalmente más eficientes que las llamadas a funciones recursivas. Esto es particularmente importante en los lenguajes funcionales donde no tiene bucles.
Para C ++, sigue siendo bueno si puede escribir sus bucles recursivos con recursividad de cola, ya que pueden optimizarse mejor, pero en tales casos, en general puede hacerlo iterativamente en primer lugar, por lo que la ganancia no es tan grande como lo haría. estar en un lenguaje funcional.
La recursividad de cola no existe realmente en el nivel del compilador en C ++.
Aunque puede escribir programas que utilizan la recursividad final, no obtiene los beneficios heredados de la recursión final implementada mediante el soporte de compiladores / intérpretes / idiomas. Por ejemplo, Scheme admite una optimización de recursividad de cola para que básicamente cambie la recursión en iteración. Esto hace que sea más rápido e invulnerable para acumular desbordamientos. C ++ no tiene tal cosa. (Por lo menos, ningún compilador que haya visto)
Aparentemente, las optimizaciones de recurrencia de cola existen tanto en MSVC ++ como en GCC. Vea esta pregunta para más detalles.