# ---
# jupyter:
#   jupytext:
#     formats: ipynb,py:percent
#     text_representation:
#       extension: .py
#       format_name: percent
#       format_version: '1.3'
#       jupytext_version: 1.15.2
#   kernelspec:
#     display_name: Python 3 (ipykernel)
#     language: python
#     name: python3
# ---

# %% [markdown] slideshow={"slide_type": "slide"}
# # Fondamenti di Programmazione <a class="tocSkip"> <img align=right width=20% src=sap.png />
#
#
# **Andrea Sterbini**
#
# lezione 16 - 16 novembre 2023

# %% slideshow={"slide_type": "notes"}
# %load_ext nb_mypy

# %% RECAP [markdown] slideshow={"slide_type": "slide"}
# # RECAP:
# - Colori come oggetti (con matematica dei colori)
# - Immagini come matrici di Colori
# - Filtri come oggetti che generano il colore del nuovo pixel
# - Figure geometriche

# %% Come si analizza un problema in stile Object-Oriented [markdown] slideshow={"slide_type": "slide"}
#
# # METODOLOGIA di analisi Object Oriented 
# - Si individuano le strutture dati necessarie (**class**)
# - con i loro **attributi** (informazioni "personali" di ciascun dato)
#   - se una informazione è identica e comune a tutti gli individui la posso mettere come **attributo di classe**
# - si definisce la loro inizializzazione (**`__init__`**) con gli argomenti necessari
# - i **metodi** fondamentali (operazione sui dati o che calcolano valori a partire dagli attributi)
#   - se vogliamo creare l'oggetto in altri modi possiamo creare un **@classmethod**
#
# Ogni volta che vogliamo aggiungere una funzionalità ci dobbiamo chiedere 
# quale oggetto deve essere "responsabile" (oppure "conosce le informazioni") per calcolarla
#
# **Metafora dell'ufficio**
# - E' un po' come voler organizzare un ufficio con persone che hanno **tipi di mansioni** diverse
#   - ciascuno ha le sue informazioni e si cerca di non assegnarle a più uffici (classi)
#   - gli scambi tra impiegati devono essere minimi
#

# %%% Ereditarietà: estensione delle info e delle funzionalità di una classe di oggetti [markdown] slideshow={"slide_type": "slide"}
#
# # Ereditarietà (Specializzazione/ Riuso e Ampliamento delle funzionalita)
# Se si vede che diverse classi condividono dei comportamenti/attributi comuni
# - definiamo una super-classe che contiene l'implementazione comune dei metodi o gli attributi comuni
# - nelle sottoclassi che ereditano da questa mettiamo solo gli attributi diversi ed i metodi diversi
#    (se necessario c'è anche il modo di chiamare i metodi della superclasse)
#
# Esempio: tutti gli animali visualizzati in un gioco hanno una posizione, una icona, un verso ...
#  l'insieme degli attributi e metodi comuni può essere messo nella classe Animale
#  da cui ereditano Cane, Gatto, Cavallo, Ornitorinco ....

# %%% Esempio: figure geometriche da disegnare con la turtle slideshow={"slide_type": "slide"}
# Tutte le Figure hanno:
# - posizione
# - colore
# - un metodo che le disegna (che per default non fa nulla)
# - un metodo che ne calcola l'area (per default 0)

# Ciascuna specifica figura
# - ha dei parametri specifici (raggio, lati, cateti, fuochi, retta e fuoco, ...)
# - ha il suo metodo specifico che la disegna
# - ha il suo metodo specifico che ne calcola l'area

# definiamo la gerarchia di classi: 
# Figura
#   Punto
#   Linea
#       Freccia
#   Rettangolo
#       Quadrato
#       TriangoloRettangolo
#   PoligonoRegolare
#       Triangolo
#       Pentagono
#   EllisseApprossimataDaCerchi
#       Cerchio
import turtle
t = turtle.Turtle()
turtle.colormode(255)


