Recursividad

Recursividad :B

Introducción

"Para entender la recursividad, primero hay que entender la recursividad"

Para aquellos que están metidos en esto de la programación, en algún momento tendrán que toparse con el concepto de la recursividad. Para muchos de nosotros no es algo sencillo de comprender y mucho menos sencillo de aplicar. Formalmente se dice que es un procedimiento o función que está definido en términos de sí mismo. Esto quiere decir que, hablando en términos de programación orientada a objetos, es un método que para poder ejecutarse, puede llegar a requerir llamarse a si mismo en varias ocasiones.

La recursividad aplica la conocida filosofía de divide y vencerás, es decir, toma un problema grande y lo va dividiendo en problemas mas pequeños que sean mas sencillos de resolver. Todo esto quedara un poco mas claro con un pequeño ejemplo.

Todos conocemos lo que es el factorial de un numero, y para los que no, no es otra cosa mas que la multiplicación sucesiva de un numero, por cada uno de sus antecesores. Por ejemplo si tenemos 5! = 5x4x3x2x1 = 120. Aunque no se aprecie claramente, en esa operación se hace uso de la recursividad :p

Para calcular el factorial de un numero, hay dos reglas sencillas, el factorial de 1 y de 0, en ambos casos es 1, para todos los demás números, hay que multiplicarse por cada antecesor, entonces podemos hacer un pequeño ejemplo;

"Fulanito quería saber cuanto era 4!, entonces le marcó a su hermano Sutanito para preguntarle, él le contesto que era fácil, 4! era 4 x 3!, pero se quedo con la duda y tuvo que marcarle a Manganito para preguntar cuanto era 3!, él le contesto que 3! era 3 x 2!, pero él también se quedo con la duda de cuanto era 2! asi que tuvo que preguntarle a Perenganito y él le contesto que 2! era 2 x 1!, pero él no sabia cuanto era 1!, así que busco en Gúgl, y se dio cuenta que 1! era 1,  entonces pudo contestarle a Manganito y decirle que 2! era 2. Después como Manganito ya sabía que 2! era 2, pudo contestarle a Sutanito que 3x2! era 6. Luego como Sutanito ya sabía que 3! era 6, pudo contestarle a Fulanito que 4x3! era 24, y por último, fue como Fulanito pudo saber que 4! era 24."

Intentado descifrar la enredosa llamada telefónica, podemos observar algo como lo siguiente

A grandes rasgos es así como trabaja la recursividad, toma un problema grande (el 4! por ejemplo), y lo va dividiendo en problemas más pequeños y lógicamente mas sencillos de resolver (las llamadas entre fulanitos) hasta que llega a un punto en que no se necesitan hacer mas divisiones (el 1!) y se pueden empezar a retornar los datos (las llamadas devueltas) para resolver el problema inicial (el dichoso 4!).

El ejemplo del factorial es un clásico para tratar de explicar como trabaja la recursividad, aunque es un ejemplo muy básico a comparación de los problemas donde realmente tiene aplicaciones la recursividad, sirve para dar un panorama general, como en todo, el dominio de esta técnica de programación reside en la práctica :p

El código en C# del método que sirve para calcular factoriales sería el siguiente:

public long fact(int n)

{

   if(n == 1 || n == 0)

      return 1;

   else

      return n * fact(n - 1);

}

Más a fondo

A un nivel un poco más profundo, se puede decir que las estructuras de datos y la recursividad están íntimamente ligadas. Por un lado, la recursividad es posible gracias a una estructura llamada Pila o Stack, que tiene sus propias características en las que no vamos a profundizar de momento, solamente como dato general la pila es una estructura de tipo lifo o último en entrar, primero en salir, por ejemplo; en una pila de platos, para tomar el plato que se encuentra hasta abajo primero hay que comenzar extrayendo el plato que se encuentra en la cima, después el que le sigue y así sucesivamente.

Con eso en mente, podemos darnos cuenta que en la imagen anterior, la primera llamada (Fulanito preguntando cuanto era 4!) fue la última en ser contestada, y a su vez, la última llamada (Perenganito investigando cuanto era 1!) fue la primera en devolver información sin dudas. Entonces a nivel estructura de datos, podemos explicar el orden de llamadas del código anterior utilizando una pila.

Como se puede apreciar, las llamadas se van almacenando en una pila dependiendo del orden en que se hacen. Otro punto remarcable es el hecho de que las últimas llamadas en realizarse, son las primeras en ser desapiladas, y las primeras llamadas en la pila son las últimas en ser desapiladas. Tal es el caso de la llamada inicial fact(4), es la última en devolver una respuesta.