Última actualización：2026-10-12

Recursividad de cola en C++¶

La optimización de la recursividad de cola es una técnica de optimización especial aplicable a funciones recursivas que puede reducir enormemente el espacio de pila que ocupan las llamadas recursivas. Con ella, el compilador puede evitar crear nuevos marcos de pila al ejecutar la recursividad de cola y reutilizar directamente el marco actual, con lo que se reduce el riesgo de desbordamiento de pila y se mejora el rendimiento.

¿Qué es la recursividad de cola?¶

Cuando la llamada recursiva, al retornar, no tiene otras operaciones pendientes que ejecutar, se habla de recursividad de cola. En este caso, el compilador puede sustituir la recursividad por una estructura de bucle, evitando el coste de las múltiples llamadas a funciones.

Ejemplo de recursividad no de cola (sucesión de Fibonacci)¶

La función fibonacci_non_tail() que proporcionas es una implementación estándar no de cola:

int fibonacci_non_tail(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci_non_tail(n - 1) + fibonacci_non_tail(n - 2);
}

En esta implementación, tras las llamadas recursivas fibonacci_non_tail(n - 1) y fibonacci_non_tail(n - 2) aún hay que sumar sus resultados, por lo que no se trata de recursividad de cola. Cada llamada debe guardar información de contexto para continuar el cálculo cuando la recursividad retorne, lo que provoca un crecimiento muy rápido del espacio de pila.

Ejemplo con optimización de recursividad de cola¶

fibonacci_tail() usa el enfoque de recursividad de cola:

int fibonacci_tail_helper(int n, int a, int b) {
    if (n == 0) {
        return a;
    }
    return fibonacci_tail_helper(n - 1, b, a + b);
}

int fibonacci_tail(int n) {
    return fibonacci_tail_helper(n, 0, 1);
}

Aquí fibonacci_tail_helper() es recursividad de cola. Puede verse que tras la llamada recursiva fibonacci_tail_helper(n - 1, b, a + b) la función ya no necesita hacer ningún otro trabajo y retorna directamente el resultado de la llamada recursiva. Por eso la llamada recursiva está en la "cola" de la función: no hay operaciones adicionales que ejecutar después de ella.

Ventajas de la optimización de la recursividad de cola¶

Menor uso del espacio de pila: al no haber que guardar el contexto de las llamadas recursivas, el compilador puede reutilizar el marco de pila y evitar su crecimiento descontrolado.
Prevención del desbordamiento de pila: la optimización permite alcanzar profundidades de recursividad muy grandes sin que se produzca desbordamiento de pila.
Mayor eficiencia: en compiladores que soportan la optimización de la recursividad de cola, su rendimiento se acerca al de la implementación iterativa, eliminando el coste de las llamadas a funciones recursivas.

Prueba de rendimiento¶

Por último, se realizó un benchmark de lo anterior y se comprobó que la optimización de la recursividad de cola resulta muy útil en este escenario: ¡la diferencia de rendimiento es enorme!