Altre ricorsioni sorprendenti

Annidamenti ricorsivi, funzioni sposate di Hofstadter, la ricorsione auto-descrittiva di Golomb e altre costruzioni sorprendenti

Nell’articolo Problemi e grafici ricorsivi abbiamo visto come la ricorsione possa generare curiose successioni numeriche, spesso rappresentabili mediante grafici altrettanto singolari: la successione di Fibonacci, quella di Lucas, la funzione g(n) con il suo albero autosimile e la successione caotica Q(n).
Proseguiamo ora esplorando ricorsioni più sofisticate, riconducibili in parte allo stesso spirito esplorativo di Douglas R. Hofstadter.

Per farlo conviene richiamare la funzione g(n), definita da:

$$
g(0)=0,qquad
g(n)=n-gbig(g(n-1)big)quad text{per } n>0.
$$

In questa ricorsione il valore di un termine dipende dalla funzione applicata a un valore precedente, che a sua volta richiede un ulteriore passo ricorsivo. Ne nasce una successione irregolare ma strutturata, rappresentabile tramite un albero autosimile, nel quale ogni livello rimanda al precedente: un esempio tipico di ricorsione annidata.

L’esempio si presta bene anche a un uso didattico in quanto mostra come si possa essere liberi nel costruire funzioni ricorsive e nell’esplorare le successioni numeriche a cui danno luogo, riconoscendone regolarità, anomalie e punti di svolta. Lo stesso Hofstadter, affascinato dalla ricorsività, ne propose molte varianti. A partire da g(n), egli passa a un annidamento ulteriore con la funzione

$$
h(0)=0,qquad
h(n)=n-hbig(h(n-1)big)quad text{per } n>0.
$$

Mettendo a confronto i grafici (tratti da Hofstadter) delle due funzioni, g e h, si osserva come la seconda presenti nodi aggiuntivi e una struttura più intricata: un ottimo esercizio per cogliere visivamente differenze e analogie nella regolarità delle costruzioni ricorsive.

Su questa stessa linea si collocano le due successioni che Hofstadter definisce, con simpatica metafora, le funzioni sposate: F(n) e M(n).

Come g(n) e h(n), esse non dipendono solo dai loro valori precedenti, ma si intrecciano tra loro in un sistema di richiami incrociati. La novità è che qui la ricorsione non è soltanto annidata, ma anche mutualmente definita: ciascuna successione esiste soltanto in virtù dell’altra, proprio come due “coniugi” che condividono un medesimo destino funzionale.

Le due successioni sono definite congiuntamente:

$$
F(1)=1,qquad M(1)=0,
$$

$$
F(n)=n – Mbig(F(n-1)big)quad text{per } n>1,
$$

$$
M(n)=n – Fbig(M(n-1)big)quad text{per } n>1.
$$

Il valore di F(n) si ottiene sottraendo un valore della successione M, mentre M(n) dipende a sua volta da un valore di F: la ricorsione procede quindi attraverso un rimbalzo continuo tra le due funzioni, che si sostengono a vicenda.

Rispetto alla funzione g(n), sono più complesse nella forma ma sorprendentemente regolari nel comportamento. Nonostante la definizione annidata e il rimpallo costante tra F e M, le due successioni crescono in modo lineare, come se sotto il meccanismo labirintico operasse una struttura ordinata e stabile.

La successione F(n) comincia così:

1, 2, 2, 3, 3, 4, 4, 5, 5, 6, …

La successione M(n) procede in parallelo:

0, 1, 2, 2, 3, 3, 4, 4, 5, 5, …

Regolari nell’andamento, ma generate da una definizione che intreccia continuamente i due insiemi di valori, le funzioni sposate costituiscono uno degli esempi più eleganti di come la ricorsione possa produrre ordine attraverso processi profondamente annidati.

La ricorsione di Golomb: una successione che si auto-descrive

Dopo le funzioni annidate e le funzioni sposate di Hofstadter, un altro esempio sorprendente di ricorsione non lineare è la successione introdotta dal matematico americano Solomon W. Golomb (1932–2016), noto per i suoi studi sulla teoria dei codici, i polimini e numerose strutture combinatorie a crescita discreta. Golomb mostrò che una ricorsione può non solo generare numeri, ma anche descrivere la distribuzione dei propri valori.

La successione è definita da:

$$
G(1)=1,
$$

