Recursividad: una aplicación clásica
Objetivo
El objetivo es explicar el concepto de la recursividad y utilizarlo para desarrollar la resolución de un laberinto en código C++.
Introducción
(Definición de wikipedia) |
¿Qué Significa esto?
Los ejemplos siempre son buenos para entender algo abstracto.
Veamos el ejemplo clásio del factorial.
Cómo resolvemos el factorial de 4.
4 x 3 x 2 x 1 = 24
Ahora llamemos a 4, N.
Cómo lo resolvemos.
N x (N-1) x (N-2) x (N-3)
Ahora pensemos cómo lo resolvemos, cuales son los pasos que aplicamos.
Supuestos:
Tenemos un número N.
(!: es el símbolo del factorial.)
Lo tenemos que multiplicar por sus enteros anteriores hasta llegar al 1.
Sabemos que por definición de factorial: 1! = 1 y 0! = 1.
Guardo el producto en un acumulador que comienza en 1.
Pasos:
1. ¿N = 1 ?
Sí, entonces terminé el calculo. El resultado está en Acumulador;
Sino Acumulador = Acumulador x N.
2. Ahora llamo N a (N-1)
3. Voy al paso 1.
Probemos los pasos: Con N = 4 (Recordemos Acumulador = 1)
1. ¿4 = 1?
No, entonces Acumulador = Acumulador x N.
Reemplazando, Acumulador = 1 x 4.
2. N = N -1.
Reemplazando, N = 4 -1, N = 3
3. Voy al paso 1 con N=3.
1. ¿3 = 1?
No, entonces Acumulador = 4 x 3 = 12;
2. N = 2
3. Voy al paso 1 con N=2
1. ¿2 = 1?
No, entonces Acumulador = 12 x 2 = 24
2. N = 1
3. Voy al paso 1 con N = 1
1. ¿1=1?
Sí, entonces terminé el calculo. El resultado está en Acumulador = 24.
Veamos el ejemplo clásio del factorial.
Cómo resolvemos el factorial de 4.
4 x 3 x 2 x 1 = 24
Ahora llamemos a 4, N.
Cómo lo resolvemos.
N x (N-1) x (N-2) x (N-3)
Ahora pensemos cómo lo resolvemos, cuales son los pasos que aplicamos.
Supuestos:
Tenemos un número N.
(!: es el símbolo del factorial.)
Lo tenemos que multiplicar por sus enteros anteriores hasta llegar al 1.
Sabemos que por definición de factorial: 1! = 1 y 0! = 1.
Guardo el producto en un acumulador que comienza en 1.
Pasos:
1. ¿N = 1 ?
Sí, entonces terminé el calculo. El resultado está en Acumulador;
Sino Acumulador = Acumulador x N.
2. Ahora llamo N a (N-1)
3. Voy al paso 1.
Probemos los pasos: Con N = 4 (Recordemos Acumulador = 1)
1. ¿4 = 1?
No, entonces Acumulador = Acumulador x N.
Reemplazando, Acumulador = 1 x 4.
2. N = N -1.
Reemplazando, N = 4 -1, N = 3
3. Voy al paso 1 con N=3.
1. ¿3 = 1?
No, entonces Acumulador = 4 x 3 = 12;
2. N = 2
3. Voy al paso 1 con N=2
1. ¿2 = 1?
No, entonces Acumulador = 12 x 2 = 24
2. N = 1
3. Voy al paso 1 con N = 1
1. ¿1=1?
Sí, entonces terminé el calculo. El resultado está en Acumulador = 24.
¿¿qué tiene ver con la recursividad??
En el primer paso se define como es el cálculo del factorial y se indica en qué momento se termina de calcular.
En el segundo paso tomo el entero anterior.
En el tercer paso tenemos que aplicar el mismo cálculo para el entero anterior. Y cómo aplico el cálculo: Como se indica en el paso 1. (Cómo ya se lo apliqué al entero posterior)
Ahí está la recusividad: Realizo un proceso basado en la definición. Itero realizando la misma definición hasta que se de la condición de corte.
Realizo un cálculo parcial, pero descubro que tengo que hacer lo mismo para el entero anterior y cuando lo realizo para este vuelvo a descubrir lo mismo, así hasta que llegue al 1.
La recursividad nos pertime resolver problemas que posean la característica de tener que utiliza la misma definición de resolución, los mismos moviemientos, los mismos pasos, los mismos cálculos o consideraciones recurrentemente.
Con la recursividad se resuelve el factorial, la sucesión de Fibonacci, las torres de Hanoi, y muchos juegos de ingenio.
Por supuesto, recorrido de árboles y resolución de caminos.
Problema del laberinto
El problema del laberinto dice que tenemos una matriz de NxM, formadas por ceros y unos.
Definiciones:
- Los unos son camino
- Los ceros son pared
- Comenzamos en las coordenadas (Columna, Fila)=(0,0)
- Sólo nos podemos mover hacia abajo o hacia la derecha
- No podemos movernos en diagonal
- No podemos saltar, entonces el camino se determina por unos que esten en casillas vecinas, siguiendo las reglas ya mencionadas
- La prioridad para movernos será: Abajo, Derecha.
¿Cómo lo resolverían sin la recusividad?
Seguro se puede, pero sería muy compleja y difícil de enterder, hasta para nosotros mismo si tenemos que mantener el código después de un tiempo.
Veamos la magia de la recursividad
Este es el código de la resolución:
Decisiones que tomé:
Decisiones que tomé:
- El programa está compuesto por dos clases: CAzar y CMatrix.
- El laberinto se llena con números al azar que los genera la clase CAzar. Un buena idea sería levantar la matriz de un archivo. Si esto lo llevamos a un juego podríamos tener un editor de laberintos.
- En la clase CMatrix se resuelve la generación, impresión y el chequeo de si tiene salida el laberinto.
CAzar.h#ifndef CAZAR_H_
#define CAZAR_H_
#include
#include
class CAzar {
public:
CAzar();
virtual ~CAzar();
public:
double getRndNumber(double dMin, double dMax);
};
#endif /* CAZAR_H_ */CAzar.cpp#include "CAzar.h"
CAzar::CAzar() {
srand((unsigned)time(0));
}
CAzar::~CAzar() {
}
double CAzar::getRndNumber(double dMin, double dMax){
double random;
random = (rand()% (int(dMax-dMin) + 1)) + dMin;
return random;
}CMatriz.h
#ifndef CMATRIX_H_
#define CMATRIX_H_
#include "CAzar.h"
//Macros para no tener número mágicos en el código
#define MAT_MAX_COL 10
#define MAT_MAX_ROW 5
#define _CAMINO_ 1.0
#define _PARED_ 0.0
//Macros para hacer más claras las preguntas
#define PUEDO_PASAR(x) (x == _CAMINO_)
#define FILA_FINAL(x) (x == MAT_MAX_ROW-1)
class CMatrix {
public:
CMatrix();
virtual ~CMatrix();
void Generate();
void Print();
bool IsThereExit();
bool RecursiveSolve( int c, int f );
private:
CAzar azar;
int matrix[MAT_MAX_COL][MAT_MAX_ROW];
};
#endif /* CMATRIX_H_ */CMatrix.cpp
#include "CMatrix.h"
#include
using namespace std;
CMatrix::CMatrix() {
}
CMatrix::~CMatrix() {
// TODO Auto-generated destructor stub
}
////////////////////////////////////////////////
void CMatrix::Generate(){
//
for ( int c = 0; c < MAT_MAX_COL; c++){
for ( int f = 0; f < MAT_MAX_ROW; f++ ){
matrix[c][f] = (int) azar.getRndNumber( _PARED_, _CAMINO_ );
}
}
}
////////////////////////////////////////////////
void CMatrix::Print(){
//
cout << "T H E M A T R I X" << endl;
int n;
for ( int f = 0; f < MAT_MAX_ROW; f++){
for ( int c = 0; c < MAT_MAX_COL; c++ ){
cout << matrix[c][f];
}
cout << endl;
}
}
/////////////////////////////////////////////////
bool CMatrix::IsThereExit(){
return RecursiveSolve(0,0);
}
/////////////////////////////////////////////////
bool CMatrix::RecursiveSolve( int c, int f ){
//1. Condición de corte final
if ( PUEDO_PASAR( matrix[c][f] ) &&
FILA_FINAL( f ) ){
cout << "estoy en (" << c << ", " << f << ")llegue al final" << endl;
return true;
}
//2. No llegué al final, así que recorro según prioridades
if( PUEDO_PASAR( matrix[c][f] ) ){//Si es camino
//2.1. Camino en el laberinto, la prioridad es bajar
if( f+1 < MAT_MAX_ROW &&
PUEDO_PASAR( matrix[c][f+1] ) ){
cout << "estoy en (" << c << ", " << f <<") me fijo en la fila siguiente" << endl;
return RecursiveSolve( c, f+1); //Uso la magia de la recursividad
}
else {
//2.2. Como no puedo bajar, me desplazo a la derecha
if( c+1 < MAT_MAX_COL && PUEDO_PASAR( matrix[c+1][f] ) ){
cout << "estoy en (" << c << ", " << f <<") me fijo en la Columna siguiente" << endl;
return RecursiveSolve( c+1, f);//Uso la magia de la recursividad
}else{
//No tengo camino para seguir.
cout << "estoy en (" << c << ", " << f <<") No tengo camino para seguir" << endl;
return false;
}
}
}
//3.Encontré una pared, por acá no.
cout << "estoy en (" << c << ", " << f <<") NADA!" << endl;
return false;
}
RecursiveSolve
- Este método devuelve true si hay salida o false en caso contrario.
- Recibe como parámetros las coordenadas en donde estoy parado en la matriz.
- Lo primero que chequeamos es la condición de corte: Que pueda pasar (que esté parado en un 1) y que la fila sea la última
- Si no se da la condición de corte me fijo si puedo pasar: es decir si estoy en un 1 y no estoy en la última fila. De ser así, me muevo de acuerdo a las prioridades: primero hacia abajo y después hacia la derecha.
- Notemos que si puedo pasar, camino. ¿cómo camino? Acá es donde uso la magia de la recursividad, me llamo a mi mismo(RecursiveSolve), aplico mi definición. El paso uno del ejemplo del factorial que escribí al principio.
- Cada vez que hacemos el "return RecursiveSolve( ... , ...);" estamos agregando en la callstack un nodo más, así que la recursividad podría bajar la performance del sistema si hacemos demasiados llamados recursivos. Este es un punto a tener en cuenta.
- Cuando se ejecutan las líneas "return true;"o "return false;" el procesador quita un nodo del callstack y regresa al punto que se había llamado. Eso provoca que se vuelva en la matríz por cada uno de los caminos que se bifurcaron.
- El método avanza en un 1 y analiza todos lo caminos desde allí, así con cada 1, regresando cuando encuentra un cero o cuando llega al final
bool CMatrix::RecursiveSolve( int c, int f ){
//1. Condición de corte final
if ( PUEDO_PASAR( matrix[c][f] ) &&
FILA_FINAL( f ) ){
cout << "estoy en (" << c << ", " << f << ")llegue al final" << endl;
return true;
}
//2. No llegué al final, así que recorro según prioridades
if( PUEDO_PASAR( matrix[c][f] ) ){//Si es camino
//2.1. Camino en el laberinto, la prioridad es bajar
if( f+1 < MAT_MAX_ROW &&
PUEDO_PASAR( matrix[c][f+1] ) ){
cout << "estoy en (" << c << ", " << f <<") me fijo en la fila siguiente" << endl;
return RecursiveSolve( c, f+1); //Uso la magia de la recursividad
}
else {
//2.2. Como no puedo bajar, me desplazo a la derecha
if( c+1 < MAT_MAX_COL && PUEDO_PASAR( matrix[c+1][f] ) ){
cout << "estoy en (" << c << ", " << f <<") me fijo en la Columna siguiente" << endl;
return RecursiveSolve( c+1, f);//Uso la magia de la recursividad
}else{
//No tengo camino para seguir.
cout << "estoy en (" << c << ", " << f <<") No tengo camino para seguir" << endl;
return false;
}
}
}
//3.Encontré una pared, por acá no.
cout << "estoy en (" << c << ", " << f <<") NADA!" << endl;
return false;
}
Prueba de la solución
int main(void) {
puts("Laberinto");
CMatrix matrix;
for ( int i = 0; i < 10; i++){
cout << endl;
cout << "----------------------------------------------------------" << endl;
matrix.Generate();
matrix.Print();
cout << matrix.IsThereExit() << endl;
}
}
Laberinto
----------------------------------------------------------
T H E M A T R I X
1101010110
0000101110
1000110100
0111011100
0010000100
estoy en (0, 0) me fijo en la Columna siguiente
estoy en (1, 0) No tengo camino para seguir
0
----------------------------------------------------------
T H E M A T R I X
1000001010
0110010011
1011001110
0100010110
0001000001
estoy en (0, 0) No tengo camino para seguir
0
----------------------------------------------------------
T H E M A T R I X
0000001101
1110010000
0010101000
1010101101
0110001101
estoy en (0, 0) NADA!
0
----------------------------------------------------------
T H E M A T R I X
0010011100
0111101110
1101010100
1001011110
1010111000
estoy en (0, 0) NADA!
0
----------------------------------------------------------
T H E M A T R I X
0001100111
1011110001
0000101000
0110010011
1010101001
estoy en (0, 0) NADA!
0
----------------------------------------------------------
T H E M A T R I X
1001101100
1110101001
0010100100
1010000110
1011110110
estoy en (0, 0) me fijo en la fila siguiente
estoy en (0, 1) me fijo en la Columna siguiente
estoy en (1, 1) me fijo en la Columna siguiente
estoy en (2, 1) me fijo en la fila siguiente
estoy en (2, 2) me fijo en la fila siguiente
estoy en (2, 3) me fijo en la fila siguiente
estoy en (2, 4)llegue al final
1
----------------------------------------------------------
T H E M A T R I X
1101000111
0100011101
0001001110
1111011000
0101001010
estoy en (0, 0) me fijo en la Columna siguiente
estoy en (1, 0) me fijo en la fila siguiente
estoy en (1, 1) No tengo camino para seguir
0
----------------------------------------------------------
T H E M A T R I X
1000010001
0111000100
0011011101
0011101011
1011011110
estoy en (0, 0) No tengo camino para seguir
0
----------------------------------------------------------
T H E M A T R I X
1100100111
0101100001
1011100000
1010011011
0001100011
estoy en (0, 0) me fijo en la Columna siguiente
estoy en (1, 0) me fijo en la fila siguiente
estoy en (1, 1) No tengo camino para seguir
0
----------------------------------------------------------
T H E M A T R I X
1011001100
1011101110
1110111010
1001001010
0110110011
estoy en (0, 0) me fijo en la fila siguiente
estoy en (0, 1) me fijo en la fila siguiente
estoy en (0, 2) me fijo en la fila siguiente
estoy en (0, 3) No tengo camino para seguir
0
Entradas