# %%% Esempio: figure geometriche da disegnare con la turtle slideshow={"slide_type": "slide"}
class Figura:
    def __init__(self, x, y, colore, direzione=0, spessore=1, campitura=None):
        self._x = x
        self._y = y
        self._colore = colore
        self._direzione = direzione
        self._spessore = spessore
        self._campitura = campitura

    def area(self):
        raise NotImplementedError("Il metodo 'area' non è stato implementato")

    def draw(self, turtle):
        turtle.end_fill()
        turtle.up()
        turtle.goto(self._x,self._y)
        turtle.setheading(self._direzione)
        turtle.color(self._colore)
        turtle.pensize(self._spessore)
        turtle.down()
        if self._campitura:
            turtle.fillcolor(self._campitura)
            turtle.begin_fill()
        
    def move(self, x, y):
        self._x = x
        self._y = y


# %%
#help(turtle)

# %%% Esempio: figure geometriche da disegnare con la turtle slideshow={"slide_type": "slide"}
        
class Rettangolo(Figura):
    def __init__(self, x, y, colore, larghezza, altezza, 
                 direzione=0, spessore=1, campitura=None):
        "creo un nuovo rettangolo"
        # riuso l'inizializzazione della mia superclasse per
        # gli attributi che già sa gestire
        super().__init__(x, y, colore, direzione, spessore, campitura)
        # gestisco qui gli attributi aggiuntivi
        self._larghezza = larghezza
        self._altezza = altezza

    def area(self):
        "calcolo l'area del rettangolo"
        return self._larghezza * self._altezza

    def draw(self, turtle):  
        """
        Disegno il rettangolo son la tartaruga fornita come parametro.
        """
        super().draw(turtle)
        turtle.forward(self._larghezza)
        turtle.left(90)
        turtle.forward(self._altezza)
        turtle.left(90)
        turtle.forward(self._larghezza)
        turtle.left(90)
        turtle.forward(self._altezza)
        turtle.left(90)
        turtle.end_fill()


# %%% Esempio: figure geometriche da disegnare con la turtle slideshow={"slide_type": "slide"}
class PoligonoRegolare(Figura):
    "Costruisco un poligono regolare"
    def __init__(self, x, y, lato, N, colore, 
                 direzione=0, spessore=1, campitura=None):
        super().__init__(x, y, colore, direzione, spessore, campitura)
        self._N = N
        self._lato = lato
        
    def draw(self, turtle):
        super().draw(turtle)
        angolo_esterno = 360/self._N
        for _ in range(self._N):                        
            turtle.forward(self._lato)
            turtle.left(angolo_esterno)
        turtle.end_fill()


class Quadrato(Rettangolo):
    def __init__(self, x, y, lato, colore, 
                 direzione=0, spessore=1, campitura=None):
        super().__init__(x, y, colore, lato, lato, 
                         direzione, spessore, campitura )


# %%% Esempio: figure geometriche da disegnare con la turtle slideshow={"slide_type": "slide"}
t.clear()

r = Rettangolo(50, 100, (255,0,0), 200, 100, 
               direzione=45, spessore=5, 
               campitura=(255,255,0))

p = PoligonoRegolare(-100, -100, 50, 5, (0,0,255), 
                     20, 4, campitura=(255,0,0) )

q = Quadrato(100, 100, 90, (0,255,0), -30, 10)

r.draw(t)

r.move(-200,-100)

r.draw(t)

p.draw(t)

q.draw(t)

print(r.area(), q.area())



# %%
t.clear()
t.hideturtle()

# %% [markdown] editable=true slideshow={"slide_type": "slide"}
# ## [i Frattali](https://it.wikipedia.org/wiki/Frattale) (insieme di Mandelbrot)
# ![mandelbrot.png](mandelbrot.png)

# %% [markdown] editable=true slideshow={"slide_type": ""}
# ### I frattali sono tra noi
# ![felci.png](felci.png)
#
# Sono composti da **parti più piccole** che hanno la **stessa struttura del tutto**

# %% [markdown] editable=true slideshow={"slide_type": ""}
# ### Disegnamo un albero frattale
# ![albero.png](albero.png)

