C++ / recursion

Bienvenidos sean a este post, hoy veremos un concepto que se aplica a las funciones.

La recursion es la accion de una funcion que se llama a si misma. Esto se aplica a todas las funciones, salvo a main. Esto es asi porque si main se llamara a si misma, vuelve a ejecutar todo nuevamente y en el mejor de los casos interrumpiendo lo que estaba ejecutando anteriormente para iniciarlo nuevamente. Por esta razon, esta prohibida la recursion en main. Para entender el concepto veamos una funcion recursiva simple:

int incrementar(int num)
{
	std::cout << num << std::endl;
	incrementar(num + 1);
}

Funcion que recibe un valor, muestra el valor recibido y luego se llama a si misma pero ahora incrementa el valor anteriormente recibido y lo vuelve a pasar como argumento. Esto es la recursion porque al llamarse a si misma, vuelve a mostrar el valor recibido y se vuelve a llamar. Esto se repetira infinitamente pero como podemos detenerlo? Para ello deben modificar la funcion de la siguiente manera:

int incrementar(int num)
{
	if (num > 100) return;
	std::cout << num << std::endl;
	incrementar(num + 1);
}

Esta vez saldra cuando num sea mayor a 100 porque return nos devolvera al lugar desde donde fue llamado. Esto no deja de ser un bucle for donde se repite a si mismo mientras no se cumpla condicion, sobre for hablamos en este post, pero vamos a ver un ejemplo para aplicar una recursion:

#include <iostream>
#include <vector>
#include <climits>

int maximo(std::vector< int > n, int pos = 0)
{
        static int max = 0;
        if (pos < n.size()) {
                max = n[pos] > max ? n[pos] : max;
                maximo(n, pos+1);
        }
        return max;
}

int minimo(std::vector< int > n, int pos = 0)
{
        static int min = INT_MAX;
        if (pos < n.size()) {
                min = n[pos] < min ? n[pos] : min;
                minimo(n, pos+1);
        }
        return min;
}

int main()
{
        int numero = 0;
        std::vector < int > arreglo;
        while(numero != -1) {
                std::cout << "Ingresa un valor (-1 para salir): ";
                std::cin >> numero;
                if (numero != -1) arreglo.push_back(numero);
        }

        std::cout << "Valor mayor: " << maximo(arreglo) << std::endl;
        std::cout << "Valor menor: " << minimo(arreglo) << std::endl;

        return 0;
}

Este codigo agregara varios valores en un vector y al final mostraremos el valor mas grande y mas chico de todos los agregados. Usaremos a vector y no un array para que puedan agregar la cantidad de valores que deseen sin limites. Primero agregaremos las tres librerias que usaremos, siendo la primera la que se utiliza. La segunda sera para crear y manejar el vector. La ultima sera para poder acceder a unas constantes, entre ellas las encargadas de establecer el valor maximo de cada tipo de dato disponible.

Lo siguiente son las funciones recursivas para obtener el valor maximo y minimo de los ingresados. Hablemos sobre uno solamente porque son exactamente iguales. Veamos como es el primero:

int maximo(std::vector< int > n, int pos = 0)
{
        static int max = 0;
        if (pos < n.size()) {
                max = n[pos] > max ? n[pos] : max;
                maximo(n, pos+1);
        }
        return max;
}

Este recibira dos valores, siendo primero el vector que analizaremos y el segundo para la posicion en cada elemento que agregamos. Pero como pasamos un valor predeterminado no es necesario informarlo. En el bloque tendremos una variable estatica llamada max, esta sera la encargada de almacenar el valor maximo y devolverlo, y tendra un valor inicial de cero. Luego mediante un condicional verificamos si el valor de pos es menor al tamaño del vector. Mientras se cumpla esta condicion estableceremos el valor en max. Para ello usaremos un operador condicional donde verifica si la posicion actual del vector es mayor a max. En caso de ser verdadero procede a asignarselo. En caso contrario, mantiene el valor que tiene asignado. Luego volvemmos a llamar a la funcion maximo pero ahora incrementaremos el valor de pos. Esto hara que pasemos a la siguiente posicion. Cuando no se cumpla mas la condicion proccedemoss a devolver el valor que este asignado en max. La funcion minimo es exactamente igual salvo por unos detalles. La primera es que la variable que almacena el valor no tiene un valor asignado sino a INT_MAX.

Esta constante es el valor maximo que puede poseer una variable de tipo int. Esto lo hacemos asi para que cualquier valor que ingresemos siempre sea menor a este. La otra diferencia esta en el operador condicional donde ahora verifica si el valor de la posicion del vector es menor al asignado a min. En caso de ser verdadero lo reemplaza, de lo contrario lo mantiene. Y el resto sigue siendo lo mismo, hasta con la misma conducta.

En el main, primero definimos una variable para almacenar los variables a agregar en el vector. Lo siguiente es crear al vector. A continuacion, tenemos un bucle donde lo repetiremos mientras numero sea distinto de -1. En el bloque mostraremos un mensaje donde podemos ingresar un valor y -1 para salir. Ingresaremos un valor a numero y luego tenemos un condicional donde si numero es distinto de -1 procede a agregarlo al vector mediante push_back. Esta funcion agregara al final del vector el valor que le pasemos como argumento. Por ultimo, mostraremos un texto para indicar que mostrara el llamado a las funciones anteriores. Compilemos y veamos como trabaja:

$ ./recur
Ingresa un valor (-1 para salir): 1
Ingresa un valor (-1 para salir): 33
Ingresa un valor (-1 para salir): 2
Ingresa un valor (-1 para salir): 4
Ingresa un valor (-1 para salir): 22
Ingresa un valor (-1 para salir): 0
Ingresa un valor (-1 para salir): 5
Ingresa un valor (-1 para salir): 1
Ingresa un valor (-1 para salir): 3
Ingresa un valor (-1 para salir): -1
Valor mayor: 33
Valor menor: 0
$

Como pueden ver agregamos una gran cantidad de valores y lo cerramos con el -1. Una vez realizado, nos trajo cuales son los valores mas grandes y chicos de los ingresados. Si bien esto se puede mejorar con algunas otras funciones, el punto era mostrar como es una funcion recursiva. Como podran deducir, este tipo de funciones fueron las versiones primitivas de los bucles. Pero tambien pueden hacer otro tipo de funciones. Tales como el orden de un vector o un array. Asi como tambien pueden usar templates y realizar este tipo de funciones para cualquier tipo de dato. Y si bien, su uso principal ya es realizado mediante otras funciones. Esto no evita que su mecanica se utilice para otros temas.

En resumen, hoy hemos visto recursion, que es, para que sirve, como se utiliza, un ejemplo para entenerlo,, y un ejemplo practico para poder entender el concepto y aplicarlo a una utilidad. 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.