La recursividad es una técnica de programación que consiste en que una serie de instrucciones se repiten como una subtarea de la tarea principal, es decir, las funciones, procesos o rutinas se llaman a sí mismos cada vez que lo requieran y se ejecutan repetidas veces hasta que se satisface una condición específica.
Sin embargo, la recursividad en algunos casos, tiene un costo computacional alto, debido a las constantes llamadas a la misma función, rutina y muchas veces estas llamadas consumen demasiada memoria.
En algunos algoritmos recursivos, se puede implementar un caso de recursividad especial llamado Tail Recursion (recursividad por cola), la cual es una técnica para optimizar la recursividad eliminando las constantes llamadas recursivas. Tail recursion es cuando la llamada recursiva es la última instrucción de la función.
Sin embargo, las funciones tail recursive deben cumplir la condición que en la parte que realiza la llamada a la función, no debe existir ninguna otra sentencia.
Una ventaja de la recursividad por cola es que podemos evitar la sobrecarga de cada llamada a la función y nos evitamos el gasto de memoria de pila. Con una función tail recursive se puede evitar lo que se conoce como stack overflow, que ocurre cuando la pila de llamadas (call stack) consume mucha memoria.
Veamos esta técnica con un ejemplo muy conocido que es encontrar el factorial de un número.
Esta simple función obtiene el factorial de un número de la manera recursiva convencional: La explicación es sencilla, llamamos a la misma función fact hasta que n sea igual a 1, en ese momento la recursividad se detiene.
int fact_recursivo(int n)
{
if(n == 1)
return n;
else
return n * fact_recursivo(n-1);
}
int main() {
int num=0;
cout << "Ingresa un nro " << endl; cin >> num;
cout << "Su factorial es " << fact_recursivo(num);
return 0;
}
Digamos que ingresé 15, si compilamos el programa la función me daría 2004310016, lo cual es correcto, pero hay que tener en cuenta todas las llamadas recursivas que hizo la función fact_recursivo, es decir, la función tiene que calcular el factorial de 14 y este el fact de 13, y este el fact de 12… sucesivamente hasta 1. Tenemos un crecimiento del número de llamadas recursivas.
Ahora vamos a realizar la misma función usando tail recursion. En este caso no se necesita guardar un marco de pila para cada llamada recursiva, y el algoritmo se comporta como si fuera iterativo.
Para conseguir esto usamos un parámetro adicional que actúa como acumulador.
Esta sería la función factorial con tail recursion:
//function factorial con tail recursion
int fact_tail_sum(int n, int sum) {
if(n == 1) {
return sum;
} else {
return fact_tail_sum(n - 1, sum*n);
}
}
//para mantener la sintaxis original de como se llama a la función factorial
int fact_tail(int n) {
return fact_tail_sum(n, 1);
}
int main() {
int num=0;
cout << "Ingresa un nro " << endl; cin >> num;
cout << "Su factorial es " << fact_tail(num);
return 0;
}
El resultado igualmente sería 2004310016, pero el costo computacional baja drásticamente debido a que cuando se hace la llamada return fact_tail_sum(n – 1, sum*n) ambos parámetros son inmediatamente resueltos. Con esta llamada podemos calcular sin esperar una llamada a una función recursiva para que nos devuelva un valor.
En este caso el compilador reduce drásticamente el uso de la pila y la cantidad de información que debe ser almacenada, el valor de n y sum es independiente del número de llamadas recursivas.
Una función recursiva normal se puede convertir a tail recursive usando en la función original un parámetro adicional, usado para ir guardando un resultado de tal manera que la llamada recursiva ya no tiene una operación pendiente.
También se usa una función adicional para mantener la sintaxis de como llamamos normalmente a la función. En el caso del factorial, para seguir llamando a la función de la forma fact(n).
En conclusión:
• Una llamada es tail recursive (recursiva por cola) si no tiene que hacer nada más después de la llamada de retorno.
• Tail recursion es cuando la llamada recursiva es la última instrucción en la función.
• Usar tail recursion es muy ventajoso, porque la cantidad de información que debe ser almacenada durante el cálculo es independiente del número de llamadas recursivas.
• El compilador trata una función tail recursive como si fuera una función iterativa.
Recent Comments