Recursividad de cola en C++

Question

¿Puede alguien mostrarme una función recursiva simple en C++?

¿Por qué es mejor la recursividad de cola, si es que incluso es?

¿Qué otros tipos de recursión existen además de la recursividad de cola?

Answer 1

Un simple cola función recursiva:

unsigned int f(unsigned int a) { 
    if (a == 0) { 
     return a; 
    } 
    return f(a - 1); // tail recursion 
} 

cola recursividad es básicamente cuando:

• sólo hay una única llamada recursiva
• que llama es la última instrucció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.

Answer 2

Tail recusion en C++ tiene el mismo aspecto que C o cualquier otro idioma.

void countdown(int count) { 
    if (count) return countdown(count - 1); 
} 

recursión de cola (cola y llamando en general) requiere despejar 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 a trabajar 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 bucle o goto es generalmente 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 instrucción 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 repetición 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); 
} 

Answer 3

cola recursividad no existe realmente en el nivel del compilador en C++.

Aunque puede escribir programas que utilizan recursividad final, no obtiene los beneficios heredados de la repetición de cola 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. (al menos, ningún compilador que haya visto)

Parece que existen optimizaciones de recurrencia de cola tanto en MSVC++ como en GCC. Ver this question para más detalles.

Answer 4

Wikipedia has a decent article on tail recursion. 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 se pueden optimizar mejor, pero en tales casos, en general puede hacerlo iterativamente en primer lugar, por lo que la ganancia no es tan alta genial como sería en un lenguaje funcional.

Answer 5

recursividad 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 reparació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 cosas buenas de esto 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.

recursividad de cola es donde 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 se convierta en un bucle:

int sum(int a[], unsigned len) { 
    if (len==0) { 
     return 0; 
    } 
    return a[0] + sum(a+1,len-1); 
} 

Esto es bastante simple que muchos compiladores probablemente podría averiguarlo todos modos, pero como puede ver, hay una adición que debe suceder después de que el retorno de la suma llamada devuelve un número, por lo que no es posible una optimización de la cola de cola simple.

Si lo hizo:

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 sería capaz de tomar ventaja de las llamadas en ambas funciones son 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 al respecto. C++ oculta algunas cosas de usted que C no tiene. 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 tiene que ser destruido después del regreso de Baz. Creo que las reglas de C++ pueden hacer que la optimización más difícil aún en los casos donde no es necesaria la variable durante la duración de la llamada, tales como:

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ícita, que también puede ocurrir en C, pero puede ser más complicado y común en C++. Por ejemplo: llamada

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í suma de a sum_helper no es una llamada de cola porque sum_helper devuelve una suma doble y tendrá que convertir esto en un int.

En C++ es bastante común para devolver una referencia de objeto que puede tener todo tipo de interpretaciones diferentes, cada uno de los cuales podría ser una conversión de tipo diferente, Por ejemplo:

bool write_it(int it) { 
     return cout << it; 
} 

Aquí hay una llamada hecho para cout.operator < < como la última declaración. cout devolverá una referencia a sí mismo (que es por lo que puede unir muchas cosas en una lista separada por < <), que luego forzará a ser evaluado como un bool, que termina llamando a otro de los métodos de cout, bool operador () Este cout.operator bool() podría llamarse como una llamada final en este caso, pero el operador < < no pudo.

EDIT:

Una cosa que vale la pena mencionar es que una de las principales razones que la optimización de llamada de cola en C es posible es que el compilador sabe que la función llamada almacenará su valor de retorno en el mismo lugar que el que llama función tendría que asegurarse de que su valor de retorno se almacena en.

Answer 6

Recurrencia de cola es un truco para hacer frente a 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 se puede resolver 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, usted aprenderá que un algoritmo de computadora necesita tener una condición de terminación invariante y. Esta es la base para construir la recursividad de cola.

1. Todo el cálculo ocurre en el paso del argumento.
2. Todos los resultados se deben pasar a las llamadas a funciones.
3. La llamada final es la última llamada y se produce al finalizar.

Para decirlo simplemente, ningún cálculo debe suceder en el valor de retorno de la función.

Tomemos por ejemplo el cálculo de una potencia de 10, que es trivial y puede escribirse mediante un bucle.

debería ser algo como

template<typename T> T pow10(T const p, T const res =1) 
{ 
return p ? res: pow10(--p,10*res); 
} 

Esto da una ejecución, e.g 4:

ret, p, res

-, 4,1

-, 3,10

-, 2100

-, 1,1000

-, 0,10000

10000, -, -

Está claro que el compilador solo tiene que copiar los valores sin cambiar el puntero de la pila y cuando la última llamada ocurre solo para devolver el resultado.

La recursividad de cola es muy importante porque puede proporcionar evaluaciones de tiempo de compilación ya preparadas, p. Lo anterior puede hacerse.

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; 
} 

}; 

este puede ser utilizado 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.