# %% [markdown]
# # cos'è un albero frattale?
# - ha un tronco che regge due rami
# - i rami sono inclinati a sinistra e a destra del tronco
# - ciascun ramo ha la **stressa struttura** di un albero 
#   ma leggermente **più piccolo**
# - un albero di **livello <= zero è una foglia**

# %% Ricorsione [markdown] slideshow={"slide_type": "slide"}
# # Problemi e Soluzioni ricorsive
#
# Una funzione **è ricorsiva se chiama se' stessa** (principio di induzione).
#
# ## Un <u>problema</u> ammette una soluzione ricorsiva se:
# - SAPPIAMO COME <u>rimpicciolire la dimensione</u> del problema da risolvere (**riduzione**)
# - esiste almeno un problema che ha una <u>soluzione elementare</u> (**caso base**)
# - <u>è sempre possibile</u>, applicando ripetutamente la riduzione, <u>arrivare ad uno dei casi base</u> (**convergenza**)
# - SAPPIAMO COME <u>ottenere la soluzione del problema iniziale dalle soluzioni dei sottoproblemi</u> (**composizione**)
#

# %% [markdown] editable=true slideshow={"slide_type": "slide"}
# ## cerchiamo le proprietà del problema ricorsivo
#
# - Un albero di livello <= 0 è una foglia (cerchietto)        (**caso base**)
# - Un albero con N livelli è formato da: (**ricomposizione**)
#   - un tronco lungo X
#   - un **albero con N-1 livelli** inclinato a sinistra, con tronco 80% di X   (**riduzione**)
#   - un **albero con N-2 livelli** inclinato a destra,   con tronco 70% di X   (**riduzione**)
# - sottraendo 1 o 2 ad N si arriva sempre ad un valore <= 0 (**convergenza**)
#   
# Questa è una definizione **ricorsiva**: i due rami sono due alberi! abbiamo **riduzione, caso base, convergenza e ricomposizione**!

# %% [markdown] editable=true slideshow={"slide_type": "subslide"}
# Mi serve uno strumento di disegno:
# - col modulo **turtle** posso tracciare movimenti relativi alla tartaruga
# - col modulo **random** posso generare colori casuali

# %% editable=true slideshow={"slide_type": "fragment"}
# Per disegnare un albero frattale uso una tartaruga e dei numeri casuali 
import turtle 
from random import randint     # generatore di interi casuali
turtle.colormode(255)          # setto i colori in modalità RGB
t = turtle.Turtle()            # creo una tartaruga
t.penup()                      # alzo la penna
t.left(90)                     # giro verso l'alto 
t.back(200)                    # mi posiziono in basso
t.pensize(5)                   # con penna cicciotta
t.speed(0)                     # e velocità alta
#help(turtle)                  # see also      (oppure 'pydoc turtle')

# %% editable=true slideshow={"slide_type": "subslide"}

def albero(t, tronco, angolo, livelli):
    '''disegno un albero con un certo tronco iniziale e # di livelli
    Argomenti:
        t:       la tartaruga a cui dare i comandi
        tronco:  lunghezza del tronco
        angolo:  inclinazione dei rami rispetto al tronco
        livelli: quanti livelli di rami disegnare
    '''
    if livelli <= 0:       # se caso base
        draw_leaf(t)       # disegno la "foglia"
    else:                  # altrimenti caso ricorsivo
        # disegno il tronco (e mi sposto alla sua fine)
        draw_trunk(t, tronco)
        # mi giro a sinistra
        t.left(angolo)
        # disegno il ramo sinistro, più piccolo 80% e con un livello di meno
        albero(t, tronco * 0.8, angolo, livelli-1)
        # mi giro a destra
        t.right(angolo*2)
        # disegno il ramo destro, più piccolo 70% e con due livelli in meno
        albero(t, tronco * 0.7, angolo, livelli-2)
        # torno nella direzione iniziale
        t.left(angolo)
        # torno alla base del tronco
        t.back(tronco)


