En el concepto anterior se vieron pequeños problemas para entender como funciona la recursividad, pero no se desarrollaron problemas donde conviene utilizar la recursividad.
Problema 1:
Imprimir la información de una lista simplemente encadenada de atrás para adelante.
El empleo de estructuras repetitivas para resolver este problema es bastante engorroso y lento (debemos avanzar hasta el último nodo e imprimir, luego avanzar desde el principio hasta el anteúltimo nodo y así sucesivamente)
El empleo de la recursividad para este problema hace más sencillo su solución.
Programa:
Ver videopublic class Recursividad { class Nodo { int info; Nodo sig; } private Nodo raiz; void insertarPrimero(int x) { Nodo nuevo = new Nodo (); nuevo.info = x; nuevo.sig=raiz; raiz=nuevo; } public void imprimirInversa(Nodo reco) { if (reco!=null) { imprimirInversa(reco.sig); System.out.print(reco.info+"-"); } } public void imprimirInversa () { imprimirInversa(raiz); } public static void main(String[] ar) { Recursividad r=new Recursividad(); r.insertarPrimero (10); r.insertarPrimero(4); r.insertarPrimero(5); r.imprimirInversa(); } }
![recursividad listas](https://www.tutorialesprogramacionya.com/javaya/imagentema/foto125.jpg)
Cuando llamamos al método recursivo le enviamos raiz y el parámetro reco recibe esta dirección. Si reco es distinto a null llamamos recursivamente al método enviándole la dirección del puntero sig del nodo.
Por lo que el parámetro reco recibe la dirección del segundo nodo.
![recursividad listas](https://www.tutorialesprogramacionya.com/javaya/imagentema/foto126.jpg)
Podemos observar como en las distintas llamadas recursivas el parámetro reco apunta a un nodo. Cuando se van desapilando las llamadas recursivas se imprime primeramente el 10 luego el 4 y por último el 5.
Problema 2:
Recorrer un árbol de directorios en forma recursiva.
Programa:
Ver videoimport java.io.File; public class Recursividad{ public void leer(String inicio,String altura) { File ar=new File(inicio); String[] dir=ar.list(); for(int f=0;f<dir.length;f++){ File ar2=new File(inicio+dir[f]); if (ar2.isFile()) System.out.println(altura+dir[f]); if (ar2.isDirectory()) { System.out.println(altura + "Directorio:"+dir[f].toUpperCase()); leer(inicio+dir[f]+"\\",altura+" "); } } } public static void main(String[] arguments) { Recursividad rec=new Recursividad(); rec.leer("d:\\windows\\",""); } }
Para recorrer y visitar todos los directorios y archivos de un directorio debemos implementar un algoritmo recursivo que reciba como parámetro el directorio inicial donde comenzaremos a recorrer:
public void leer(String inicio,String altura)
Creamos un objeto de la clase File con el directorio que llega como parámetro y mediante el método list obtenemos todos los archivos y directorios de dicho directorio:
File ar=new File(inicio); String[] dir=ar.list();
Mediante un for recorremos todo el vector que contiene la lista de archivos y directorios:
for(int f=0;f<dir.length;f++){
Creamos un objeto de la clase File para cada directorio y archivo:
File ar2=new File(inicio+dir[f]);
Luego de crear un objeto de la clase file podemos verificar si se trata de un archivo o directorio:
if (ar2.isFile()) System.out.println(altura+dir[f]); if (ar2.isDirectory()) { System.out.println(altura + "Directorio:"+dir[f].toUpperCase()); leer(inicio+dir[f]+"\\",altura+" "); }
Si es un archivo lo mostramos y si es un directorio además de mostrarlo llamamos recursivamente al método leer con el directorios nuevo a procesar.
Problema 3:
Desarrollar un programa que permita recorrer un laberinto e indique si tiene salida o no.
Para resolver este problema al laberinto lo representaremos con una matriz de 10 x 10 JLabel.
El valor:
"0" Representa pasillo "1" Representa pared "9" Persona "s" Salida
A la salida ubicarla en la componente de la fila 9 y columna 9 de la matriz. La persona comienza a recorrer el laberinto en la fila 0 y columna 0. Los ceros y unos disponerlos en forma aleatoria (con la función random)
Programa:
Ver videoimport javax.swing.*; import java.awt.*; import java.awt.event.*; class Laberinto extends JFrame implements ActionListener { JLabel[][] l; JButton b1; JButton b2; boolean salida; Laberinto() { setLayout(null); l=new JLabel[10][10]; for(int f=0;f<10;f++) { for(int c=0;c<10;c++) { l[f][c]=new JLabel(); l[f][c].setBounds(20+c*20,50+f*20,20,20); add(l[f][c]); } } b1=new JButton("Recorrer"); b1.setBounds(10,300,100,25); add(b1); b1.addActionListener(this); b2=new JButton("Crear"); b2.setBounds(120,300,100,25); add(b2); b2.addActionListener(this); crear(); } public void crear() { for(int f=0;f<10;f++) { for(int c=0;c<10;c++) { int a=(int)(Math.random()*4); l[f][c].setForeground(Color.black); if (a==0) l[f][c].setText("1"); else l[f][c].setText("0"); } } l[9][9].setText("s"); l[0][0].setText("0"); } public void recorrer(int fil,int col) { if (fil>=0 && fil<10 && col>=0 && col<10 && salida==false) { if (l[fil][col].getText().equals("s")) salida=true; else if (l[fil][col].getText().equals("0")) { l[fil][col].setText("9"); l[fil][col].setForeground(Color.red); recorrer(fil,col+1); recorrer(fil+1,col); recorrer(fil-1,col); recorrer(fil,col-1); } } } public void actionPerformed(ActionEvent e) { if (e.getSource()==b1) { salida=false; recorrer(0,0); if (salida) setTitle("tiene salida"); else setTitle("no tiene salida"); } if (e.getSource()==b2) crear(); } public static void main(String[] ar) { Laberinto l=new Laberinto(); l.setBounds(0,0,300,400); l.setVisible(true); l.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); } }
El método más importante es el recorrer:
public void recorrer(int fil,int col)
Primero verificamos si la coordenada a procesar del laberinto se encuentra dentro de los límites correctos y además no hayamos encontrado la salida hasta el momento:
if (fil>=0 && fil<10 && col>=0 && col<10 && salida==false)
Si entra al if anterior verificamos si estamos en la salida:
if (l[fil][col].getText().equals("s")) salida=true;
En el caso que no estemos en la salida verificamos si estamos en pasillo:
if (l[fil][col].getText().equals("0")) {
En caso de estar en el pasillo procedemos a fijar dicha JLabel con el caracter "9" e intentamos desplazarnos en las cuatro direcciones (arriba, abajo, derecha e izquierda), este desplazamiento lo logramos llamando recursivamente:
l[fil][col].setText("9"); l[fil][col].setForeground(Color.red); recorrer(fil,col+1); recorrer(fil+1,col); recorrer(fil-1,col); recorrer(fil,col-1);
Problema propuesto
- Desarrollar el juego del Buscaminas. Definir una matriz de 10*10 de JButton y disponer una 'b' para las bombas (10 diez) un cero en los botones que no tienen bombas en su perímetro, un 1 si tiene una bomba en su perímetro y así sucesivamente. Cuando se presiona un botón si hay un cero proceder en forma recursiva a destapar los botones que se encuentran a sus lados. Disponer el mismo color de frente y fondo de los botones para que el jugador no pueda ver si hay bombas o no.Ver video
import javax.swing.*; import java.awt.*; import java.awt.event.*; class Buscaminas extends JFrame implements ActionListener { JButton [] [] bot; JButton b1; Buscaminas () { setLayout (null); bot = new JButton [10] [10]; for (int f = 0 ; f < 10 ; f++) { for (int c = 0 ; c < 10 ; c++) { bot [f] [c] = new JButton ("0"); bot [f] [c].setBounds (20 + c * 41, 50 + f * 41, 41, 41); bot [f] [c].setBackground (Color.lightGray); bot [f] [c].setForeground (Color.lightGray); bot [f] [c].addActionListener (this); add (bot [f] [c]); } } b1 = new JButton ("Reiniciar"); b1.setBounds (20, 470, 100, 30); add (b1); b1.addActionListener (this); disponerBombas (); contarBombasPerimetro (); } void disponerBombas () { int cantidad = 10; do { int fila = (int) (Math.random () * 10); int columna = (int) (Math.random () * 10); if (bot [fila] [columna].getText ().equals ("b") == false) { bot [fila] [columna].setText ("b"); cantidad--; } } while (cantidad != 0); } void contarBombasPerimetro () { for (int f = 0 ; f < 10 ; f++) { for (int c = 0 ; c < 10 ; c++) { if (bot [f] [c].getText ().equals ("0") == true) { int cant = contarCoordenada (f, c); bot [f] [c].setText (String.valueOf (cant)); } } } } int contarCoordenada (int fila, int columna) { int total = 0; if (fila - 1 >= 0 && columna - 1 >= 0) { if (bot [fila - 1] [columna - 1].getText ().equals ("b") == true) total++; } if (fila - 1 >= 0) { if (bot [fila - 1] [columna].getText ().equals ("b") == true) total++; } if (fila - 1 >= 0 && columna + 1 < 10) { if (bot [fila - 1] [columna + 1].getText ().equals ("b") == true) total++; } if (columna + 1 < 10) { if (bot [fila] [columna + 1].getText ().equals ("b") == true) total++; } if (fila + 1 < 10 && columna + 1 < 10) { if (bot [fila + 1] [columna + 1].getText ().equals ("b") == true) total++; } if (fila + 1 < 10) { if (bot [fila + 1] [columna].getText ().equals ("b") == true) total++; } if (fila + 1 < 10 && columna - 1 >= 0) { if (bot [fila + 1] [columna - 1].getText ().equals ("b") == true) total++; } if (columna - 1 >= 0) { if (bot [fila] [columna - 1].getText ().equals ("b") == true) total++; } return total; } void desactivarJuego () { for (int f = 0 ; f < 10 ; f++) { for (int c = 0 ; c < 10 ; c++) { bot [f] [c].setEnabled (false); } } } void reiniciar () { setTitle (""); for (int f = 0 ; f < 10 ; f++) { for (int c = 0 ; c < 10 ; c++) { bot [f] [c].setText ("0"); bot [f] [c].setEnabled (true); bot [f] [c].setBackground (Color.lightGray); bot [f] [c].setForeground (Color.lightGray); } } disponerBombas (); contarBombasPerimetro (); } public void actionPerformed (ActionEvent e) { if (e.getSource () == b1) { reiniciar (); } for (int f = 0 ; f < 10 ; f++) { for (int c = 0 ; c < 10 ; c++) { if (e.getSource () == bot [f] [c]) { if (bot [f] [c].getText ().equals ("b") == true) { setTitle ("Boooooooooooooomm"); desactivarJuego (); } else if (bot [f] [c].getText ().equals ("0") == true) { recorrer (f, c); } else if (bot [f] [c].getText ().equals ("1") == true || bot [f] [c].getText ().equals ("2") == true || bot [f] [c].getText ().equals ("3") == true || bot [f] [c].getText ().equals ("4") == true || bot [f] [c].getText ().equals ("5") == true || bot [f] [c].getText ().equals ("6") == true || bot [f] [c].getText ().equals ("7") == true || bot [f] [c].getText ().equals ("8") == true) { bot [f] [c].setBackground (Color.yellow); bot [f] [c].setForeground (Color.black); } } } } verificarTriunfo (); } void verificarTriunfo () { int cant = 0; for (int f = 0 ; f < 10 ; f++) { for (int c = 0 ; c < 10 ; c++) { Color col = bot [f] [c].getBackground (); if (col == Color.yellow) cant++; } } if (cant == 90) { setTitle ("Ganooooooooo"); desactivarJuego (); } } void recorrer (int fil, int col) { if (fil >= 0 && fil < 10 && col >= 0 && col < 10) { if (bot [fil] [col].getText ().equals ("0")) { bot [fil] [col].setText (" "); bot [fil] [col].setBackground (Color.yellow); recorrer (fil, col + 1); recorrer (fil, col - 1); recorrer (fil + 1, col); recorrer (fil - 1, col); recorrer (fil - 1, col - 1); recorrer (fil - 1, col + 1); recorrer (fil + 1, col + 1); recorrer (fil + 1, col - 1); } else if (bot [fil] [col].getText ().equals ("1") == true || bot [fil] [col].getText ().equals ("2") == true || bot [fil] [col].getText ().equals ("3") == true || bot [fil] [col].getText ().equals ("4") == true || bot [fil] [col].getText ().equals ("5") == true || bot [fil] [col].getText ().equals ("6") == true || bot [fil] [col].getText ().equals ("7") == true || bot [fil] [col].getText ().equals ("8") == true) { bot [fil] [col].setBackground (Color.yellow); bot [fil] [col].setForeground (Color.black); } } } public static void main (String [] ar) { Buscaminas m = new Buscaminas (); m.setBounds (0, 0, 470, 600); m.setVisible(true); m.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); } }
No hay comentarios:
Publicar un comentario