La ricorsione in natura: il broccolo romano e un suo particolare
La ricorsione è una nozione fondamentale in matematica e in informatica. Una equazione ricorsiva definisce qualcosa in termini di sé stesso. Ad esempio, questa è l'equazione che definisce un autovettore di una matrice e che sta alla base dell'algoritmo del PageRank del motore di ricerca Google: $$\lambda x = A x$$ L'equazione definisce l'importanza $x$ di una pagina Web in termini dell'importanza $A x$ delle pagine che hanno dei collegamenti ipertestuali ad essa.
Il principio d'induzione è un'altra forma di ricorsione in matematica. Esso asserisce che se $\mathcal{P}$ è una proprietà che vale per il numero $0$, e se $\mathcal{P}(n)$ implica $\mathcal {P}(n+1)$ per ogni $n$, allora $\mathcal{P}(n)$ vale per ogni $n$. Dunque per dimostrare che $\mathcal{P}$ vale devo assumere che $\mathcal{P}$ stessa valga su numeri più piccoli.
Una funzione ricorsiva in un programma è una funzione che nel corpo richiama sè stessa. Una funzione ricorsiva si costruisce induttivamente: si programma dapprima la funzione sul caso base (lo 0 dell'induzione). Quindi, assumendo che la funzione faccia il suo lavoro su un input pari a $n$, si programma la funzione per l'input $n+1$. La ricorsione in informatica è una sorta di iterazione (di fatto ogni funzione ricorsiva si può scrivere usando i cicli). Come per i cicli, è bene che la ricorsione termini dopo un numero finito di chiamate ricorsive (si dice che ricorsione deve essere ben fondata).
La ricorsione e i sistemi complessi hanno molte cose in comune. Anche la ricorsione è un fenomeno che si ritrova spesso in natura: sotto forma di frattali, la ritroviamo negli alberi, nel profilo delle coste, nel profilo delle montagne, nelle nubi, nei cristalli di ghiaccio, in alcune foglie e fiori.
La ricorsione in natura: il broccolo romano e un suo particolare
Un frattale è un oggetto autosomigliante, cioè che si ripete nella sua forma allo stesso modo su scale diverse, ovvero non cambia aspetto anche se visto con una lente d'ingrandimento. E' un oggetto a prima vista complesso, ma generato da una sorgente ordinata molto semplice. I frattali appartengono al mondo della natura ma vengono spesso studiati dai matematici e riprodotti dagli artisti (non solo generativi).
"Si ritiene che in qualche modo i frattali abbiano delle corrispondenze con la struttura della mente umana, è per questo che la gente li trova così familiari. Questa familiarità è ancora un mistero e più si approfondisce l'argomento più il mistero aumenta." (Benoit Mandelbrot)
La ricorsione, inoltre, sfruttando la potenza riflessiva, produce risultati complessi a partire da semplice regole codificate. Inoltre, micro variazioni nelle regole della ricorsione possono produrre effetti di vasta portata.
Vediamo alcuni esempi di ricorsione.