$$
G(n)=1 + G!big(n – G(G(n-1))big)qquad text{per } n>1.
$$

La formula è compatta: ogni termine dipende da un valore precedente, il quale
a sua volta viene usato come indice per ottenere un altro valore ancora. È una ricorsione doppiamente annidata, simile a quelle di Hofstadter, ma con un comportamento straordinariamente regolare.

Cosa descrive questa successione? Il risultato più sorprendente è che G(n) indica quante volte il numero n compare nella successione.

La successione, cioè, “racconta se stessa”: una rara e affascinante proprietà di auto-descrizione.

I primi valori sono:

1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, …

e ogni numero n compare nella successione esattamente G(n) volte. La successione è quindi composta da blocchi consecutivi: il blocco dell’1, il blocco del 2, del 3, e così via.
La tabella seguente mostra in modo trasparente i primi blocchi e l’indice finale raggiunto al termine di ciascuno di essi.

Ogni riga mostra tre fatti inseparabili:

• G(n) dice quante volte apparirà il numero n nella successione;
• il blocco di n contiene G(n) ripetizioni consecutive di n;
• la somma cumulativa delle lunghezze dei blocchi indica l’indice massimo raggiunto completando ciascun blocco.

Per esempio, il blocco del 5 si estende fino all’indice 11; il decimo termine della successione appartiene quindi a quel blocco, e di conseguenza G(10)=5.
Allo stesso modo, il blocco del 9 termina all’indice 28 e quello del 10 all’indice 33.

Osservazioni didattiche

La successione di Golomb è monotona non decrescente: i suoi valori non diminuiscono mai, ma restano costanti per intervalli sempre più lunghi. La struttura “a gradini” che ne risulta è una conseguenza diretta della regola G(n) = numero di volte in cui n compare nella successione.

Inoltre la ricorsione è intrinsecamente sequenziale: G(n) non può essere calcolato senza conoscere tutti i valori precedenti.
La tabella dei blocchi organizza in modo visivo le informazioni già ottenute, ma non fornisce alcuna scorciatoia di calcolo.

In definitiva, la successione di Golomb è un esempio paradigmatico di
ricorsione autoreferenziale. Non descrive soltanto il valore successivo, ma la struttura complessiva della successione.

Ancora un esempio di esercizio per una classe di scuola secondaria

Dalla funzione g(n) alle sue varianti annidate, dalle funzioni sposate di Hofstadter alla ricorsione autoreferenziale di Golomb, abbiamo visto come una definizione ricorsiva, anche minima, possa generare strutture inaspettatamente ricche. In tutti questi esempi la ricorsione non si limita a “produrre il passo successivo”: organizza l’intera successione, ne determina l’andamento, ne rivela la logica interna.

Per mostrare quanto poco basti a innescare comportamenti sorprendenti, vale la pena chiudere con un esempio estremamente semplice. Consideriamo la successione definita da:

$$
H(1)=1,qquad
H(n)=leftlfloor frac{n}{H(n-1)} rightrfloor qquad (n>1),
$$

dove il simbolo ⌊ ⌋ indica la parte intera inferiore: ⌊x⌋ è il più grande intero ≤ x. La regola è minimale: ogni valore si ottiene dividendo n per il termine precedente e prendendo la parte intera del risultato. I primi valori sono calcolati immediatamente:

H(1)=1,
H(2)=⌊2/1⌋=2,
H(3)=⌊3/2⌋=1,
H(4)=⌊4/1⌋=4,
H(5)=⌊5/4⌋=1,
H(6)=⌊6/1⌋=6, …

Nonostante la regola sia semplicissima, la successione che ne risulta presenta irregolarità, ripetizioni e cambi di passo improvvisi. È un piccolo promemoria del fatto che la ricorsione, anche quando nasce da una formula scarna, può sfruttare l’interazione tra i propri valori per costruire strutture non ovvie, proprio come accade nei casi che abbiamo discusso sopra.

Esistono però ricorsioni che portano questo principio molto più lontano: ricorsioni che operano sul linguaggio, non soltanto sui numeri, e che generano crescita strutturata e fenomeni universali. Una di queste è la successione Look-and-say di Conway, che merita un’analisi dedicata e sarà il tema del prossimo intervento.

L’articolo Altre ricorsioni sorprendenti proviene da MATMEDIA.IT.