# %% editable=true slideshow={"slide_type": "subslide"}
# devo definire come disegnare il tronco e la foglia
def draw_trunk(t, lunghezza):
    'Disegno un tratto di colore casuale'
    # cambio colore a caso
    R = randint(100, 200)
    G = randint(100, 200)
    B = randint(100, 200)
    t.color(R,G,B)
    # abbasso la penna
    t.pendown()
    # mi muovo in avanti di lunghezza pixel
    t.forward(lunghezza)
    # alzo la penna
    t.penup()
    # NOTA: ora sono all'estremo opposto del tronco


# %% editable=true slideshow={"slide_type": "subslide"}
def draw_leaf(t):
    'disegno una foglia col colore corrente'
    # abbasso la penna
    t.pendown()
    # disegno un pallino
    t.dot()
    # alzo la penna
    t.penup()


# %% editable=true slideshow={"slide_type": "subslide"}
## Vediamo se funziona :-)
t.clear() # pulisco il foglio
albero(t,100,30,10)

# %% editable=true slideshow={"slide_type": "subslide"}
## Vediamo se funziona :-)
t.clear() # pulisco il foglio
albero(t,100,20,9)

# %% [markdown] slideshow={"slide_type": "slide"}
# ## Esempio classico: il fattoriale
# ## DEF: il fattoriale di un numero N intero positivo è il prodotto dei numeri da 1 a N positivo
#
# - come ridurre il problema? **diminuisco N di 1**
# - quale soluzione semplice conosco? **F(1) = 1**
# - come ottengo F(N) da F(N-1)?  **lo moltiplico per N**
# - il passo di riduzione converge al caso base? **Sì, sottraendo 1 a N alla fine si arriva ad 1**

# %%% Le 4 proprietà di un algoritmo ricorsivo [markdown] slideshow={"slide_type": "slide"}
# ## Esempio classico: fattoriale(N)
#
#    proprietà     |       esempio
# :---------------:|:-------------------:
# **caso base**    |  **`F(1) = 1`**
# **riduzione**    |  **`F(N) -> F(N-1)`**
# **convergenza**  |  **`N, N-1, ..... 1`**
# **composizione** |  **`F(N) = N*F(N-1)`**

# %% [markdown] slideshow={"slide_type": "slide"}
# ## Schema di implementazione ricorsiva
# ```python
#     def funzione(problema):
#         if is_caso_base(problema):
#             return soluzione nota
#         else:
#             sottoproblema  = riduzione(problema)
#             sottosoluzione = funzione(sottoproblema)
#             soluzione      = composizione(sottosoluzione)
#             return soluzione
# ```

# %%% Le 4 proprietà di un algoritmo ricorsivo slideshow={"slide_type": "slide"}
from rtrace import trace

@trace(pause=True)
def fattoriale(N : int) -> int :
    if N==1:
        return 1
    else:
        return N*fattoriale(N-1)

fattoriale.trace(5)


# %%% Le 4 proprietà di un algoritmo ricorsivo [markdown] slideshow={"slide_type": "slide"}
# ## Altro caso classico: i coniglietti di Fibonacci
# - Una coppia di conigli il primo mese è giovane e non prolifica
# - dal secondo mese in poi fa una coppia di coniglietti ogni mese
#
# <img src="Fibonacci_Rabbits.svg" width="70%"/>
#
# Ad ogni mese il numero di coppie si ottiene sommando:
# - i nuovi coniglietti che nascono dalle coppie adulte (quelle di 2 mesi prima)
# - e le coppie correnti (1 mese prima)

# %% [markdown] slideshow={"slide_type": "slide"}
# ### Soluzione iterativa (simulando le coppie)
# - F(0)=0
# - F(1)=1
# - ...
# - F(N)=F(N-1)+F(N-2)

# %% [markdown] slideshow={"slide_type": "slide"}
# ### Soluzione ricorsiva
# Se osserviamo il problema dal punto di vista dell'anno N:
# - **caso base**: 0 coppia se N==0 
# - **caso base**: 1 coppia se N==1   (erano troppo giovani)
# - **riduzione del problema**: Per calcolare F(N) ci servono F(N-1) ed F(N-2)
# - **composizione della soluzione**:   F(N) = F(N-1) + F(N-2)

