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