Informazioni su questo esperimento
Un albero è un tronco con sopra due alberi più piccoli. Questa sola frase è un programma completo: una funzione che disegna un ramo e poi chiama sé stessa due volte. La ricorsione trasforma regole brevi in immagini ricche. Guarda un albero, un triangolo di Sierpiński e un fiocco di neve di Koch prendere forma chiamata dopo chiamata; segui lo stack delle chiamate mentre cresce e si riduce, e conta quanto rapidamente esplode il numero di chiamate all’aumentare della profondità.
Obiettivi di apprendimento
- Individuare il caso base e il caso ricorsivo di una funzione ricorsiva
- Seguire l’ordine in cui le chiamate ricorsive vengono eseguite e restituiscono il controllo
- Spiega cosa contiene lo stack delle chiamate e perché la sua profondità è importante
- Calcola il numero di chiamate per una determinata profondità, ad esempio 2^(n+1) − 1 per un albero binario
- Descrivi l’autosimilarità e calcola una semplice dimensione frattale
Come si usa
- 1Scegli l’albero di profondità 3 e osserva lentamente le chiamate. Quale ramo viene disegnato per primo: quello sinistro o quello destro? Perché?
- 2Metti in pausa quando lo stack raggiunge la profondità massima. Che cosa rappresenta ogni frame dello stack? Quanti frame ci sono rispetto alla profondità?
- 3Completa una tabella con profondità e chiamate per l’albero. Trova la regola e verificala alla profondità 10.
- 4Modifica l’angolo dei rami e il rapporto tra le lunghezze. Quali impostazioni fanno sovrapporre i rami?
- 5Passa al triangolo di Sierpinski. Dov’è il caso base nel codice? Quanti triangoli vengono disegnati alla profondità 5?
- 6Costruisci il fiocco di neve di Koch alla profondità 5. Usa i valori mostrati per spiegare come il perimetro possa continuare a crescere mentre l’area rimane limitata.
Il modello
Ipotesi
- Le chiamate vengono eseguite una alla volta, nell’ordine del programma e in profondità, proprio come avviene in un normale linguaggio di programmazione.
- Lo pseudocodice passa posizioni e direzioni come parametri, quindi non è necessario ripristinare lo stato della tartaruga quando una chiamata termina.
- La dimensione frattale dell’albero, log 2 / log(1/r), descrive solo le punte quando i rami non si sovrappongono.
- Le profondità massime sono limitate affinché la riproduzione passo dopo passo rimanga veloce: 12 per l’albero, 7 per il triangolo e 6 per il fiocco di neve.
Provalo in classe
- Q1Cosa succederebbe se la funzione dell’albero non avesse un caso base?
- Q2Quante chiamate effettua la funzione di Sierpinski alla profondità 4? Spiega la risposta con una somma.
- Q3Perché lo stack delle chiamate non diventa mai più profondo della profondità della ricorsione più uno, anche se vengono effettuate migliaia di chiamate?
- Q4Scrivi una funzione ricorsiva che calcoli n! e individua il suo caso base.
- Q5La costa della Gran Bretagna sembra tanto più lunga quanto più corto è il righello con cui la si misura. Come spiega questo fenomeno il fiocco di neve di Koch?
Domande frequenti
La ricorsione è più lenta di un ciclo?
Ogni chiamata richiede un po’ di tempo e memoria per il proprio frame dello stack, quindi un ciclo è spesso leggermente più veloce. Tuttavia, per strutture ramificate come alberi, cartelle annidate o l’analisi sintattica, la ricorsione è molto più semplice da scrivere, e qualsiasi ricorsione può essere riscritta usando uno stack esplicito gestito autonomamente.
Che cos’è un stack overflow?
Ogni chiamata non ancora terminata mantiene un frame nello stack delle chiamate. Se la ricorsione diventa troppo profonda, per esempio perché non si raggiunge mai il caso base, lo stack esaurisce la memoria e il programma va in crash con un errore di stack overflow.
Dove si trovano i frattali in natura?
Le felci, il broccolo romanesco, le reti fluviali, i fulmini, i vasi sanguigni e le ramificazioni delle vie respiratorie dei polmoni sono approssimativamente autosimili su più scale; per questo si usano regole ricorsive per generarli nella computer grafica.