# %%% Le 4 proprietà di un algoritmo ricorsivo slideshow={"slide_type": "slide"}
@trace(pause=True)
def fibonacci(N : int) -> int :
    if N < 2:
        return 1
    else: 
        return fibonacci(N-1) + fibonacci(N-2)

fibonacci.trace(4)


# %%% Strategia di analisi [markdown] slideshow={"slide_type": "slide"}
# # METODO: le 4 proprietà vi guidano per affrontare un problema ricorsivo sconosciuto:
# - trovate il **caso base**
# - confrontate **problemi** di dimensioni diverse per capire come fare la "riduzione"
# - confrontate **soluzioni** di dimensioni diverse per capire come calcolare la "soluzione"
# - **verificate che** applicando più volte il passo di riduzione **si arrivi sempre ad un caso base** (convergenza)
# - altrimenti aumentate i casi base

# %% [markdown] slideshow={"slide_type": "slide"}
# ## E' sempre possibile simulare un ciclo con una ricorsione
# ## E' sempre possibile simulare una ricorsione con uno o più cicli (e se necessario una pila/stack)
# - Iacopini Bohm
#

# %%% Corrispondenza tra ricorsione e iterazione (teorema di Iacopini-Bohm) slideshow={"slide_type": "slide"}
#  0 1 1 2 3 5 8 13 21

def fibonacci_iter(N : int) -> int :
    coppie = [0, 1]
    for i in range(N):
        coppie.append(coppie[-1] + coppie[-2])
    print(coppie)
    return coppie[-1]
    
print(fibonacci_iter(70))
# MA ATTENZIONE!!! 
# E' sufficiente ricordasi SOLO dei DUE mesi precedenti!

# %%% Corrispondenza tra ricorsione e iterazione (teorema di Iacopini-Bohm) slideshow={"slide_type": "slide"}
# Mi ricordo SOLO dei DUE mesi precedenti
def fibonacci_iter2(N : int) -> int :
    corrente, precedente = 1, 0
    for i in range(N):
        corrente, precedente = corrente+precedente, corrente
    return corrente

print(fibonacci_iter2(70))


# %%% Corrispondenza tra ricorsione e iterazione (teorema di Iacopini-Bohm) slideshow={"slide_type": "slide"}
# simuliamo l'allevamento anno per anno da 1 ad N con la ricorsione
# - convertiamo le variabili di stato del ciclo in argomenti della funzione 
@trace()
def _fibonacci_ric_efficiente(N : int, i : int, 
                              corrente : int, 
                            precedente : int):
    if i == N:
        return corrente
    else:
        corrente, precedente = corrente+precedente, corrente
        return _fibonacci_ric_efficiente(N, i+1, corrente, precedente)

# definiamo una funzione di appoggio che inizializza le variabili di stato 
def fibonacci_ric_efficiente(N : int):
    return _fibonacci_ric_efficiente(N, 0, 1, 0)

# oppure potevamo dare dei valori di default appropriati alle "variabili di stato"

_fibonacci_ric_efficiente.trace(7, 0, 1, 0)


# %%% Corrispondenza tra ricorsione e iterazione (teorema di Iacopini-Bohm) slideshow={"slide_type": "slide"}
# proviamo invece a lavorare in uscita dalla ricorsione
# - ciascuna chiamata ritorna la coppia *corrente, precedente*
# ovvero calcoliamo F(N) -> corrente, precedente
# - nel caso base la coppia è           1, 0
# - da corrente, precedente del mese prima (N-1) posso calcolare quelli di N
@trace()
def fibonacci_efficiente(N : int ) -> tuple[int,int] :
    if N == 0:
        return 1, 0        # all'inizio ci sono 0 ed 1 coppia
    else:
        # ottengo i due valori del mese precedente (F(N-1) e F(N-2))
        corrente, precedente = fibonacci_efficiente(N-1)
        # calcolo i due valori per questo mese     (F(N)   e F(N-1))
        return corrente+precedente, corrente

print(fibonacci_efficiente(5)[0])

fibonacci_efficiente.trace(5)


