# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3 (ipykernel)
#     language: python
#     name: python3
# ---

# # La ricorsione
#
# In questo breve notebook Jupyter, pensato per chi si vuol mettere alla prova, vediamo brevemente cosa sono le funzioni ricorsive e poi le usiamo per disegnare un frattale autosimile, la curva di Koch, con il modulo `turtle`.
#
# In matematica, il fattoriale di un numero intero $n$, $n!$, è il prodotto di tutti i numeri da $1$ a $n$:
#
# $$n! = 1⋅2⋅3⋅...⋅(n-1)⋅n$$
#
# Inoltre, per definizione $0! = 1$. I primi valori del fattoriale sono:
#
# $1! = 1$, $2! = 2$, $3!= 6$, $4 != 24$, $5! = 120$, $6! = 720$, ...

# ### Esercizio 1
# Scrivi una funzione che calcoli il fattoriale di un numero `N` usando un ciclo `for`.



# Il fattoriale può anche essere definito ricorsivamente:
#
# $$0! =1$$
# $$n! = n⋅(n-1)!$$
#
# Questa definizione è molto semplice da implementare con una funzione ricorsiva, cioè una funzione che chiama se stessa:

# +
def fattoriale(n):
    if n == 0:
        return 1
    else:
        return n*fattoriale(n-1)

print(fattoriale(6))
# -

# Ogni funzione ricorsiva ha due componenti fondamentali:
#
# * una chiamata ricorsiva alla funzione stessa ` return n * fattoriale(n-1)`
#
# * una condizione che termini la ricorsione
#
# `    if n == 0:
#         return 1`
#
# Senza questa condizione, le chiamate ricorsive non hanno termine e il codice produce un errore.

# ### Esercizio 2
# I **numeri di Fibonacci** sono una successione numerica introdotta nel XII secolo da <NAME>. La successione è definita ricorsivamente:
#
# $$Fib(n) = Fib(n-1) + Fib(n-2)$$
# $$Fib(1) = 1$$
# $$Fib(2) = 1$$
#
# I primi numeri della successione sono
#
# $$1~~1~~   2~~   3~~   5~~   8~~   13~~~   21~~~   34~~~   55~~~   89~~~   144~~~   233~~~   377~~~   610~~~   987$$
#
# La successione di Fibonacci ha numerose proprietà matematiche, ma in questo contesto ci concentriamo sulla costruzione di una funzione ricorsiva che calcoli questi numeri.
#
# Prova a scrivere una funzione ricorsiva che calcoli i numeri di Fibonacci.



# # Immagini ricorsive
# Possiamo usare le funzioni ricorsive per generare delle immagini che sono autosimili, cioè che sono contenute in delle proprie parti.
#
# Per esempio, la seguente funzione genera una stella a cinque punte:

# +
from turtle import *

shape("turtle")
home()
clear()
speed(10)

def stella(lato):
    for i in range(5):
        forward(lato)
        left(216)

stella(100)
# -

# Possiamo modificare la funzione in modo da disegnare una stella più piccola in ogni vertice della stella.
#
# Chiaramente, dobbiamo introdurre una condizione per fermare la ricorsione quando le stelle sono troppo piccole.

# +
from turtle import *

shape("turtle")
home()
clear()
speed(10)

def stella(lato):
    if lato < 10:
        return
    for i in range(5):
        forward(lato)
        stella(lato/3)
        left(216)

stella(300)
# -

# Il risultato è il seguente:
# ![image.png](attachment:image.png)
#
# Come è evidente, se non terminassimo la ricorsione ad una certa profondità, questa immagine sarebbe contenuta nelle sue parti.

# # I Frattali
#
# Una delle applicazioni più divertenti delle funzioni ricorsive è la creazione di immagini frattali autosimili. I frattali autosimili sono figure geometriche che contengono al proprio interno copie identiche di se stesse. 
#
# Non tutti i frattali sono autosimili, tuttavia tutte le figure autosimili che genereremo nel seguito sono frattali (chiariremo meglio il concetto più avanti).
#
# ## La curva di Koch
#
# ![image.png](attachment:image.png)
#
# La curva di Koch è un esempio di frattale autosimile: si parte da un segmento diviso in tre parti e si sostituisci il triangolo centrale con un due lati di un triangolo equilatero, ripetendo ricorsivamente l’operazione sui quattro segmenti ottenuti. Le prossime figure illustrano visivamente i primi passaggi della ricorsione.
# ![image-2.png](attachment:image-2.png)
# ![image-3.png](attachment:image-3.png)
# ![image-4.png](attachment:image-4.png)
# ![image-5.png](attachment:image-5.png)

# Il seguente codice genera lo schema base della curva di Koch

# +
from turtle import *

shape("turtle")
home()
clear()
speed(10)

def koch_base(L):
    forward(L)
    left(60)
    forward(L)
    right(120)
    forward(L)
    left(60)
    forward(L)
    
koch_base(100)
# -

# L'idea alla base del disegno della curva di Koch è sostituire i segmenti (disegnati con la funzione `forward`) con altre curve di Koch, chiamando ricorsivamente la funzione.
#
# ### Esercizio 3
#
# Scrivi una funzione che disegni la curva di Koch.



# ## Cosa contraddistingue i frattali
#
# I frattali autosimili sono figure interessanti per le loro proprietà estetiche. Tuttavia, sono anche molto interessanti per le loro proprietà matematiche e geometriche. Consideriamo le figure geometriche nel piano, generalmente possiamo classificarle facilmente in linee o superfici: ad esempio un ellisse è chiaramente una linea, mentre un cerchio è una superficie. Questa classificazione perde di significato se consideriamo i frattali: una figura come la curva di Koch presenta caratteristiche intermedie tra quelle di una linea e quello di una superficie.
#
# Per rendercene conto, immaginiamo di stampare una figura e consideriamo la quantità di inchiostro consumata in funzione della dimensione $l$ della figura: $C(l)$. È intuitivo che se stampiamo una linea, $C$ è direttamente proporzionale a $l$:
#
# $$C(l) \propto l$$
#
# Mentre se stampiamo una superficie, $C$ cresce come il quadrato di $l$:
#
# $$C(l) \propto l^2$$
#
# Ma consideriamo ora la curva di Koch. Una curva di Koch di lato $l$ è composto da quattro copie di se stessa di lato $l/3$, quindi
#
# $$C(l) = 4 \cdot C(l/3)$$
#
# Se sostituiamo in questa equazione $C(l) = K\cdot l^\alpha$ otteniamo
#
# $$K\cdot l^\alpha   = 4K\cdot \frac{l^\alpha}{3^\alpha}$$ 
#
# questa equazione ha soluzione solo se 
# $$ \frac{4}{3^\alpha} =1 \Longrightarrow \alpha=  \log_3(4) \approx 1,26$$
# Quindi per una curva di Koch
#
# $$C(l)\propto l^{1,26} $$
#
# Possiamo introdurre il concetto di dimensione di una figura: le linee hanno dimensione 1, le superfici dimensione 2 e la curva di Koch ha dimensione 1,26. La dimensione di un frattale è sempre non intera e in matematica è detta dimensione di Hausdorff. I frattali non sono necessariamente autosimili, tuttavia tutti i frattali hanno la caratteristica di avere una dimensione non intera.
#

# ### Esercizio 4
# Con un procedimento ricorsivo simile alla curva di Koch, puoi generare un altro frattale autosimile, il triangolo di Sierpinski:
#
# ![image.png](attachment:image.png)
#
# Prova a scrivere un codice ricorsivo che generi il triangolo di Sierpinski.



StarcoderdataJupyterScriptsDedupFiltered