Algoritmos Recursivos

2.1 Recorrido del Árbol de Archivos

Vamos a ver un algoritmo recursivo para recorrer un árbol de archivos. El algoritmo recorrerá un directorio y todos sus subdirectorios, mostrando una lista de todos los archivos y carpetas.

import os

def list_files_recursive(directory, indent=0):
    # Obtener la lista de todos los archivos y carpetas en el directorio actual
    items = os.listdir(directory)
                
    for item in items:
        # Crear la ruta completa hacia el archivo o carpeta
        path = os.path.join(directory, item)
                    
        # Imprimir con sangría para una mejor percepción de la estructura
        print(' ' * indent + item)
                    
        # Si es una carpeta, recorrer su contenido recursivamente
        if os.path.isdir(path):
            list_files_recursive(path, indent + 4)
            
# Ejemplo de uso
root_directory = '/path/to/root/directory'
list_files_recursive(root_directory)

¿Cómo funciona esto?

1. Función list_files_recursive(directory, indent=0):
   • directory — el directorio actual cuyo contenido queremos mostrar.
   • indent — el nivel actual de sangría para mostrar la jerarquía de archivos y carpetas.
2. Obtenemos la lista de todos los archivos y carpetas en el directorio actual usando os.listdir(directory).
3. Iteramos a través de cada elemento en la lista items.
4. Crear la ruta completa del elemento usando os.path.join(directory, item).
5. Imprimir el nombre del elemento con sangría, que aumenta 4 espacios por cada nivel de jerarquía.
6. Verificamos si el elemento es una carpeta usando os.path.isdir(path). Si lo es, llamamos recursivamente a list_files_recursive(path, indent + 4) para recorrer su contenido.

Ejemplo de salida:

Supongamos que tenemos la siguiente estructura de directorios:

root_directory/
    file1.txt
    dir1/
        file2.txt
        file3.txt
        dir2/
            file4.txt
    file5.txt

Al ejecutar la función list_files_recursive(root_directory) obtendremos la siguiente salida:

file1.txt
dir1
    file2.txt
    file3.txt
    dir2
        file4.txt
file5.txt

Este algoritmo recorre recursivamente el árbol de directorios, mostrando todos los archivos y carpetas respetando su jerarquía.

2.2 Torres de Hanói

El problema de las "Torres de Hanói"

Las Torres de Hanói es un clásico problema recursivo que implica mover discos de una varilla a otra usando una varilla auxiliar.

Reglas:

1. Solo se puede mover un disco a la vez.
2. Un disco solo se puede colocar sobre una varilla vacía o sobre un disco de mayor tamaño.
3. Debes mover todos los discos de una varilla a otra, usando la varilla auxiliar.

Aquí hay un algoritmo recursivo para resolver este problema:

El algoritmo de las Torres de Hanói resuelve el problema de la siguiente manera:

1. Mover n - 1 discos de la varilla inicial a la auxiliar, usando la varilla destino.
2. Mover el disco restante de la varilla inicial a la varilla destino.
3. Mover n - 1 discos de la varilla auxiliar a la varilla destino, usando la varilla inicial.

Ejemplo en Python

def hanoi_tower(n, source, target, auxiliary):
    if n == 1:
        print(f"Mover disco 1 de {source} a {target}")
        return
    hanoi_tower(n - 1, source, auxiliary, target)
    print(f"Mover disco {n} de {source} a {target}")
    hanoi_tower(n - 1, auxiliary, target, source)
        
# Ejemplo de uso:
n = 3  # Cantidad de discos
hanoi_tower(n, 'A', 'C', 'B')
        

¿Cómo funciona esto?

Caso base:

Si solo hay un disco (n == 1), simplemente se puede mover de la varilla inicial a la varilla destino.

if n == 1:
    print(f"Mover disco 1 de {source} a {target}")
    return

Caso recursivo:

Paso 1. Mover n-1 discos de la varilla inicial a la auxiliar, usando la varilla destino.

