<jupyter_start><jupyter_text>La ricorsioneIn 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 1Scrivi 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:<jupyter_code>def fattoriale(n):
    if n == 0:
        return 1
    else:
        return n*fattoriale(n-1)

print(fattoriale(6))<jupyter_output><empty_output><jupyter_text>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 2I **numeri di Fibonacci** sono una successione numerica introdotta nel XII secolo da Leonardo Fibonacci. 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 ricorsivePossiamo 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:<jupyter_code>from turtle import *

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

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

stella(100)<jupyter_output><empty_output><jupyter_text>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.<jupyter_code>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)<jupyter_output><empty_output><jupyter_text>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 FrattaliUna 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<jupyter_code>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)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09534992954438704, 'fraction_numerical': 0.02677313292625646, 'mean_word_length': 4.747638326585695, 'pattern_counts': {'":': 0, '<': 18, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '123015', 'license': 'CC0-1.0', 'n_tokens_mistral': 1563, 'n_tokens_neox': 1488, 'n_words': 503, 'path': 'avanzato_ricorsione_frattali.ipynb', 'repo_name': 'comaschipaolo/corso_coding_2022', 'size': '4258'}