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:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Recursividad7
{
public class Recursividad
{
class Nodo
{
public int info;
public Nodo sig;
}
private Nodo raiz;
void InsertarPrimero(int x)
{
Nodo nuevo = new Nodo ();
nuevo.info = x;
nuevo.sig=raiz;
raiz=nuevo;
}
private void ImprimirInversa(Nodo reco)
{
if (reco!=null)
{
ImprimirInversa(reco.sig);
Console.Write(reco.info+"-");
}
}
public void ImprimirInversa ()
{
ImprimirInversa(raiz);
}
static void Main(string[] args)
{
Recursividad r=new Recursividad();
r.InsertarPrimero (10);
r.InsertarPrimero(4);
r.InsertarPrimero(5);
r.ImprimirInversa();
Console.ReadKey();
}
}
}
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.
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:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace Recursividad8
{
public class Recursividad
{
public void Leer(string inicio)
{
String[] archivos=Directory.GetFiles(inicio);
Console.WriteLine(inicio + " (Directorio)");
for(int f=0;f < archivos.Length;f++)
{
Console.WriteLine(archivos[f]+" (Archivo)");
}
String[]directorios=Directory.GetDirectories(inicio);
for(int f=0;f < directorios.Length;f++)
{
Leer(directorios[f]);
}
}
static void Main(string[] args)
{
Recursividad rec = new Recursividad();
rec.Leer("c:\\Windows\\");
Console.WriteLine();
Console.ReadKey();
}
}
}
Debemos importar el espacio de nombres System.IO (donde se encuentra la clase Directory):
using System.IO;
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)
El método estático GetFiles de la clase Directory retorna todos los archivos contenidos en la carpeta que le pasamos como parámetro. Seguidamente imprimimos todos los archivos:
String[] archivos=Directory.GetFiles(inicio);
Console.WriteLine(inicio + " (Directorio)");
for(int f=0;f < archivos.Length;f++)
{
Console.WriteLine(archivos[f]+" (Archivo)");
}
Ahora obtenemos todos los directorios contenidos en la carpeta actual y llamamos en forma recursiva para cada directorio:
String[]directorios=Directory.GetDirectories(inicio);
for(int f=0;f < directorios.Length;f++)
{
Leer(directorios[f]);
}
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 Label.
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
El código fuente de la aplicación la podemos descargar de aquí.
Programa:
archivo: Form1.Designer.cs
namespace Laberinto
{
partial class Form1
{
///
/// Variable del diseñador requerida.
///
private System.ComponentModel.IContainer components = null;
///
/// Limpiar los recursos que se estén utilizando.
///
/// true si los recursos administrados se deben eliminar; false en caso contrario, false.
protected override void Dispose(bool disposing)
{
if (disposing && (components != null))
{
components.Dispose();
}
base.Dispose(disposing);
}
#region Código generado por el Diseñador de Windows Forms
///
/// Método necesario para admitir el Diseñador. No se puede modificar
/// el contenido del método con el editor de código.
///
private void InitializeComponent()
{
this.button1 = new System.Windows.Forms.Button();
this.button2 = new System.Windows.Forms.Button();
this.SuspendLayout();
//
// button1
//
this.button1.Location = new System.Drawing.Point(11, 15);
this.button1.Name = "button1";
this.button1.Size = new System.Drawing.Size(75, 23);
this.button1.TabIndex = 0;
this.button1.Text = "Verificar";
this.button1.UseVisualStyleBackColor = true;
this.button1.Click += new System.EventHandler(this.button1_Click);
//
// button2
//
this.button2.Location = new System.Drawing.Point(93, 15);
this.button2.Name = "button2";
this.button2.Size = new System.Drawing.Size(124, 23);
this.button2.TabIndex = 1;
this.button2.Text = "Otro laberinto";
this.button2.UseVisualStyleBackColor = true;
this.button2.Click += new System.EventHandler(this.button2_Click);
//
// Form1
//
this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
this.ClientSize = new System.Drawing.Size(345, 428);
this.Controls.Add(this.button2);
this.Controls.Add(this.button1);
this.Name = "Form1";
this.Text = "Form1";
this.Load += new System.EventHandler(this.Form1_Load);
this.ResumeLayout(false);
}
#endregion
private System.Windows.Forms.Button button1;
private System.Windows.Forms.Button button2;
}
}
archivo: Form1.cs
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace Laberinto
{
public partial class Form1 : Form
{
private Label[,] mat;
private bool salida;
public Form1()
{
InitializeComponent();
}
private void Form1_Load(object sender, EventArgs e)
{
int x = 10;
int y = 50;
mat=new Label[10,10];
for (int fil = 0; fil < mat.GetLength(0); fil++)
{
for (int col = 0; col < mat.GetLength(1); col++)
{
mat[fil, col] = new Label();
mat[fil, col].Location = new Point(x, y);
mat[fil, col].Size = new Size(30, 30);
Controls.Add(mat[fil, col]);
x = x + 32;
}
y = y + 32;
x = 10;
}
Crear();
}
private void Crear()
{
Text = "";
button1.Enabled = true;
Random ale=new Random();
for(int f = 0; f < 10; f++)
{
for(int c = 0; c < 10; c++)
{
mat[f, c].BackColor = Color.Azure;
int a=ale.Next(0,4);
if (a==0)
mat[f,c].Text="1";
else
mat[f,c].Text="0";;
}
}
mat[9,9].Text="s";
mat[0,0].Text="0";
}
private void Recorrer(int fil, int col)
{
if (fil >= 0 && fil < 10 && col >= 0 && col < 10 && salida == false)
{
if (mat[fil,col].Text=="s")
salida = true;
else
if (mat[fil,col].Text=="0")
{
mat[fil,col].Text="9";
mat[fil,col].BackColor=Color.Red;
Recorrer(fil, col + 1);
Recorrer(fil + 1, col);
Recorrer(fil - 1, col);
Recorrer(fil, col - 1);
}
}
}
private void button1_Click(object sender, EventArgs e)
{
button1.Enabled = false;
salida = false;
Recorrer(0, 0);
if (salida == true)
Text = "Tiene salida";
else
Text = "No tiene salida";
}
private void button2_Click(object sender, EventArgs e)
{
Crear();
}
}
}
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 (mat[fil,col].Text=="s")
salida = true;
En el caso que no estemos en la salida verificamos si estamos en pasillo:
if (mat[fil,col].Text=="0")
{
En caso de estar en el pasillo procedemos a fijar dicha Label con el caracter "9" e intentamos desplazarnos en las cuatro direcciones (arriba, abajo, derecha e izquierda), este desplazamiento lo logramos llamando recursivamente:
mat[fil,col].Text="9";
mat[fil,col].BackColor=Color.Red;
Recorrer(fil, col + 1);
Recorrer(fil + 1, col);
Recorrer(fil - 1, col);
Recorrer(fil, col - 1);
Problemas propuestos
-
Desarrollar el juego del Buscaminas. Definir una matriz de 10*10 de Button 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.
El código fuente de la aplicación la podemos descargar de aquí.
archivo: Form1.Designer.cs namespace Buscaminas { partial class Form1 { ////// Variable del diseñador requerida. /// private System.ComponentModel.IContainer components = null; ////// Limpiar los recursos que se estén utilizando. /// /// true si los recursos administrados se deben eliminar; false en caso contrario, false. protected override void Dispose(bool disposing) { if (disposing && (components != null)) { components.Dispose(); } base.Dispose(disposing); } #region Código generado por el Diseñador de Windows Forms ////// Método necesario para admitir el Diseñador. No se puede modificar /// el contenido del método con el editor de código. /// private void InitializeComponent() { this.button1 = new System.Windows.Forms.Button(); this.SuspendLayout(); // // button1 // this.button1.Location = new System.Drawing.Point(13, 13); this.button1.Name = "button1"; this.button1.Size = new System.Drawing.Size(75, 23); this.button1.TabIndex = 0; this.button1.Text = "Reiniciar"; this.button1.UseVisualStyleBackColor = true; this.button1.Click += new System.EventHandler(this.button1_Click); // // Form1 // this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F); this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font; this.ClientSize = new System.Drawing.Size(496, 448); this.Controls.Add(this.button1); this.Name = "Form1"; this.Text = "Form1"; this.Load += new System.EventHandler(this.Form1_Load); this.ResumeLayout(false); } #endregion private System.Windows.Forms.Button button1; } } archivo: Form1.cs using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms; namespace Buscaminas { public partial class Form1 : Form { private Button[,] mat; public Form1() { InitializeComponent(); } private void Form1_Load(object sender, EventArgs e) { int x = 10; int y = 50; mat = new Button[10, 10]; for (int fil = 0; fil < mat.GetLength(0); fil++) { for (int col = 0; col < mat.GetLength(1); col++) { mat[fil, col] = new Button(); mat[fil, col].Text = "0"; mat[fil, col].Location = new Point(x, y); mat[fil, col].Size = new Size(30, 30); mat[fil, col].Click += Presionado; Controls.Add(mat[fil, col]); x = x + 30; } y = y + 30; x = 10; } Reiniciar(); } void Reiniciar() { Text=""; for (int f = 0; f < 10; f++) { for (int c = 0; c < 10; c++) { mat[f,c].Text="0"; mat[f,c].Enabled = true; ; mat[f,c].ForeColor=Color.LightGray; mat[f,c].BackColor=Color.LightGray; } } DisponerBombas(); ContarBombasPerimetro(); } void DisponerBombas() { int cantidad = 10; Random ale = new Random(); do { int fila = ale.Next(0, 10); int columna = ale.Next(0, 10); if (mat[fila,columna].Text!="b") { mat[fila,columna].Text="b"; cantidad--; } } while (cantidad != 0); } void ContarBombasPerimetro() { for (int f = 0; f < 10; f++) { for (int c = 0; c < 10; c++) { if (mat[f,c].Text=="0") { int cant = ContarCoordenada(f, c); mat[f,c].Text=cant.ToString(); } } } } int ContarCoordenada(int fila, int columna) { int total = 0; if (fila - 1 >= 0 && columna - 1 >= 0) { if (mat[fila - 1,columna - 1].Text=="b") total++; } if (fila - 1 >= 0) { if (mat[fila - 1,columna].Text=="b") total++; } if (fila - 1 >= 0 && columna + 1 < 10) { if (mat[fila - 1,columna + 1].Text=="b") total++; } if (columna + 1 < 10) { if (mat[fila,columna + 1].Text=="b") total++; } if (fila + 1 < 10 && columna + 1 < 10) { if (mat[fila + 1,columna + 1].Text=="b") total++; } if (fila + 1 < 10) { if (mat[fila + 1,columna].Text=="b") total++; } if (fila + 1 < 10 && columna - 1 >= 0) { if (mat[fila + 1,columna - 1].Text=="b") total++; } if (columna - 1 >= 0) { if (mat[fila,columna - 1].Text=="b") total++; } return total; } private void button1_Click(object sender, EventArgs e) { Reiniciar(); } private void Presionado(object sender, EventArgs e) { for (int f = 0; f < 10; f++) { for (int c = 0; c < 10; c++) { if (sender == mat[f,c]) { if (mat[f,c].Text=="b") { Text="Boooooooooooooomm"; DesactivarJuego(); } else if (mat[f,c].Text=="0") { Recorrer(f, c); } else if (mat[f,c].Text=="1" || mat[f,c].Text=="2" || mat[f,c].Text=="3" || mat[f,c].Text=="4" || mat[f,c].Text=="5" || mat[f,c].Text=="6" || mat[f,c].Text=="7" || mat[f,c].Text=="8") { mat[f,c].BackColor=Color.Yellow; mat[f,c].ForeColor=Color.Black; } } } } VerificarTriunfo(); } void DesactivarJuego() { for (int f = 0; f < 10; f++) { for (int c = 0; c < 10; c++) { mat[f,c].Enabled=false; } } } void VerificarTriunfo() { int cant = 0; for (int f = 0; f < 10; f++) { for (int c = 0; c < 10; c++) { Color col = mat[f,c].BackColor; if (col == Color.Yellow) cant++; } } if (cant == 90) { Text="Ganooooooooo"; DesactivarJuego(); } } void Recorrer(int fil, int col) { if (fil >= 0 && fil < 10 && col >= 0 && col < 10) { if (mat[fil,col].Text=="0") { mat[fil,col].Text=" "; mat[fil,col].BackColor=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 (mat[fil,col].Text=="1" || mat[fil,col].Text == "2" || mat[fil,col].Text == "3" || mat[fil,col].Text == "4" || mat[fil,col].Text == "5" || mat[fil,col].Text == "6" || mat[fil,col].Text == "7" || mat[fil,col].Text == "8") { mat[fil,col].BackColor=Color.Yellow; mat[fil,col].ForeColor=Color.Black; } } } } }