hanoi_tower(n - 1, source, auxiliary, target)

Paso 2. Mover el disco n de la varilla inicial a la varilla destino.

print(f"Mover disco {n} de {source} a {target}")

Paso 3. Mover n - 1 discos de la varilla auxiliar a la varilla destino, usando la varilla inicial.

hanoi_tower(n - 1, auxiliary, target, source)

Ejemplo de salida:

Para tres discos (n = 3) en las varillas A, B y C, el programa mostrará:

Mover disco 1 de A a C
Mover disco 2 de A a B
Mover disco 1 de C a B
Mover disco 3 de A a C
Mover disco 1 de B a A
Mover disco 2 de B a C
Mover disco 1 de A a C

2.3 Copo de Nieve de Koch

Dibujar un copo de nieve usando recursión es una tarea interesante, que a menudo se utiliza para el estudio de fractales. Una de las formas más sencillas de dibujar un copo de nieve es usando la curva de Koch, que es una curva fractal.

Algoritmo para dibujar el Copo de Nieve de Koch

La curva de Koch se construye de la siguiente manera:

• Comenzamos con una línea recta.
• Dividir cada segmento en tres partes y reemplazar la parte central con una pequeña curva que parece un "esquina".
• Repetimos este proceso de forma recursiva para cada segmento.

Instrucciones paso a paso

• Inicio: Dibuja el segmento inicial.
• División: Divide cada segmento en tres partes.
• Reemplaza la parte central: En la parte central dibuja una "esquina", formada por dos líneas que crean un ángulo de 60 grados.
• Repite el proceso: Continúa este proceso para cada segmento.

Ejemplo en Python usando la biblioteca Turtle

import turtle

def draw_koch_curve(t, length, depth):
    if depth == 0:
        t.forward(length)
    else:
        length /= 3.0
        draw_koch_curve(t, length, depth - 1)
        t.left(60)
        draw_koch_curve(t, length, depth - 1)
        t.right(120)
        draw_koch_curve(t, length, depth - 1)
        t.left(60)
        draw_koch_curve(t, length, depth - 1)
            
def draw_snowflake(t, length, depth):
    for _ in range(3):
        draw_koch_curve(t, length, depth)
        t.right(120)
            
# Configurar la pantalla
screen = turtle.Screen()
screen.bgcolor("sky blue")
            
# Configurar la tortuga
t = turtle.Turtle()
t.speed(0)
t.color("white")
            
# Dibujar el copo de nieve
t.penup()
t.goto(-100, 50)
t.pendown()
draw_snowflake(t, 300, 4)
            
# Finalizar dibujo
turtle.done()
            

¿Cómo funciona esto?

1. Función draw_koch_curve(t, length, depth):

• t: la tortuga que dibuja.
• length: longitud del segmento.
• depth: profundidad de la recursión, que determina el nivel de detalle.

2. Caso base:

Si depth es igual a 0, la tortuga dibuja un segmento recto.

if depth == 0:
    t.forward(length)
        

3. Caso recursivo:

Divide el segmento en tres partes y aplica draw_koch_curve recursivamente a cada parte, añadiendo giros.

length /= 3.0
draw_koch_curve(t, length, depth - 1)
t.left(60)
draw_koch_curve(t, length, depth - 1)
t.right(120)
draw_koch_curve(t, length, depth - 1)
t.left(60)
draw_koch_curve(t, length, depth - 1)

4. Función draw_snowflake(t, length, depth):

Dibuja tres curvas de Koch conectadas en un copo de nieve.

for _ in range(3):
    draw_koch_curve(t, length, depth)
    t.right(120)

¿Cómo ejecutar el código?

• Asegúrate de tener instalada la biblioteca Turtle (pip install PythonTurtle).
• Copia y pega el código en un archivo .py y ejecútalo. Verás cómo se dibuja el copo de nieve en la pantalla.

Este algoritmo permite visualizar la estructura fractal de un copo de nieve utilizando principios simples de recursión y construcciones geométricas.