Dalla definizione ricorsiva alle strutture complesse: numeri, grafici e immagini tra successioni, alberi e autosimiglianza.
Nell’ampia e luminosa galleria della storia, che espone il lascito culturale di Leonardo Fibonacci, fa bella mostra di sé il celebre problema dei conigli:
«Quante coppie di conigli verranno prodotte in un anno, a partire da un’unica coppia, se ogni mese ciascuna coppia dà alla luce una nuova coppia che diventa produttiva a partire dal secondo mese?».
Il numero di coppie è, di mese in mese e oltre, nella successione che porta il suo nome: la successione di Fibonacci:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...
Una successione generabile in modo ricorsivo a partire da due soli valori iniziali:
$$
\begin{cases}
f(n)=f(n-1)+f(n-2), & n>2\\[4pt]
f(1)=1,\quad f(2)=1
\end{cases}
$$
La ricorsività entra così in scena con il suo tratto distintivo: una legge che si applica a se stessa, generando una struttura che nasce e cresce a partire dai propri risultati precedenti. Ogni termine, infatti, è la somma dei due precedenti.
La successione di Lucas
La stessa legge di ricorsione può dar luogo a successioni numeriche diverse semplicemente variando i valori iniziali. È il caso della successione di Lucas, da Édouard Lucas (1842–1891), autore della classica opera Récréations Mathématiques, definita da:
$$
\begin{cases}
l(n)=l(n-1)+l(n-2), & n>2\\[4pt]
l(1)=1,\quad l(2)=3
\end{cases}
$$
Da cui si ottiene:
1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ...
La ricorsione è la stessa di Fibonacci, ma la diversa scelta delle condizioni iniziali modifica l’intera successione.
È un primo insegnamento: la ricorsività è una forma, un recipiente formale capace di generare mondi numerici diversi a seconda di ciò che vi si immette all’inizio. È interessante osservare che le due successioni, quella di Fibonacci e quella di Lucas, sono collegate dalla seguente relazione: f(2n) = f(n)· l(n).
Ad esempio: f(10) = 55 = 5 · 11 = f(5) · l(5). Una formula particolarmente utile quando si desidera calcolare rapidamente termini di indice pari nella successione di Fibonacci.
Ricorsioni immaginate: l’ingresso di Hofstadter
A questo punto il nostro percorso incontra l’autore che più di ogni altro si è lasciato affascinare dalla ricorsività: Douglas R. Hofstadter.
Nelle sue ricorsioni “immaginate”, la ripetizione di una regola su se stessa diventa non soltanto un procedimento matematico, ma una struttura logica, un modo di pensare, un meccanismo che genera livelli, ritorni e annidamenti. Con una ulteriore parentesi, la ricorsione di Fibonacci può essere alterata in modo da generare una nuova successione:
$$
f(n)=f\!\big(n\cdot f(n-1)\big)+f\!\big(n-f(n-2)\big),\qquad n>2
$$
$$
f(1)=f(2)=1.
$$
Questa legge, pur ricordando nella forma la ricorsione classica di Fibonacci, produce una successione molto diversa:
1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, ...
L’andamento appare irregolare, quasi caotico: un caos però prodotto in modo ordinato, perché interamente determinato da una regola precisa. È un primo esempio di come una legge ricorsiva, quando si “ripiega” su se stessa, possa generare comportamenti complessi.
Una ricorsione sorprendente: la funzione g(n)
Consideriamo ora la ricorsione:
$$
g(n)=n-g(g(n-1)), \qquad n>0
$$
con valore iniziale:
$$
g(0)=0.
$$
Per coglierne il funzionamento è utile osservare i primi termini:
- \(g(0)=0\)
- \(g(1)=1-g(g(0)) = 1-g(0) = 1\)
- \(g(2)=2-g(g(1)) = 2-g(1) = 1\)
- \(g(3)=3-g(g(2)) = 3-g(1) = 2\)
- \(g(4)=4-g(g(3)) = 4-g(2) = 3\)
- \(g(5)=5-g(g(4)) = 5-g(3) = 3\)
- \(g(6)=6-g(g(5)) = 6-g(3) = 4\)
La successione comincia quindi così:
0, 1, 1, 2, 3, 3, 4, 4, 4, 5, 6, ...
Per rappresentarne la struttura, si utilizza spesso un albero ricorsivo, in cui ogni nodo riporta un valore della successione:
Questo albero presenta alcune caratteristiche sorprendenti:
- lungo il ramo di destra compare nuovamente la successione di Fibonacci;
- la distribuzione dei valori mostra una chiara autosimiglianza:
porzioni dell’albero appaiono come versioni ridotte dell’intera struttura; - l’intero diagramma nasce da una ricorsione che si applica ai propri risultati, producendo livelli annidati sempre più ricchi.
In questo senso, la funzione \(g(n)\) è un esempio emblematico di come una regola semplice, applicata ricorsivamente, possa dare luogo a un grafico che rende visibile la dinamica interna della successione.
Una ricorsione caotica
Tra le ricorsioni discusse da Hofstadter, una delle più sorprendenti è definita da:
$$
Q(n)=Q\big(n-Q(n-1)\big)+Q\big(n-Q(n-2)\big),\qquad Q(1)=Q(2)=1.
$$
A differenza della ricorsione di Fibonacci, dove gli indici sono sempre gli stessi (\(n-1\) e \(n-2\)), qui gli indici dipendono dai valori già ottenuti.
Ogni nuovo termine richiede quindi di “tornare indietro” di un numero di passi determinato dalla successione stessa.
Si può vedere il meccanismo calcolando i primi valori:
- \(Q(1)=1\)
- \(Q(2)=1\)
- \(Q(3)=Q(3-Q(2))+Q(3-Q(1)) = Q(2)+Q(2) = 1+1 = 2\)
- \(Q(4)=Q(4-Q(3))+Q(4-Q(2)) = Q(2)+Q(3) = 1+2 = 3\)
- \(Q(5)=Q(5-Q(4))+Q(5-Q(3)) = Q(2)+Q(3) = 1+2 = 3\)
- \(Q(6)=Q(6-Q(5))+Q(6-Q(4)) = Q(3)+Q(3) = 2+2 = 4\)
- \(Q(7)=Q(7-Q(6))+Q(7-Q(5)) = Q(3)+Q(4) = 2+3 = 5\)
La successione comincia dunque così:
1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, ...
L’andamento è chiaramente irregolare: compaiono ripetizioni, salti in avanti, talvolta anche “rallentamenti”.
Eppure la successione non ha nulla di casuale: è completamente deterministica, interamente governata dalla regola data.
È uno dei casi che Hofstadter presenta come esempio di caos prodotto in modo del tutto ordinato.
Il tratto distintivo di questa definizione è la sua natura annidata: gli argomenti di ogni termine dipendono da termini precedenti che dipendono a loro volta da altri termini. Si crea così una catena di rimandi, molto simile alle immagini cui Hofstadter ricorre spesso: storie dentro storie, scatole dentro scatole, parentesi dentro parentesi.
Ricorsioni, autosimiglianza e immagini: il caso Escher
L’idea che una struttura possa contenere versioni di se stessa in forma trasformata, ridotta o ripetuta trova una rappresentazione visiva straordinaria nelle opere di M. C. Escher.
Escher si appropriò dell’idea che le parti di un oggetto potessero essere copie dell’oggetto stesso e la mise in scena nella xilografia Pesci e squame. Naturalmente questi pesci e queste squame sono uguali solo se visti a un livello sufficientemente astratto. Tutti sanno che le squame di un pesce non sono realmente piccole copie di un pesce; e neanche le cellule del pesce sono piccole copie del pesce.
Comunque, il DNA di un pesce, posto all’interno di ogni singola cellula, è una “copia” molto involuta dell’intero pesce. In questo senso il quadro di Escher contiene più che un granello di verità.
Proprio come all’interno di ogni minuscolo pezzetto di pesce è contenuto il suo DNA, così ogni piccolo frammento di un’opera porta la “firma” del suo autore. Non sappiamo come chiamarla, se non stile: una parola vaga e sfuggente, che tuttavia riesce a rivelare un’identità riconoscibile nel diverso.
Le opere di Escher, le ricorsioni di Hofstadter e le successioni di Fibonacci e Lucas mostrano tutte, ognuna a suo modo, come la parte possa contenere il tutto: un principio di autosomiglianza che attraversa numeri, forme e idee.
Ricorsività: dai numeri alle forme
Dai problemi iniziali di Fibonacci alle variazioni di Lucas, fino alle ricorsioni immaginate da Hofstadter, abbiamo visto come una definizione che si applica ai propri risultati possa generare comportamenti semplici o imprevedibili, regolari o irregolari. In ogni caso, ciò che nasce è una struttura, non un semplice elenco di numeri.
Nei grafici ricorsivi questa struttura diventa visibile. L’albero generato dalla funzione \(g(n)\) rende immediatamente percepibili i ritorni, le diramazioni, le simmetrie interne della ricorsione: è la successione che “prende forma”. Le tassellature di M. C. Escher mostrano qualcosa di analogo: motivi che si trasformano, si ripetono, si incastrano, proprio come le definizioni ricorsive
riusano continuamente i propri risultati.
La ricorsività permette così di passare dai problemi ai grafici, dai numeri alle immagini. La stessa logica che genera una successione genera una figura; e ciò che nei numeri appare come dipendenza dai casi precedenti, nelle immagini appare come autosimiglianza. È questa la ragione unificante dei nostri esempi: una regola semplice che, applicata a se stessa, costruisce strutture complesse. La ricorsione non è soltanto un procedimento tecnico: è un modo di produrre forme, numeriche o visive, che portano in sé la traccia della regola da cui nascono.
COMMENTS