La ricorsività negli anni del PNI

Nella didattica degli anni del PNI, la ricorsività come ponte tra matematica classica e informatica educativa.

Quando, nell’aprile del 1985, la ministra Franca Falcucci avviò il Piano Nazionale Informatica (PNI), la ricorsività divenne uno dei temi centrali della didattica della matematica, simbolo del tentativo di coniugare il pensiero algoritmico con la tradizione logico-deduttiva.

La struttura ricorsiva creava indubbiamente molti collegamenti con diversi rami della matematica, dove non è solo una tecnica di calcolo, ma costituisce un principio fondamentale per la definizione di oggetti e per la dimostrazione di proprietà. Era, altresì, adatta per un approccio algoritmico significativo attraverso la scomposizione dei problemi in sotto-problemi più semplici.

Per il linguaggio di programmazione la scelta cadde sul Pascal, che, a differenza del Basic, supportava la ricorsione: una scelta motivata da ragioni didattiche e metodologiche. L’approccio alla programmazione strutturata avrebbe indotto gli studenti a pianificare accuratamente l’algoritmo promuovendo il ragionamento logico e la disciplina mentale.

Sostanzialmente, il Pascal era visto come lo strumento ideale per insegnare i fondamenti concettuali e metodologici dell’informatica, non solo le regole di un linguaggio, ma i modi di pensare che stanno alla base della soluzione algoritmica dei problemi.

La definizione ricorsiva di una funzione \( f(n) \) si articola attraverso:

• un caso base \( f(0) \) oppure \( f(1) \)
• un passo induttivo: \( f(n) \) è definita in funzione di \( f(n-1) \)

Agli studenti abituati a modalità più “lineari” (algoritmi iterativi, esecuzioni passo-passo), il meccanismo poteva sembrare controintuitivo.

Nell’esempio seguente si può osservare come la versione iterativa appaia sicuramente meno criptica e di lettura più agevole.

Ovviamente la verifica al computer, effettuata con successo, era un motivo convincente per accettare la versione ricorsiva. Non era, comunque, immediato pensare a un problema definito in termini di sé stesso. Dal punto di vista della programmazione, era difficile immaginare come una certa procedura “interna” potesse essere richiamata prima della chiusura di quella esterna.

In effetti la ricorsione ha la sua base logica nel Principio di induzione, una regola che, come osserva Poincaré (La Scienza e l’ipotesi), è inaccessibile alla dimostrazione analitica, né può essere provata con l’esperienza. Un “giudizio sintetico a priori” che si impone a noi con un’evidenza irresistibile poiché: «non è altro che l’affermazione della potenza della mente che sa di poter concepire la ripetizione indefinita di un medesimo atto allorché questo sia una volta possibile».

Per quanto riguarda le potenzialità del Pascal, si faceva osservare agli studenti come, in un certo senso, venisse simulato il processo della mente umana.

«Come si calcola il fattoriale di 5?»
– Moltiplicando 5 per 4!
E come si calcola il fattoriale di 4?
– Moltiplicando 4 per 3!
… e così via fino ad arrivare a \( 0! = 1 \).

A questo punto si torna indietro, riprendendo le valutazioni lasciate in sospeso fino ad arrivare al calcolo completo:

• \( 1 \cdot 1 = 1 \)
• \( 2 \cdot 1 = 2 \)
• \( 3 \cdot 2 = 6 \)
• \( 4 \cdot 6 = 24 \)
• \( 5 \cdot 24 = 120 = 5! \)

La ricorsione era possibile in Pascal grazie al fatto che nuove variabili locali venivano generate dinamicamente al momento di richiamare una procedura; i valori di ogni livello non erano distrutti ma rimanevano accessibili al programma finché non fosse completata la chiamata successiva.

Con l’aiuto di ChatGPT ricostruiamo la traccia delle chiamate ricorsive con una grafica stile anni ’90.

Per coinvolgere e interessare maggiormente gli studenti, oltre agli esempi di contenuto matematico, veniva proposta la soluzione di giochi o indovinelli.
Un esempio classico era il noto enigma della torre di Hanoi.

