C++ / recursion mas profunda

Bienvenidos sean a este post, hoy hablaremos nuevamente sobre recursion.

En este post hablamos sobre recursion, y vimos algunos ejemplos para entender el concepto de recursion. Para meternos en contexto, vamos a analizar el siguiente ejemplo:

#include <iostream>

int factoreo(int n)
{
        if (n<= 1) return 1;
        return n * factoreo(n - 1);
}

int main()
{
        std::cout << factoreo(10) << std::endl;

        return 0;
}

Funcion simple donde calculamos el factoreo del valor recibido, donde si este es menor a 1 siempre devuelve 1. De lo contrario, devuelve el producto del valor recibido por un nuevo llamado a la funcion restando en uno al valor recibido. En el main, mostramos el resultado devuelto por el llamado a la funcion. Compilemos y veamos la salida:

$ ./recursion
3628800
$

Las funciones recursivas proveen soluciones elegantes comparadas con sus contrapartes iterativas. Sin embargo, debemos tener mucho cuidado como se usan porque este nos puede llevar a problemas de overflow en stack. Comentemos sobre las recursiones posibles.

Recursion head

Esta no es otra que la recursion regular con la cual estamos familiarizados. En el ejemplo anterior, la funcion factoreo se comporta como una funcion recursiva de este tipo, porque este hace una llamada recursiva antes de procesar el resultado en el paso actual.

Como mencionamos, para encontrar y devolver el resultado del producto, la funcion es llamada con un argumento reducido. Esto implica que el operador * es una especie de retenedor y esta esperando por su segundo argumento que sera devuelto por nuevo llamado a la funcion. Esto ocasiona que el stack crezca linealmente con el numero de llamadas recursivas a la funcion. Vamos a cambiar la funcion de factoreo de la siguiente manera:

#include <iostream>

int factoreo(int n)
{
        int resultado = 1;
        for(int i = n; i > 1; --i)
                resultado *= i;

        return resultado;
}

int main()
{
        std::cout << factoreo(10) << std::endl;

        return 0;
}

Solamente modificamos la funcion de factoreo, el resto sigue siendo de la manera. Yendo a la funcion, primero establecemos un valor inicial para resultado. En el bucle haremos nuevamente la reduccion del valor informado y en este haremos la multiplicacion. Y al final devolvemos el valor almacenado en resultado. Si lo compilan y ejecutan, deben obtener la misma salida que antes.

Una de las principales diferencias con el anterior es que el resultado de cada producto en cada vuelta en la misma variable. Con todo lo comentado podemos decir que cada funcion toma un espacio especificado en el stack, porque cada resultado generado debe ser almacenado en el stack. Siempre vamos a pensar que trabaja con la misma direccion de memoria, y deberia, pero en la vida real cada llamado a la funcion genera su propio espacio para sus variables. Por esta razon, debemos encontrar una solucion para que el resultado de cada llamada recursiva siempre se almacene en el mismo lugar.

Recursion tail

Esta es la solucion al inconveniente que mencionamos anteriormente porque su idea basica es hacer el procesamiento actual antes del llamado recursivo. Tomemos el codigo anterior y hagamos el siguiente cambio:

#include <iostream>

int factoreo(int n, int resultado)
{
        if (n <= 1) return resultado;
        return factoreo(n - 1, n * resultado);
}

int main()
{
        std::cout << factoreo(10, 1) << std::endl;

        return 0;
}

El primer cambio es en la funcion donde volvemos a hacerla recursiva como al inicio pero ahora recibe dos valores. El primero es para el valor para calcular el factoreo, como antes, pero el segundo sera para el calculo del resultado. Por eso, en el condicional si n es menor o igual a 1 procedemos a devolver el valor de resultado sin llamar recursivamente a la funcion. De lo contrario devolvemos el llamado de la funcion donde pasamos el valor de n – 1, seguido de la operacion para hacer el calculo pero ahora el resultado sera calculado en el momento de llamado. El otro cambio es al momento de llamado donde debemos pasar el valor inicial de resultado, que al igual que el inicio es de 1. Si lo compilan y ejecutan deben obtener la misma salida nuevamente.

Este tambien es denominado como Optimizacion de llamado de Tail (TCO por sus siglas en ingles) y si es soportado por el compilador, este se involucra sabiendo que el segundo argumento debe ser almacenado en el mismo lugar en cada llamada recursiva. Permitiendo que el stack se mantenga del mismo tamaño sin importar la cantidad de llamadas recursivas que efectuemos. Esta son dos formas de recursion que disponemos, la comun y mas clasica y esta ultima que nos permite mejorarla.

En resumen, hoy hemos visto nuevamente recursion, pero ahora hemos visto las dos posibilidades que disponemos, hablamos de la clasica llamada head y el inconveniente que puede acarrearnos su uso, asi como mejorarla mediante la iteracion, para luego mejorarla con otro tipo de recursion. Espero les haya resultado de utilidad sigueme en tumblr, Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.