Algoritmi Ricorsivi

2.1 Scansione dell'albero dei file

Diamo un'occhiata a un algoritmo ricorsivo per la scansione dell'albero dei file. L'algoritmo navigherà attraverso la directory e tutte le sue sottodirectory, elencando tutti i file e le cartelle.

import os

def list_files_recursive(directory, indent=0):
    # Otteniamo la lista di tutti i file e cartelle nella directory corrente
    items = os.listdir(directory)
                
    for item in items:
        # Creiamo il percorso completo al file o cartella
        path = os.path.join(directory, item)
                    
        # Visualizziamo con l'indentazione per una migliore comprensione della struttura
        print(' ' * indent + item)
                    
        # Se è una cartella, scansioniamo ricorsivamente il suo contenuto
        if os.path.isdir(path):
            list_files_recursive(path, indent + 4)
            
# Esempio di utilizzo
root_directory = '/path/to/root/directory'
list_files_recursive(root_directory)

Come funziona?

1. Funzione list_files_recursive(directory, indent=0):
   • directory — directory corrente di cui vogliamo elencare il contenuto.
   • indent — livello di indentazione corrente per mostrare la nidificazione di file e cartelle.
2. Otteniamo la lista di tutti i file e cartelle nella directory corrente usando os.listdir(directory).
3. Iteriamo su ogni elemento nella lista items.
4. Creiamo il percorso completo all'elemento usando os.path.join(directory, item).
5. Visualizziamo il nome dell'elemento con l'indentazione, che aumenta di 4 spazi per ogni livello di nidificazione.
6. Controlliamo se l'elemento è una cartella usando os.path.isdir(path). Se sì, richiamiamo ricorsivamente list_files_recursive(path, indent + 4) per scansionare il suo contenuto.

Esempio di output:

Supponiamo di avere la seguente struttura di directory:

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

Eseguendo la funzione list_files_recursive(root_directory) otteniamo il seguente output:

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

Questo algoritmo scansiona ricorsivamente l'albero delle directory, visualizzando tutti i file e le cartelle tenendo conto della loro struttura nidificata.

2.2 Torri di Hanoi

Il problema delle "Torri di Hanoi"

Le Torri di Hanoi sono un classico problema ricorsivo che comporta lo spostamento di dischi da un perno all'altro usando un perno ausiliario.

Regole:

1. È possibile spostare un solo disco alla volta.
2. Un disco può essere posizionato solo su un perno vuoto o su un disco di dimensioni maggiori.
3. È necessario spostare tutti i dischi da un perno all'altro, utilizzando il perno ausiliario.

Ecco un algoritmo ricorsivo per risolvere questo problema:

L'algoritmo delle Torri di Hanoi risolve il problema nel seguente modo:

1. Spostare n - 1 dischi dal perno iniziale all'ausiliario, usando il perno di destinazione.
2. Spostare il disco rimanente dal perno iniziale a quello di destinazione.
3. Spostare n - 1 dischi dal perno ausiliario a quello di destinazione, usando il perno iniziale.

Esempio in Python

def hanoi_tower(n, source, target, auxiliary):
    if n == 1:
        print(f"Sposta il disco 1 da {source} a {target}")
        return
    hanoi_tower(n - 1, source, auxiliary, target)
    print(f"Sposta il disco {n} da {source} a {target}")
    hanoi_tower(n - 1, auxiliary, target, source)
        
# Esempio di utilizzo:
n = 3  # Numero di dischi
hanoi_tower(n, 'A', 'C', 'B')
        

Come funziona?

Caso base:

Se c'è un solo disco (n == 1), allora può essere semplicemente spostato dal perno iniziale a quello di destinazione.

if n == 1:
    print(f"Sposta il disco 1 da {source} a {target}")
    return

Caso ricorsivo:

Passaggio 1. Sposta n-1 dischi dal perno iniziale a quello ausiliario, usando il perno di destinazione.

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

Passaggio 2. Sposta il disco n dal perno iniziale a quello di destinazione.

print(f"Sposta il disco {n} da {source} a {target}")

Passaggio 3. Sposta n - 1 dischi dal perno ausiliario a quello di destinazione, usando il perno iniziale.

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

Esempio di output:

Per tre dischi (n = 3) sui perni A, B e C, il programma mostrerà:

Sposta il disco 1 da A a C
Sposta il disco 2 da A a B
Sposta il disco 1 da C a B
Sposta il disco 3 da A a C
Sposta il disco 1 da B a A
Sposta il disco 2 da B a C
Sposta il disco 1 da A a C

2.3 Fiocco di neve di Koch

Disegnare un fiocco di neve usando la ricorsione è un compito interessante, spesso utilizzato per studiare i frattali. Uno dei modi più semplici per disegnare un fiocco di neve è usare la curva di Koch, che è una curva frattale.

Algoritmo per disegnare il fiocco di neve di Koch

La curva di Koch è costruita nel seguente modo:

• Iniziamo con una linea retta.
• Dividiamo ciascun segmento in tre parti e sostituiamo la parte centrale con una piccola curva che ricorda un "angolino".
• Ripetiamo questo processo ricorsivamente per ciascun segmento.

Istruzioni passo passo

• Inizio: Disegna il segmento iniziale.
• Divisione: Dividi ciascun segmento in tre parti.
• Sostituisci la parte centrale: Sul segmento centrale disegna un "angolino", costituito da due linee che formano un angolo di 60 gradi.
• Ripeti il processo: Continua questo processo per ciascun segmento.

Esempio in Python usando la libreria 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)
            
# Configurazione dello schermo
screen = turtle.Screen()
screen.bgcolor("sky blue")
            
# Configurazione della tartaruga
t = turtle.Turtle()
t.speed(0)
t.color("white")
            
# Disegniamo il fiocco di neve
t.penup()
t.goto(-100, 50)
t.pendown()
draw_snowflake(t, 300, 4)
            
# Fine del disegno
turtle.done()
            

Come funziona?

1. Funzione draw_koch_curve(t, length, depth):

• t: la tartaruga che disegna.
• length: la lunghezza del segmento.
• depth: la profondità della ricorsione, che determina il livello di dettaglio.

2. Caso base:

Se depth è uguale a 0, la tartaruga disegna un segmento diritto.

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

3. Caso ricorsivo:

Dividi il segmento in tre parti, e applica draw_koch_curve ricorsivamente a ciascuna parte, aggiungendo delle rotazioni.

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. Funzione draw_snowflake(t, length, depth):

Disegna tre curve di Koch unite in un singolo fiocco di neve.

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

Come eseguire il codice?

• Assicurati di avere la libreria Turtle installata (pip install PythonTurtle).
• Copia e incolla il codice in un file .py e eseguilo. Vedrai disegnare un fiocco di neve sullo schermo.

Questo algoritmo permette di visualizzare la struttura frattale del fiocco di neve utilizzando semplici principi di ricorsione e costruzioni geometriche.