Imaginemos un mundo libre

La paz interior comienza en el momento en el que decides no permitir, que ninguna persona o evento, tome el control de tus emociones.

Tail recursion

with 7 comments

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:

// Función 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) << endl;
    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.

El código fuente de este y otros ejercicios de C++ está disponible en Github: 

https://github.com/ronnyml/C---Tutorial

Gracias por tu visita al blog. Puedes seguirme en Twitter haciendo click en el siguiente enlace:

Written by Ronny Yabar

May 19, 2009 at 10:30 pm

7 Responses

Subscribe to comments with RSS.

  1. En que casos específicos es bueno utilizar la recursividad, ya que dijeron que consume mucha memoria.

    John

    October 8, 2009 at 4:51 pm

  2. Realmente la recusión tiene muchas ventajas, a la hora de implementar algoritmos para la resuloción de problemas matemáticos, pero en muchos casos utiliza mucha memoria, lo cual no es muy efectivo para algunos casos

    marco

    October 16, 2009 at 2:59 pm

  3. Hasta ahora, para un proyecto de desarrollo real nunca he necesitado usar recursividad, incluso para lo que es procesamiento de señales. Hasta ahora la recursividad la tengo como ejercicio académico, suele ser interesante experimentar con ella.

    yelinna

    November 6, 2009 at 10:21 pm

  4. Muy buena explicacion y blog en general. Me ayudo a terminar de entender el tema de recursion de cola.

    Gracias

    Maximiliano

    February 3, 2012 at 3:18 pm

  5. Hola!
    Me gusta mucho la forma en que muestras la estructura de C++
    Me preguntaba si tiene algunos ejemplos de Pilas y colas?

    Mayra Ocampo

    November 14, 2012 at 8:02 pm

    • Hola Mayra gracias por la visita. No he escrito aun en el blog sobre pilas y colas, pero está en la lista de posts pendientes. Un abrazo y mucha suerte con C++.

      Ronny Yabar Aizcorbe

      December 8, 2012 at 2:35 am

  6. Muchas gracias por la explicación.

    darkz555

    August 22, 2013 at 11:05 pm


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: