La macchina come equivalente didattico del concetto di funzione. Il valore didattico dell’operare ricorsivo.

Nel precedente articolo La macchina dei numeri e la ricerca di un punto fisso avevamo lasciato aperta una domanda: una volta introdotto un numero e ottenuto il risultato, si può rimettere quel risultato nella macchina?

È una domanda che mira a rafforzare il concetto stesso di funzione, che non è soltanto una “regola”, ma comporta anche che si precisi in quale insieme si prendono i valori di ingresso e quale sia l’insieme bersaglio o di arrivo. È però anche la domanda che apre al tema della ricorsività, un argomento che sta  conoscendo una notevole fortuna sia sul piano scientifico sia su quello didattico e, che vanta una storia lunga e ricca di buona matematica, perché affonda le sue radici nelle operazioni elementari e quotidiane che l’uomo compie da sempre.

Un esempio semplice e insieme sorprendente è infatti antico: risale a Erone di Alessandria.

Per calcolare la radice quadrata di un numero positivo $a$, ad esempio  $\sqrt{2}$, Erone di Alessandria (I secolo d.C.) proponeva una procedura comprensibile anche da studenti della scuola media.

Se è $x^2=2$, allora è $x\cdot x=2$, quindi $x=2/x$. Questo significa che se $x_0$ è una buona approssimazione di $\sqrt{2}$, anche $2/x_0$ lo è. Anzi: se $x_0$ è un’approssimazione per eccesso, allora $2/x_0$ lo è per difetto, e viceversa. Gli studenti lo comprendono facilmente: a numeratore fisso, un denominatore più grande produce un risultato più piccolo.

Sulla retta reale, se $x_0$ è a destra di $\sqrt{2}$ (approssimazione per eccesso), $2/x_0$ è a sinistra (per difetto). La loro media aritmetica sta nel mezzo ed è un’approssimazione migliore della radice di 2. Se chiamiamo $x_1$ questa nuova approssimazione e ripetiamo il procedimento con $x_1$, otteniamo valori sempre più vicini a $\sqrt{2}$.

Per esempio, con $x_0 = 1.5$ si ha $2/1.5 = 1.333\ldots$, quindi $x_1 = (1.5 + 1.333\ldots)/2 = 1.4166\ldots$; dopo tre passi si arriva a $x_3 = 1.414215686\ldots$, valore corretto fino alla quinta cifra dopo la virgola. Ad ogni iterazione il numero di cifre corrette raddoppia: si dice che il metodo di Erone ha convergenza quadratica.

Il passo dopo passo delle operazioni ricorsive

L’esempio di Erone mostra una macchina che si alimenta dei propri risultati: l’uscita diventa nuovo ingresso e così via, in un processo in cui ogni passo si compie a partire dal precedente e che incuriosisce su dove potrà andare a parare. Questa idea — simile a molte azioni naturali e quotidiane come camminare (un passo dopo l’altro), mangiare (un cucchiaio dopo l’altro), misurare (trasportando l’unità di misura) — cioè che il passo n-esimo si può compiere solo dopo aver compiuto il passo n–1, è il cuore della ricorsività o ricorsione.

Per chiarirla, possiamo immaginare una macchina di uso comune, come un macinacaffè: si introducono i chicchi, si ottiene la polvere e si può — ipoteticamente — rimettere quella polvere in macchina per ottenere una macinatura ancora più fine. Dopo un certo numero di passaggi, però, il processo si stabilizza: il materiale non cambia più in modo sensibile. Allo stesso modo, in matematica, alcune funzioni tendono verso un valore stabile, altre oscillano, altre ancora mostrano comportamenti più complessi.

Per illustrare meglio procedura e concetto attingiamo ad un altro racconto, ancora più antico del primo.

Sia d la funzione che, ad ogni $n \in \mathbb{N}$, associa la somma dei divisori di $n$, escluso $n$ stesso.

Domanda: esiste in $\mathbb{N}$ un numero $a$ tale che $d^2(a) = a$?

Questo è un problema che, sorprendentemente, attiene all’amicizia. Pare infatti che Pitagora, alla domanda: «Che cos’è un amico?», rispondesse: «Uno che sia l’altro io, come sono 220 e 284».

Perché 220 è “l’altro io” di 284 e viceversa? Ovvero, perché 220 e 284 sono numeri amici? I divisori propri di 220 (cioè tutti tranne 220 stesso) sono:

$1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110$

la cui somma è $284$. I divisori propri di 284 sono:

$1, 2, 4, 71, 142$

la cui somma è $220$. Se indichiamo con $d$ la funzione che associa a ogni numero la somma dei suoi divisori propri, allora $d(220) = 284$ e $d(284) = 220$.
La macchina $d$ non lascia invariato il numero, ma crea un ciclo di periodo 2: un esempio aritmetico di ricorsione doppia.
Il ciclo $220 \leftrightarrow 284$ è, a tutti gli effetti, un caso di $f^2(x) = x$.

Esistono altre coppie di numeri amici.
La seconda in ordine di grandezza — i numeri 1184 e 1210 — fu scoperta solo nel 1866 da un ragazzo di sedici anni.
Un’altra coppia, 17896 e 18416, era già stata trovata da Fermat nel 1636.
Ne esistono altre, ma non tantissime — l’amicizia è un bene prezioso —, e non tutti i numeri hanno amici: ad esempio, 10 non ne ha.
I suoi divisori, 1, 2 e 5, hanno somma 8, ma i divisori di 8 (1, 2 e 4) hanno somma 7, che è un numero primo; e tutti i numeri primi — malgrado la loro importanza, o forse proprio per questa — non hanno amici.
Si potrebbe dire: la solitudine dei numeri primi.

Esistono però anche numeri che hanno più di un amico: sono i numeri socievoli.
Se nella macchina mettiamo in ingresso il numero 12496, esso ricompare dopo cinque reimmissioni: $d^5(12496) = 12496$. Si ottiene così una catena di cinque numeri socievoli:

12496, 14288, 15472, 14536, 14624

Fu il matematico Paul Poulet (1887–1946) a scoprirla nel 1918, insieme a un’altra catena ancora più lunga — di ben 28 numeri — il più piccolo dei quali è 14316.

Fino ad oggi non si conoscono altre catene socievoli così lunghe o più lunghe;
né — cosa curiosa e tuttora irrisolta — sono state trovate catene o cicli di ordine 3, e certamente non ne esistono con numeri inferiori a 50 milioni.
Queste ipotetiche terne socievoli sono state chiamate crowds: «in matematica», scrive David Wells, «un crowd è un fenomeno molto elusivo, che può anche non esistere».

E se nella macchina mettiamo il numero 6?
La somma dei suoi divisori propri è ancora 6. Un numero che coincide con la somma dei propri divisori è detto numero perfetto: è un caso in cui $d(m) = m$. Nella metafora dell’amicizia, i numeri perfetti si potrebbero chiamare auto-amici.

Euclide ed Eulero, in una sintesi che unisce più di venti secoli di storia, li hanno compiutamente caratterizzati, dimostrando — nell’uno e nell’altro verso — che essi hanno la forma:

$$2^{p-1}\,(2^p – 1)$$

dove $2^p – 1$ è un numero primo.
Marin Mersenne ne fu un appassionato studioso, tanto che i numeri della forma $2^p – 1$ sono ricordati come numeri di Mersenne, e quelli che risultano primi sono detti primi di Mersenne.
La scoperta di un nuovo primo di Mersenne svela automaticamente anche un nuovo numero perfetto. L’ultimo numero perfetto trovato, nell’ottobre 2024, corrisponde al 52° numero primo di Mersenne:

$$2^{136{.}279{.}841} – 1$$

Questo numero ha circa 41.024.320 cifre, e il numero perfetto corrispondente è:

$$2^{136{.}279{.}840} \times (2^{136{.}279{.}841} – 1)$$

Per la maggior parte dei numeri accade che $d^{\,n}(a) = 1$, cioè la successione

$$a \;\longrightarrow\; d(a) \;\longrightarrow\; d^{2}(a) \;\longrightarrow\; d^{3}(a) \;\longrightarrow\; \dots$$

si stabilizza, attratta dal numero 1.

Orbite e ricorsività

Il discorso sulla ricorsività in aritmetica è ricchissimo: numeri amici, mirabili, perfetti, catene di numeri socievoli, ma anche le successioni di Fibonacci e di Lucas, e ovviamente, la successione dei numeri naturali, sono tutti esempi descrivibili tramite procedure ricorsive. Ne parleremo in altri articoli, dove però tutto sarà più godibile se prima avremo sistemato e arricchito il nostro lessico di orbite, semi, stabilità, attrattori — come, ad esempio, il numero 1 per $d^{\,n}(a)$.
Da quanto è stato detto, lo schema che generalmente si associa al concetto di funzione è quello di una macchina che trasforma un dato $x_0$ in ingresso in un certo $x_1$ in uscita. Se $f$ è una funzione definita su un dominio $X$ e con $f(X)\subseteq X$, il dato in uscita $x_1$ può essere reintrodotto:

$$x_2 = f(x_1) = f(f(x_0))$$

e così via. Si tratta quindi di studiare il comportamento della sequenza

$$x_0,\; f(x_0),\; f^{2}(x_0),\; f^{3}(x_0),\; \dots$$

che può anche scriversi

$$f^{0}(x_0),\; f^{1}(x_0),\; f^{2}(x_0),\; \dots,\; f^{n}(x_0)$$

dove, con un leggero abuso di notazione:

\(f^{0} = \mathrm{id}_X,\quad f^{1} = f,\quad f^{2} = f \circ f,\quad \text{e in generale}\)

\[
f^{n} = \underbrace{f \circ f \circ f \circ \cdots \circ f}_{\text{$n$ volte}}.
\]

Il valore iniziale $x_0$ si chiama seme. Reintrodurre in $f$ il valore prodotto da $f$ significa cercare una qualche regolarità o struttura. Nel linguaggio dei sistemi dinamici, l’insieme dei punti

$$x_0,\; f(x_0),\; f^{2}(x_0),\; \dots,\; f^{n}(x_0),\; \dots$$

si chiama orbita di $x_0$, mentre l’insieme di tutte le orbite costituisce il quadro delle fasi del sistema.

Può accadere che per qualche $n>1$ si abbia $f^{n}(x_0)=x_0$: si parla allora di orbite periodiche o cicli. Al riguardo, possiamo riprendere due domande poste già nell’articolo da cui abbiamo preso le mosse:

• Esiste una funzione \(h\) tale che, per ogni \(x\), \(h^2(x) = -x\)?
• Esiste una funzione \(k\) tale che \(k^2(x) = \frac{1}{x}\)?

Per la prima, un esempio immediato si trova nel campo dei numeri complessi: basta pensare all’unità immaginaria \(i\) e alla funzione \(h(x) = i \cdot x\). Infatti,

$$h(h(x)) = i \cdot (i \cdot x) = i^2 x = -x.$$

Questa funzione è ciclica di ordine 4 (poiché \(h^4(x)=x\)).

Per la seconda condizione, \(k^2(x) = 1/x\), possiamo considerare, sempre nel campo complesso, la funzione \(k(x) = x^i\). Infatti,

$$(x^i)^i = x^{i^2} = x^{-1} = \frac{1}{x}.$$

Entrambe le funzioni, \(h\) e \(k\), sono dunque esempi di funzioni che trattate ricorsivamente generano orbite periodiche.

L’idea che una funzione, applicata più volte, riporti al punto di partenza — magari con un’inversione o un cambio di segno — è di grande valore formativo: aiuta gli studenti a cogliere il movimento interno delle operazioni matematiche, a vedere i numeri non più come entità statiche ma come oggetti dinamici in trasformazione.

In questa prospettiva, la ricorsione diventa un linguaggio universale: insegna a pensare per processi, a riconoscere le regolarità, a prevedere l’evoluzione di un sistema. È il passo naturale che unisce l’aritmetica elementare ai sistemi dinamici, e la scoperta al pensiero riflessivo. La macchina dei numeri continua a girare: ogni risultato può essere rimesso in gioco, ogni ritorno può aprire un nuovo percorso.

La produzione di orbite periodiche non è però esclusiva delle funzioni complesse.
Un esempio semplice si trova tra le funzioni razionali:

$$f : x \mapsto \frac{1}{1 – x}, \qquad g : x \mapsto \frac{x – 1}{x}.$$

Scrivendo le due funzioni in forma ricorsiva, si ottiene:

$$x_{n+1} = \frac{1}{1 – x_n}, \qquad x_{n+1} = \frac{x_n – 1}{x_n}.$$

Per un valore iniziale generico $x_0$, l’orbita prodotta da $f$ è:

$$x_0 \;\xrightarrow{f}\; \frac{1}{1 – x_0} \;\xrightarrow{f}\; \frac{x_0 – 1}{x_0} \;\xrightarrow{f}\; x_0.$$

Mentre l’orbita generata da $g$ segue il percorso opposto:

$$x_0 \;\xrightarrow{g}\; \frac{x_0 – 1}{x_0} \;\xrightarrow{g}\; \frac{1}{1 – x_0} \;\xrightarrow{g}\; x_0.$$

Le due sequenze descrivono orbite inverse: risultano, infatti, una l’inversa dell’altra:

$$f \circ g(x) = g \circ f(x) = x.$$

Conclusione

Per la scuola, la ricorsività è una palestra naturale del pensiero: invita a osservare i processi, cogliere le relazioni, capire che la conoscenza cresce quando si ritorna criticamente su ciò che si è già fatto.
È la stessa logica che anima la ricerca, l’apprendimento e ogni altra attività umana.

Per approfondire rinviamo al link ricorsività e all’articolo Numeri amici, mirabili e perfetti.