# %%% esempio: GCD con l'algoritmo di Euclide [markdown] slideshow={"slide_type": "slide"}
# ## Altro esempio: Massimo Comun Divisore di x, y interi positivi
# Ovvero dobbiamo trovare quel'intero **$M$** tale che:
# - **$x = M*k$** 
# - **$y = M*j$**
# - con **$k,j>=1$** (e senza fattori comuni)


# %%% esempio: GCD con l'algoritmo di Euclide [markdown] slideshow={"slide_type": "slide"}
# ### Quali sono le proprieta di **$x$** ed **$y$**?
# - se **x==y** allora **k==j==1** e **M=x**     (ecco un buon **caso base**!)
# - altrimenti proviamo a <u>sottrarre il minore dal maggiore</u>
#   - **z = x-y = M*(k-j)**   quindi **z** e **y** hanno lo stesso **MCD**, <br>
#     e inoltre <u>z è più piccolo di x</u>  (ecco la nostra **riduzione**!)
#     - ad ogni passo si riduce la somma k+j di almeno j (il più piccolo) 
#     - sottraendo un numero più piccolo non si può andare nei negativi nè sullo 0
#   - a forza di sottrarre arriveremo per forza a j=k=1 ovvero al caso base      (ed ecco la **convergenza**)
#   - una volta trovato **M** abbiamo la soluzione di ciascun caso __più grande__ (**ricomposizione**)
#
# Ottimizzazione: invece di sottrarre y da x calcoliamone il resto -> algoritmo di **Euclide**


# %%% esempio: GCD con l'algoritmo di Euclide slideshow={"slide_type": "slide"}
# Sfruttiamo la definizione ricorsiva del problema
# per dare una implementazione ricorsiva
@trace()
def GCD(x : int, y : int) -> int :
    # FIXME: controllare che siano  interi E positivi
    if x == y:
        return x
    else:
        if x>y:
            return GCD(x-y, y)
        else:
            return GCD(y-x, x)

GCD.trace(108, 64)


# %%% esempio: GCD con l'algoritmo di Euclide slideshow={"slide_type": "slide"}
## Non è difficile farne una versione iterativa

def GCD_iter(x : int, y : int) -> int :
    while x != y:
        if x > y:
            x -= y
        else:
            y -= x
    return x

print(GCD_iter(75,45))


# %%% esempio: palindromaP [markdown] slideshow={"slide_type": "slide"}
# ## Esempio: Check se una stringa/lista è palindroma <br> (si legge uguale in senso inverso)
#
# ### soluzioni iterative
# - rovescio e confronto
# - scandisco gli indici degli elementi agli estremi e li confronto


# %% run_control={"marked": false}
from typing import Sequence
## Rovescio e confronto
def palindromaP_iter1(sequenza : Sequence):
    rovesciata = sequenza[::-1]
    return rovesciata == sequenza

# leggermente inefficiente, costruisco una nuova sequenza e confronto 2N elementi
# (potrei confrontarne solo N)
palindromaP_iter1('amoRoma')


# %% slideshow={"slide_type": "slide"}
## Versione iterativa

def palindromaP_iter2(sequenza : Sequence ) -> bool :
    for i in range(len(sequenza)//2):
        print('comparing', sequenza[i], sequenza[-i-1], sequenza[i] == sequenza[-i-1])
        if sequenza[i] != sequenza[-i-1]:
            return False
    return True

palindromaP_iter2('amoRoma')
#palindromaP_iter([1, 2, 3, 4, 5, 4, 3, 2, 1])

# %%
def palindroma_iter2(sequenza):
    inizio = 0
    fine   = len(sequenza)-1
    while inizio < fine:
        print('comparing', sequenza[inizio], sequenza[fine], sequenza[inizio] == sequenza[fine])
        if sequenza[inizio] != sequenza[fine]:
            return False
        inizio += 1
        fine   -= 1
    return True

palindroma_iter2([1, 2, 3, 4,  5, 4, 3, 2, 1])

# %%% esempio: palindromaP [markdown] slideshow={"slide_type": "slide"}
# ### soluzione ricorsiva
# - **casi base**: ogni sequenza di lunghezza 0 o 1 è palindroma
# - se è lunga 2 o più elementi il primo e l'ultimo devono essere uguali
# - se non lo sono NON è palindroma (altro **caso base**)
# - se lo sono deve essere palindromo anche il resto, tolto primo ed ultimo carattere
#   - (togliere i 2 caratteri = **riduzione**)
#   - a forza di togliere 2 caratteri si arrivarà sempre a 1 o 0 (**convergenza**)
#   - la stringa è palindroma se sono uguali primo e ultimo AND la sottostringa è palindroma <br>
#    (**costruzione della soluzione dalla sottosoluzione** + calcolo locale)


# %% slideshow={"slide_type": "slide"}
@trace()
def palindromaP(sequenza : Sequence ) -> bool :
    "predicato che verifica se una sequenza è palindroma"
    if len(sequenza) < 2:
        return True
    if sequenza[0] != sequenza[-1]:
        return False
    else:
        return palindromaP(sequenza[1:-1])

palindromaP.trace('amoRoma')

# un po' inefficiente perchè crea tante sottosequenze


# %% slideshow={"slide_type": "slide"}
# versione che usa gli indici inizio e fine e non crea sottostringhe
@trace()
def _palindromaP2(sequenza : Sequence, inizio : int, fine : int ) -> bool :
    if inizio >= fine:
        return True
    if sequenza[inizio] != sequenza[fine]:
        return False
    return _palindromaP2(sequenza, inizio+1, fine-1)
    
def palindromaP2(sequenza):
    return palindromaP2(sequenza, 0, len(sequenza)-1)


_palindromaP2.trace('amoRoma', 0, 6)

# %% [markdown] slideshow={"slide_type": "slide"}
# ## Esploriamo un albero di directory: <br>cerchiamo tutti i file .txt e la loro dimensione
#
# - una directory contiene files (caso base) e sottodirectory (caso ricorsivo)
# - ogni volta che esaminiamo una sottodirectory abbiamo un problema simile a quello iniziale, e più piccolo
# - a forza di scendere arriveremo in una sottodirectory che contiene solo file (convergenza)
# - i file trovati nelle sottodirectory vanno raccolti assieme a quelli della dir iniziale (composizione)
#
# Per esaminare directory e files si usa la libreria **`os`**

# %% slideshow={"slide_type": "subslide"}
import os

@trace()
def cerca_file_sizes(directory : str) -> dict[str, int] :
    "cerco tutti i file '.txt' e ne ritorno le dimensioni"
    risultato = {}
    for nome in os.listdir(directory):
        # ignoro file e dir che iniziano per '.' oppure '_'
        if nome[0] in '_.': continue
        fullname = directory + '/' + nome
        # se sono nel caso ricorsivo
        if os.path.isdir(fullname):
            trovati = cerca_file_sizes(fullname)
            # aggiorno il dizionario con ciò che ho trovato nella sottodirectory
            risultato.update(trovati) 
        # altrimenti se è un file che finisce con 'txt'
        elif nome.endswith('.txt'):
            size = os.path.getsize(fullname)
            risultato[fullname] = size
    return risultato

cerca_file_sizes.trace('../lezione11')


# %%
## soluzione ricorsiva che raccoglie i file
## in un dizionario fornito come argomento
## e aggiornato mano a mano che si esplora

def cerca_file_sizes2(directory : str, dizionario : dict[str, int]) -> None:
    "cerco tutti i file '.txt' e ne ritorno le dimensioni"
    for nome in os.listdir(directory):
        # ignoro file e dir che iniziano per '.' oppure '_'
        if nome[0] in '_.': continue
        fullname = directory + '/' + nome
        # se sono nel caso ricorsivo
        if os.path.isdir(fullname):
            cerca_file_sizes2(fullname, dizionario)
        # altrimenti se è un file che finisce con 'txt'
        elif nome.endswith('.txt'):
            size = os.path.getsize(fullname)
            dizionario[fullname] = size

D : dict[str,int] = {}
cerca_file_sizes2('..', D)
D