Si deve spostare una torre di \( n \) dischi dal primo perno a sinistra al terzo perno, con le condizioni di muovere un solo disco alla volta e di non poggiare mai un disco su uno più piccolo. I tre perni sono indicati con 1, 2, 3, rispettivamente.

Il problema che, a una prima lettura, sembra un vero rompicapo, si risolve con un opportuno algoritmo ricorsivo.

Si osserva inizialmente che, nel caso semplicissimo di una torre costituita da \( n = 2 \) dischi, il problema si risolve in 3 mosse:

• spostare il disco superiore da 1 a 2
• spostare il disco inferiore da 1 a 3
• spostare il primo disco da 2 a 3

Il perno 2 serve da “appoggio”.

Nel caso di una torre costituita da 3 dischi si può ripetere il ragionamento considerando i due dischi superiori come un blocco unico. Le 3 mosse diventano:

• spostare il blocco da 1 a 2
• spostare il disco inferiore da 1 a 3
• spostare il blocco da 2 a 3

Il problema non è risolto ma è ricondotto al caso precedente (essendo il blocco una torre costituita da due dischi), evidenziando così la sua natura ricorsiva.

Una procedura generale sarà indicata con spostatorre(n, partenza, arrivo, appoggio), ovvero: sposta n dischi dal perno “partenza” al perno “arrivo” usando “appoggio” come perno provvisorio.
Il caso base è \( n = 1 \), corrispondente all’istruzione semplice: spostare il disco da partenza ad arrivo. I tre sottoproblemi diventano:

• spostatorre(n-1, partenza, appoggio, arrivo)
• spostadisco(partenza, arrivo)
• spostatorre(n-1, appoggio, arrivo, partenza)

dove la procedura spostadisco diventa un semplice comando di output:

Osservazione

Alla semplicità dell’algoritmo ricorsivo non corrisponde una bassa complessità computazionale, in quanto il numero \( M_n \), minimo numero di mosse necessarie, aumenta in modo esponenziale al crescere di \( n \).

L’algoritmo riduce il problema \( n \) all’insieme di due problemi \( n-1 \) più una singola mossa; pertanto:

\[
M_n = 2M_{n-1} + 1
\]

La formula chiusa:
\[
M(n) = 2^n - 1
\] può essere dimostrata per induzione, oppure con sostituzioni ripetute, del tipo:
\[
M_n = 2(2M_{n-2} + 1) + 1
= 2\bigl(2(2M_{n-3} + 1) + 1\bigr) + 1
= 8M_{n-3} + 4 + 2 + 1
\] dopo \( k \) iterazioni:
\[
M_n = 2^k M_{n-k} + (2^{k-1} + 2^{k-2} + \dots + 2^1 + 2^0)
\] Poiché a \( k = n-1 \) corrisponde il caso base \( M_1 = 1 \), si può scrivere:
\[
M_n = 2^{n-1} + (2^{n-2} + 2^{n-3} + \dots + 2^1 + 2^0)
\] ovvero:
\[
M(n) = 2^{n-1} + 2^{n-2} + 2^{n-3} + \dots + 2 + 1 = 2^n - 1
\] (somma di n termini di una progressione geometrica di ragione 2 e primo termine uguale a 1).

L’elevata complessità temporale dell’algoritmo è evidente. Nel caso classico \( n = 64 \) il risultato è circa \( 1{,}8 \cdot 10^{19} \) mosse. Secondo i tempi di esecuzione dei computer degli anni ’90 (una mossa in 1 μs, circa) occorrerebbero circa 5000 secoli, riducibili a 500 per i computer più moderni (una mossa in 1 ns, circa).

Anche se molto spesso nelle applicazioni laboratoriali venivano privilegiate le procedure iterative, la struttura ricorsiva rimaneva sempre una risorsa, sintetica ed elegante, per la concettualizzazione.

Riferimenti

• Serotti – Sturlese – Chili, Informatica con il Pascal, Zanichelli
• Peter Grogono, Programmare in Pascal, Franco Muzzio editore