Recursión explicada
Por Eduardo Sequelis
¿Qué es recursión?
Podemos decir que la recursión es la reproducción de una “misma” (cosa) pero en una escala más pequeña sucesivamente N veces hasta llegar un mínimo el cuál la función no puede ser subdividida.
Un ejemplo sería una muñeca rusa “matrioshka” la cuál, la muñeca más grande contiene una más pequeña que a su vez tiene una más pequeña hasta la N muñeca que es la más pequeña.
Desde el punto de vista matemático tenemos una figura geométrica que la subdividimos de tal manera que quepa en la primera división y así sucesivamente hasta llegar a un punto donde no se puede percibir las subdivisiones, dando pie a lo que llamamos un fractal.
En programación le llamamos recursión a esta técnica que nos permite manejar de una forma “simple” problemas que de forma iterativa con ciclos sería muy complicado manejar.
Ya hablando en términos de programación C++ (no sólo en este lenguaje, la mayoría de los lenguajes soportan) la recursión es usada para que una función se llame a sí misma. Cuando una función se invoca a sí misma se le llama “llamada recursiva” y lo podemos definir como la característica de regresar a sí misma y repetir, para nosotros programadores, tenemos que estar pensando en condiciones donde se termine la recursión.
Hay dos tipos de recursión, la recursión directa y la recursión indirecta. La recursión directa es la cuál tenemos una función A que dentro de su serie de instrucciones que llaman a la función A. La recursión indirecta tiene la característica que una función A llama a una función B y la función B llama a su vez a la función A.
Para resolver problemas de programación (o matemáticos) con recursión debemos de hacer 3 preguntas para validar que se puede resolver ese problema con recursión y posteriormente hacer un análisis detallado con unos pasos enlistados más abajo.
¿Hay un caso base en el cuál se resuelva el problema y no se resuelva con otra llamada recursiva?
¿Cada vez que se manda a llamar la función recursiva se ve una disminución del problema original?
¿En caso de que funcione la parte recursiva, el resto de la función funciona correctamente?
Para resolver problemas con recursión necesitas analizar con la siguiente lista de pasos:
1.- Tener una definición exacta del resultado al resolver el problema.
2.- Determinar el tamaño del problema que se tiene que resolver en una llamada a la función, el valor del problema se debe de mostrar en los valores de los parámetros.
3.- Identifica y resuelve el caso base, el cuál se puede expresar con no recursividad
4.- Resuelve el caso base correctamente en términos de un pedazo más pequeño del problema original.
Por poner un ejemplo:
Vamos a pensar en la serie Fibonacci donde queremos determinar el décimo número de la serie, la secuencia de números sigue el siguiente patrón matemático.
f0 = 0
f1 = 1
fn = fn-1 + fn-2
¿Hay un caso base en el problema? Sí, en este ejemplo tenemos el caso base f0 = 0 al igual que f1 = 1 y f2 = 1 dado que… f2 = f1 + f0.
¿Cada vez que se manda a llamar la función recursiva hay se ve una disminución del problema original?
Sí, asumiendo que queremos saber el número Fibonacci que está en la posición 10, excluyendo el 0 cómo un índice. Podemos hacer una función que vaya desglosando el número hasta llegar a f1 (explico este ejemplo más adelante).
¿En caso de que funcione la parte recursiva, el resto de la función funciona correctamente?
Debemos de tener un pedazo de código que rompa con la recursión, en caso que llegue a f1 y a f2.
Entonces para plantear nuestro código hacemos la siguiente serie de preguntas que vienen enumeradas arriba.
¿Tenemos una definición exacta del resultado al resolver el problema?
Si, si nosotros metemos un 10 a la función, esta nos debería retornar un 55.
¿Determinamos el tamaño del problema que se tiene que resolver en una llamada a la función? El valor del problema se debe de mostrar en los valores de los parámetros.
Sí, podemos ver que si metemos 10, esto va a ser igual a f10, sabemos que para regresar el valor Fibonacci de esa secuencia, tenemos que llegar a f2 y f1.
¿Identificamos y resolvimos el caso base, el cuál se puede expresar con no recursividad?
Sí, sabemos que el caso base es que el parámetro del número que queremos conseguir sea 2 o 1, podemos poner una función que regrese el valor de f2 y f1 (valor 1)
¿Resolvemos el caso base correctamente en términos de un pedazo más pequeño del problema original?
Sí, cuando vamos reduciendo el parámetro de entrada siempre estamos reduciendo el problema, posteriormente tenemos que llegamos a un punto donde no se puede subdividir más, en este caso sería que el índice llegue a 1 o a 2 que corresponden a f1 y a f2.
Yo sé que muchos de los lectores deben de estar pensando… “Okeeey, a ver, ya dime qué está pasando, que no te entiendo.”
Toca ilustrarlo.
long fibonacci_recursivo(int n) {
if((n==1)||(n==2)){
return 1;
}else{
return(fibonacci_recursivo(n-1) +fibonacci_recursivo(n-2));
}
}En el código anterior tenemos la resolución de Fibonacci con recursividad.
Lectores… “A ver, explica” .
Nosotros ya pasamos por el análisis anterior, ya hicimos las preguntas correspondientes para saber si la recursividad nos va a ayudar a solucionar el problema, ya identificamos que si podemos romper el problema en pedazos más pequeños, y salir del loop infinito en caso de que no tenga caso base.
Lo que estamos haciendo es declarar el método, y el método recibe el parámetro que como ya mencionamos es el “índice” por así decirlo.
Nosotros inmediatamente, preguntamos… ¿Es el caso base? con la sentencia if(n==2||n==1){}
En caso que sea, regresamos un 1 como respuesta en caso que no, mandamos a llamar la misma función pero con dos índices menores, con la sentencia.
return (fibonacci_recursividad(n-1) + fibonacci_recursividad(n-2));
Lector… “Explícame esa movida malévola”.
Okey, vamos a ejecutar lo que estamos diciendo…
Para efectos de de que no sea tan redundante el artículo vamos a hacer solo hasta f5.
Suponiendo que el parámetro inicial es 5.
Para leer esto, se tiene que tomar en cuenta que, el verde es la primera ejecución
Las amarillas son a las que mandó a llamar la primera ejecución, y las azules son las que manda a llamar la segunda ejecución, como podrán ver la ejecución de n = 3 se repite en 2 momentos, al igual que el resto de los casos base, así que esto se puede leer de la siguiente manera:
Casilla (0,0) invoca a casilla (0,1) y casilla (0,2)
Posteriormente tenemos que la casilla (0,1) invoca a casilla (1,1) y (2,1)
Casilla (0,2) manda a llamar a casilla (1,2) y a (2,2)
Como casilla (1,1) es igual a casilla (0,2) en casilla (1,1) es como si estuvieran las casillas (2,1) y (2,2).
Y con eso llegamos al resultado que se ve expresado en las casillas (0,1) y (0,2)
Por último, me gustaría hacer unas precisiones, en C++ tenemos que una línea de código que manda a llamar a una función recursiva, no se deja de ejecutar y no continúa con el resto de las sentencias hasta que termina con la recursión. Ejemplo:
void TreeNode<T>::inorder(std::stringstream &aux) const { if (left != 0) { left->inorder(aux); } if(aux.tellp() != 1){ aux << " "; } aux << value; if(right != 0){ right->inorder(aux); }}
Aquí lo que está sucediendo es que estamos en un nodo de un árbol binario, que tiene ciertas características, y mandamos a llamar esta misma función en la primera sentecia left -> inorder(aux); y esto se repite hasta que el nodo izquierdo el n nodo izquierdo del nodo principal ya no tiene nodo y termina con el resto de las sentencias de la misma función pero a sus respectivos niveles, hasta ese momento es que pasa a la siguiente sentencia que es aux<<value; Eso quiere decir si tiene 20 nodos izquierdos y el último tiene 20 nodos derechos no se va a ejecutar el aux<<value principal hasta que no se ejecuten todas esas operaciones.
Por último cuando tenemos algo de este estilo:
int TreeNode::depth() const {int right_count = -1;int left_count = -1;int higher_count = -1;if(left != 0){ left_count = left->depth();}if(right != 0){ right_count = right->depth();}higher_count = (left_count > right_count) ? left_count:right_count;return (higher_count +1);}
Estamos haciendo una función que recorra un árbol binario y regrese la profundidad máxima, en realidad lo que está pasando es que va utilizando nuevos lugares en memoria, de right_count con cada vez que entra a esa línea de comando. Por lo que cuando llega al final de la ejecución, cuando regresa (higher_count + 1) lo que está pasando es que cuando se ejecuta actualiza el valor de left o right _ count de la función que los mandó a llamar, y así sucesivamente hasta llegar a la primera llamada.
Para finalizar, la recursión es una técnica de programación que simplifica muchos problemas de programación que de forma iterativa, serían muy complicados de manejar. El manejo de problemas con ésta técnica es a través de casos base o la simplificación más simple.
Espero que este artículo haya sido sobre su agrado.
Referencias
[1] Image taked from https://spanish.alibaba.com/product-detail/large-size-summer-style-country-life-images-nesting-dolls-russian-dolls-that-fit-inside-each-other-handmade-wooden-art-set-20-pc-50030060917.html
[2] Image taked from https://www.pinterest.es/pin/275845545903940958/
[3] Libro de consulta: NELL DALE. (2003). Programming with Recursion. En C++ Plus Data Structures (789). Canada Mississaga 2406 Nikanna Road Canada: JONES AND BARTLETT PUBLISHERS.
