91 - Recursividad: Problemas donde conviene aplicar la recursividad
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:
Recorrer un árbol de directorios en forma recursiva. Mostrar de cada directorios los archivos y directorios, luego descender a cada directorio y hacer la misma actividad.
Programa: ejercicio317.py
import os
def leer(directorio):
lista = os.listdir(directorio)
for elemento in lista:
if os.path.isfile(directorio+elemento):
print(elemento+" [archivo]")
if os.path.isdir(directorio+elemento):
print(elemento+" [directorio]")
leer(directorio+elemento+"/")
leer("c:/programaspython/")
Cuando ejecutamos este programa tenemos como resultado un listado de todos los archivos contenidos en la carpeta c:/programaspython/ y todas sus subcarpetas:
La función leer es recursiva ya que dentro de la misma se llama a leer.
Importamos el módulo 'os':
import os
Lo primero que hacemos dentro de la función leer es llamar a la función 'listdir' del módulo 'os' que lo que hace es retornar una lista con todos los nombres de archivos y directorios contenidos en la carpeta que le pasamos como parámetro (la primera vez que se llama la función leer recibe la carpeta 'c:/programaspython/'):
def leer(directorio):
lista = os.listdir(directorio)
Recorremos la lista en forma completa y por cada entrada en la lista verificamos si se trata de un archivo:
for elemento in lista:
if os.path.isfile(directorio+elemento):
print(elemento+" [archivo]")
O si dicho elemento se trata de una carpeta, en dicha situación además de imprimir el nombre de la carpeta procedemos a llamar en forma recursiva a la función leer pasando como parámetro dicha carpeta para que haga la misma actividad:
if os.path.isdir(directorio+elemento):
print(elemento+" [directorio]")
leer(directorio+elemento+"/")
Desde el bloque principal de nuestro programa llamamos por primera vez a la función 'leer' indicando a partir de que unidad y carpeta empezar a imprimir:
leer("c:/programaspython/")
Problema 2:
Desarrollar un programa que permita recorrer un laberinto e indique si tiene salida o no empleando la librería tkinter.
Para resolver este problema al laberinto lo representaremos con una lista de 10 elementos de tipo lista que en casa una hay 10 Label.
El valor:
0 Representa pasillo 1 Representa pared 9 Persona 5 Salida
A la salida ubicarla en la componente de la fila 9 y columna 9.
La persona comienza a recorrer el laberinto en la fila 0 y columna 0.
Los ceros y unos disponerlos en forma aleatoria.
Programa: ejercicio318.py
import tkinter as tk
from tkinter import ttk
import random
class Aplicacion:
def __init__(self):
self.ventana1=tk.Tk()
self.ventana1.title("Laberinto")
self.salida=False
self.generar_laberinto()
self.boton1=ttk.Button(self.ventana1, text="Recorrer", command=self.analizar)
self.boton1.grid(column=0, row=10, columnspan=5, padx=10, pady=10)
self.boton2=ttk.Button(self.ventana1, text="Generar otro", command=self.generar_otro)
self.boton2.grid(column=5, row=10, columnspan=5, padx=10, pady=10)
self.ventana1.mainloop()
def generar_laberinto(self):
self.tablero=[]
listafila=[]
for fila in range(0,10):
for columna in range(0,10):
label=ttk.Label(self.ventana1, text=self.retornar_aleatorio(), foreground="red")
label.grid(column=columna, row=fila, padx=10, pady=10)
listafila.append(label)
self.tablero.append(listafila)
listafila=[]
self.tablero[0][0].configure(text=0)
self.tablero[9][9].configure(text=5)
def generar_otro(self):
for fila in range(0,10):
for columna in range(0,10):
self.tablero[fila][columna].configure(text=self.retornar_aleatorio(),background="#f0f0f0")
self.tablero[0][0].configure(text=0)
self.tablero[9][9].configure(text=5)
def retornar_aleatorio(self):
valor=random.randint(1,4)
if valor==1:
return 1
else:
return 0
def analizar(self):
self.salida=False
self.recorrer(0,0)
if self.salida:
self.ventana1.title("Tiene salida el laberinto")
else:
self.ventana1.title("No tiene salida el laberinto")
def recorrer(self, fil, col):
if fil>=0 and fil<10 and col>=0 and col<10 and self.salida==False:
if self.tablero[fil][col].cget("text")==5:
self.salida=True
else:
if self.tablero[fil][col].cget("text")==0:
self.tablero[fil][col].configure(text=9)
self.tablero[fil][col].configure(background="yellow")
self.recorrer(fil,col+1)
self.recorrer(fil+1,col)
self.recorrer(fil-1,col)
self.recorrer(fil,col-1)
aplicacion1=Aplicacion()
Cuando ejecutamos el programa se genera un laberinto en forma aleatoria:
Cuando presionamos el botón "Recorrer" comenzamos a avanzar desde la fila 0 y columna 0:
En el método generar_laberinto mediante dos for anidados procedemos a crear cada uno de los objetos de tipo Label y almacenarlos en una lista:
def generar_laberinto(self):
self.tablero=[]
listafila=[]
for fila in range(0,10):
for columna in range(0,10):
label=ttk.Label(self.ventana1, text=self.retornar_aleatorio(), foreground="red")
label.grid(column=columna, row=fila, padx=10, pady=10)
listafila.append(label)
Cada vez que finaliza el for interno procedemos a almacenar en el atributo self.tablero la lista que acabamos de crear con las 10 Label:
self.tablero.append(listafila)
listafila=[]
Fuera de los for configuramos el inicio del laberinto con un valor 0 (pasillo) y el valor 5 para la salida del laberinto:
self.tablero[0][0].configure(text=0)
self.tablero[9][9].configure(text=5)
Cuando se presiona el botón para recorrer el laberinto se llama al método 'analizar' donde inicializamos el atributo 'salida' con el valor False presuponiendo que no tiene salida el laberinto:
def analizar(self):
self.salida=False
self.recorrer(0,0)
if self.salida:
self.ventana1.title("Tiene salida el laberinto")
else:
self.ventana1.title("No tiene salida el laberinto")
En el método 'analizar' llamamos al método recursivo 'recorrer' y lo comenzamos en la fila 0 y columna 0.
El método recursivo como vemos puede hacer múltiples llamadas recursivas:
def recorrer(self, fil, col):
if fil>=0 and fil<10 and col>=0 and col<10 and self.salida==False:
if self.tablero[fil][col].cget("text")==5:
self.salida=True
else:
if self.tablero[fil][col].cget("text")==0:
self.tablero[fil][col].configure(text=9)
self.tablero[fil][col].configure(background="yellow")
self.recorrer(fil,col+1)
self.recorrer(fil+1,col)
self.recorrer(fil-1,col)
self.recorrer(fil,col-1)
En el método 'recorrer' lo primero que verificamos que la coordenada a visitar esté dentro del tablero y que no hayamos encontrado la salida:
if fil>=0 and fil<10 and col>=0 and col<10 and self.salida==False:
Si el primer if se verifica verdadero pasamos a ver si en esa coordenada se encuentra la salida:
if self.tablero[fil][col].cget("text")==5:
self.salida=True
En caso de que no se encuentre la salida verificamos si estamos en una coordenada que hay pasillo:
else:
if self.tablero[fil][col].cget("text")==0:
En el caso que haya pasillo en dicha coordenada fijamos la persona disponiendo un 9 y cambiamos el color de fondo de dicha Label:
self.tablero[fil][col].configure(text=9)
self.tablero[fil][col].configure(background="yellow")
Finalmente tratamos de avanzar en las cuatro direcciones para seguir buscando la salida:
self.recorrer(fil,col+1)
self.recorrer(fil+1,col)
self.recorrer(fil-1,col)
self.recorrer(fil,col-1)
Problema 3:
Desarrollar el juego del Buscaminas. Definir una lista de 10 elementos de tipo lista y en estas listas internas almacenar las referencias a botones.
El juego consiste en destapar todas las casillas que no tiene bombas. Si se presiona la casilla que tiene bomba finaliza el juego. En las casillas que están en el perímetro de una bomba aparece un número que indica la cantidad de bombas a su alrededor. Por ejemplo si una casilla tiene el 2 significa que de las 8 casillas a su alrededor hay 2 bombas.
Si se selecciona una casilla que no tiene bombas a su alrededor se libera esta y todas las que se encuentran próximas a ella.
Permitir volver a jugar mediante un menú de opciones.
Cuando se inicia el juego debe aparecer el tablero con las 100 casillas:
Luego de destapar algunas casillas:
Programa: ejercicio319.py
import tkinter as tk
from tkinter import ttk
import random
from tkinter import messagebox as mb
class Aplicacion:
def __init__(self):
self.ventana1=tk.Tk()
self.destapadas=0
self.enjuego=True
self.ventana1.geometry("500x500")
self.ventana1.title("Buscaminas")
self.ventana1.configure(background="#BEF781")
self.generar_tablero()
self.generar_bombas()
self.generar_bombas_proximas()
menubar1 = tk.Menu(self.ventana1)
self.ventana1.config(menu=menubar1)
opciones1 = tk.Menu(menubar1)
opciones1.add_command(label="Reiniciar", command=self.reiniciar)
opciones1.add_command(label="Salir", command=self.ventana1.destroy)
menubar1.add_cascade(label="Opciones", menu=opciones1)
self.ventana1.mainloop()
def generar_tablero(self):
self.tablero=[]
listafila=[]
for fila in range(0,10):
for columna in range(0,10):
boton=ttk.Button(self.ventana1, text="", command=lambda fi=fila, co=columna: self.presion(fi,co))
boton.place(x=columna*50,y=fila*50,width=50,height=50)
listafila.append(boton)
self.tablero.append(listafila)
listafila=[]
def generar_bombas(self):
self.bombas=[]
listafila=[]
for fila in range(0,10):
for columna in range(0,10):
listafila.append("0")
self.bombas.append(listafila)
listafila=[]
cantidad=10
while cantidad!=0:
fila=random.randint(0,9)
columna=random.randint(0,9)
if self.bombas[fila][columna]!="b":
self.bombas[fila][columna]="b"
#self.tablero[fila][columna].configure(text="b")
cantidad=cantidad-1
def generar_bombas_proximas(self):
for f in range(0,10):
for c in range(0,10):
if self.bombas[f][c]=="0":
cant=self.contar_lado(f,c)
self.bombas[f][c]=str(cant)
def contar_lado(self, fila, columna):
total=0
if fila-1>=0 and columna-1>=0:
if self.bombas[fila-1][columna-1]=="b":
total=total+1
if fila-1>=0:
if self.bombas[fila-1][columna]=="b":
total=total+1
if fila-1>=0 and columna+1<10:
if self.bombas[fila-1][columna+1]=="b":
total=total+1
if columna+1<10:
if self.bombas[fila][columna+1]=="b":
total=total+1
if fila+1<10 and columna+1<10:
if self.bombas[fila+1][columna+1]=="b":
total=total+1
if fila+1<10:
if self.bombas[fila+1][columna]=="b":
total=total+1
if fila+1<10 and columna-1>=0:
if self.bombas[fila+1][columna-1]=="b":
total=total+1
if columna-1>=0:
if self.bombas[fila][columna-1]=="b":
total=total+1
return total
def presion(self, fila, columna):
if self.enjuego:
if self.bombas[fila][columna]=="b":
self.enjuego=False
self.destapar()
mb.showinfo("Información", "Perdiste hay una bomba")
else:
if int(self.bombas[fila][columna])==0:
self.recorrer(fila,columna)
else:
if int(self.bombas[fila][columna])>=1 and int(self.bombas[fila][columna])<=8 and self.tablero[fila][columna].cget("text")=="":
self.tablero[fila][columna].configure(text=self.bombas[fila][columna])
self.destapadas=self.destapadas+1
if self.destapadas==90:
self.enjuego=False
mb.showinfo("Información", "Ganaste")
def recorrer(self, fil, col):
if fil>=0 and fil<10 and col>=0 and col<10:
if self.bombas[fil][col]=="0" and self.tablero[fil][col]!=None:
self.bombas[fil][col]=" "
self.destapadas=self.destapadas+1
self.tablero[fil][col].destroy()
self.tablero[fil][col]=None
self.recorrer (fil, col + 1)
self.recorrer (fil, col - 1)
self.recorrer (fil + 1, col)
self.recorrer (fil - 1, col)
self.recorrer (fil - 1, col - 1)
self.recorrer (fil - 1, col + 1)
self.recorrer (fil + 1, col + 1)
self.recorrer (fil + 1, col - 1)
else:
if self.tablero[fil][col]!=None:
if int(self.bombas[fil][col])>=1 and int(self.bombas[fil][col])<=8 and self.tablero[fil][col].cget("text")=="":
self.tablero[fil][col].configure(text=self.bombas[fil][col])
self.destapadas=self.destapadas+1
def reiniciar(self):
self.destapadas=0
self.eliminar_botones()
self.generar_tablero()
self.generar_bombas()
self.generar_bombas_proximas()
self.enjuego=True
def eliminar_botones(self):
for fila in range(0,10):
for columna in range(0,10):
if self.tablero[fila][columna]!=None:
self.tablero[fila][columna].destroy()
self.tablero[fila][columna]=None
def destapar(self):
for fila in range(0,10):
for columna in range(0,10):
if self.tablero[fila][columna]!=None:
if self.bombas[fila][columna]!="0":
self.tablero[fila][columna].configure(text=self.bombas[fila][columna])
aplicacion1=Aplicacion()
La recursividad en este problema se utiliza cuando hay que destapar casillas libres a su alrededor en el método recorrer.