Toccare il fondo

Un bambino chiede al padre perché il mondo sia fatto così. Il padre risponde che la terra poggia sul dorso di una tartaruga gigante. Il bambino chiede su cosa poggi la tartaruga. Il padre risponde che poggia su un'altra tartaruga. Il bambino insiste una terza volta, e il padre, ormai senza vie di fuga, chiude la conversazione: sono tartarughe fino in fondo.

La battuta gira in mille salse da almeno due secoli. Nel 1838 un giornale di New York la raccontava con delle rocce al posto delle tartarughe. Nel 1854 un predicatore la citava con una tartaruga sola. Solo nel 1886 compare la prima versione con le tartarughe impilate all'infinito, e da lì la storia rimbalza da William James a Bertrand Russell fino a Stephen Hawking, che la mette in apertura di Dal Big Bang ai buchi neri attribuendola, con cautela, a qualcuno, forse Russell. Ogni narratore aggiunge una variazione, nessuno risale davvero all'originale: la barzelletta si comporta esattamente come il fenomeno che descrive, una catena di eredità senza una fonte visibile in fondo.

 Figura 1: The saying holds that the world is supported by an infinite stack of increasingly larger turtles.

Foto: Pelf, pubblico dominio, via Wikimedia Commons

In informatica, questa storia ha un nome tecnico: caso base mancante. Una funzione ricorsiva è una funzione che, per calcolare il proprio risultato, chiama se stessa su un problema più piccolo. Funziona solo se, prima o poi, la catena di chiamate incontra un caso talmente piccolo da non aver bisogno di ulteriori chiamate: il caso base, la tartaruga che finalmente tocca terra. Se quel caso non c'è, o è scritto male, il programma continua a scendere di livello in livello finché la memoria dedicata alle chiamate, lo stack, non si esaurisce. Il messaggio d'errore che ne segue si chiama, non a caso, stack overflow: il fondo che la metafisica può permettersi di non avere, il computer è costretto a incontrarlo comunque, e nel modo peggiore possibile.

C'è un secondo modo classico di rompere una ricorsione, complementare al primo, e qui l'Italia ha l'originale invece della traduzione. Nel V secolo avanti Cristo Zenone di Elea immagina Achille, il più veloce dei guerrieri, che concede dieci metri di vantaggio a una tartaruga (di nuovo lei) e non riesce mai a raggiungerla: mentre Achille percorre lo spazio che lo separa da lei, la tartaruga avanza di un tratto ulteriore, sempre più piccolo ma sempre maggiore di zero. Qui il difetto è complementare a quello del mito: nella storiella manca il fondo della catena, nel paradosso manca invece l'avvicinarsi della condizione di arresto, che retrocede a ogni passo senza mai annullarsi. Il paradosso si è sciolto solo secoli dopo Zenone, con l'aritmetica delle serie convergenti: la matematica, in questo caso, ha fatto da caso base al posto della logica.

 

Figura 2: Il paradosso di Zenone - Achille battuto dalla tartaruga

Immagine: Martin Grandjean, CC BY-SA 4.0, via Wikimedia Commons

C'è un ultimo tassello di questa storia che riguarda direttamente l'informatica italiana, ed è troppo preciso per lasciarlo fuori. Nel 1959 l'Olivetti presenta il primo calcolatore a transistor del mondo, e lo chiama Elea. Ufficialmente è un acronimo, Elaboratore Elettronico Aritmetico, ma fu il poeta Franco Fortini, che lavorava nell'ufficio pubblicità sotto la direzione di Adriano Olivetti, a costruirlo apposta perché tornasse il nome della città, il cui sito oggi si chiama Velia, vicino Ascea, in Campania. Quando l'informatica italiana ha avuto bisogno per la prima volta di un nome e di un'identità, è tornata istintivamente al luogo dove la logica aveva già inciampato nella sua prima ricorsione, duemilaquattrocento anni prima.

Chi insegna programmazione a scuola conosce bene la reazione che la parola ricorsione suscita in aula: un misto di sospetto e vertigine, come davanti a un corridoio di specchi. Il pregiudizio coglie qualcosa di vero, e merita una precisazione tecnica. Un teorema di equivalenza computazionale garantisce che qualunque funzione calcolabile con ricorsione lo sia anche con la sola iterazione, purché si gestisca esplicitamente uno stack proprio. È quello che fa il compilatore, in silenzio, ogni volta che traduce una chiamata ricorsiva in istruzioni macchina. La ricorsione, allora, non aggiunge potenza di calcolo: toglie al programmatore il lavoro di tenere il conto dei livelli aperti, delegandolo al runtime del linguaggio.

Questo spiega perché, in alcuni casi, evitare la ricorsione sia un esercizio masochistico più che un atto di prudenza. Attraversare un file system di profondità sconosciuta, esplorare un albero binario, far retrocedere un algoritmo di backtracking su una scacchiera delle otto regine: in tutti questi casi la versione iterativa esiste, ma richiede di ricostruire a mano, con un array o una pila esplicita, lo stesso stack che la ricorsione avrebbe gestito da sola. Il codice non diventa più sicuro, diventa solo più lungo e più difficile da leggere, l'esatto opposto di ciò che la parola manutenibile dovrebbe garantire.

È giusto, per onestà, portare in aula anche un caso in cui il verdetto non è scontato: la ricerca dicotomica su un array ordinato. La versione ricorsiva ricalca fedelmente la definizione induttiva del problema, caso base quando l'intervallo si svuota o l'elemento è trovato, passo induttivo che dimezza l'intervallo e richiama la funzione: è la stessa struttura mentale che poi si ritrova identica in mergesort, quicksort, ricerca su alberi, e insegnarla in questa forma costruisce un'intuizione che si trasferisce altrove. La versione iterativa, con un ciclo while che aggiorna due indici, evita l'overhead della chiamata a funzione e usa uno spazio costante invece che proporzionale alla profondità della ricorsione, un vantaggio che in codice a basso livello o su sistemi con vincoli stretti di memoria può contare davvero. Va però ridimensionato l'argomento che si sente ripetere più spesso, quello del rischio di stack overflow: la profondità di questa ricorsione cresce come il logaritmo della dimensione dell'array, per cui anche un miliardo di elementi produce appena una trentina di livelli, una distanza siderale dalla profondità di un file system annidato o di un albero sbilanciato, dove il rischio è reale. Tolto di mezzo quell'argomento debole, restano due criteri legittimi e diversi, chiarezza dimostrativa e riuso concettuale da una parte, parsimonia di risorse dall'altra, e nessuno dei due basta da solo a dichiarare un vincitore.

Donald Knuth, che alla ricorsione ha dedicato un intero capitolo del suo The Art of Computer Programming, nel 1991 pubblicò un breve saggio dal titolo Textbook examples of recursion, in cui osservava quanto siano poveri, dal punto di vista didattico, gli esempi standard con cui si introduce l'argomento nei manuali: il fattoriale, Fibonacci, sempre gli stessi due cavalli di battaglia. Propose al loro posto la funzione 91 di McCarthy e la ricorsione tripla di Takeuchi, casi in cui la terminazione non è affatto ovvia da dimostrare e che per questo, sosteneva, insegnano davvero qualcosa sulla natura della ricorsione, invece di farla digerire per abitudine.

  

Figura 3: Schema dello stack di chiamate, frame che si accumulano e si srotolano

C'è poi un modo tutto informatico di scherzare sulla stessa vertigine. Nella cultura hacker, a partire dagli anni Settanta, è diventata una tradizione battezzare i programmi con acronimi che contengono se stessi. GNU, il progetto di Richard Stallman, sta per GNU's Not Unix: la G di GNU sta per GNU. Wine sta per Wine Is Not an Emulator. Il caso più elaborato è forse Hurd, il kernel del progetto GNU: Hurd sta per Hird of Unix-Replacing Daemons, e Hird sta a sua volta per Hurd of Interfaces Representing Depth, due sigle che si definiscono a vicenda senza che nessuna delle due tocchi mai terra, il gemello informatico di due funzioni mutuamente ricorsive prive di un caso base condiviso. Espandere GNU alla lettera produce, come battuta ricorrente tra i programmatori, una catena che non si chiude mai: GNU's Not Unix's Not Unix's Not Unix, e così via, la stessa identica struttura della tartaruga sotto la tartaruga, scritta da chi quella struttura la programma ogni giorno.

Anche le altre arti giocano da secoli allo stesso gioco. Il Polittico Stefaneschi, dipinto da Giotto intorno al 1320, ritrae il cardinale committente che offre a San Pietro il polittico stesso, l'opera che lo contiene. Velázquez porta lo stesso gesto al suo apice in Las Meninas, dipingendo se stesso nell'atto di dipingere il quadro che stiamo guardando. Il termine tecnico per questo procedimento, mise en abyme, coniato da André Gide nel 1893 mutuandolo dall'araldica, descrive uno scudo che contiene una versione più piccola di sé, e la stessa idea ridotta a meccanismo pubblicitario produce nel 1904 l'effetto Droste, l'infermiera che sulla confezione di cioccolato regge un vassoio con sopra un'altra confezione identica, e così all'infinito.

  

Figura 4: Esempio di effetto Droste: in questo caso è stata inserita la stessa immagine all'interno della cornice in maniera ricorsiva tramite elaborazione digitale.

Foto: Nevit Dilmen, CC BY-SA 3.0, via Wikimedia Commons

In letteratura la ricorsione ha un nome familiare anche a chi non l'ha mai sentita chiamare così: si dice, in italiano, che una storia è costruita a scatole cinesi, dal nome dei set di contenitori artigianali cinesi progettati per essere infilati uno dentro l'altro (la matrioska russa, che spesso usiamo come immagine più immediata, ne è in realtà una derivazione più tarda). Le mille e una notte annidano racconti dentro racconti dentro racconti con una profondità che in certe versioni arriva a includere la stessa cornice di Shahrazad che li narra, e persino Cervantes gioca la stessa carta quando fa incontrare al suo Don Chisciotte dei personaggi che hanno già letto la prima parte del romanzo in cui vivono. Ma è Jorge Luis Borges, che di questi giochi ha fatto una poetica intera, a offrire l'esempio più puro: ne Le rovine circolari un mago sogna un uomo fino a dargli vita reale, per scoprire solo nell'ultima riga di essere lui stesso il sogno di qualcun altro, una ricorsione che rivela il proprio caso base solo alla fine, quando ormai il lettore è arrivato in fondo allo stack insieme al personaggio.

Il cavolo romanesco non somiglia a un frattale, lo è, letteralmente: ogni cimetta ripete in scala ridotta la forma dell'infiorescenza intera. Mandelbrot, che ha dato un nome a questa famiglia di forme, partì da una domanda quasi identica al problema della tartaruga letta al contrario: quanto è lunga la costa della Gran Bretagna? Più piccolo è il righello, più la costa si allunga, perché ogni insenatura ne rivela altre più piccole, in una ricorsione che la sola geometria non saprebbe mai fermare. A fermarla, in natura, è sempre la materia: la cellula più piccola, l'atomo, il limite fisico oltre il quale non esiste più un dettaglio da rivelare. È forse l'unico dominio, tra quelli che abbiamo incontrato, in cui il caso base non va cercato né dimostrato: la fisica lo impone da sé, cosa che non si può fare né con un mito, né con un teorema, né con un racconto. 

A questo punto il ragionamento chiede un salto dichiarato, dal codice alla teologia, un campo lontano da compilatori e stack quanto si può immaginare. Il salto regge, però, e conviene percorrerlo per intero, perché nasconde una distinzione più larga di quanto sembri a prima vista. C'è un'autoreferenzialità che chiude il cerchio: quella di Gödel, che dimostra l'incompletezza dell'aritmetica costruendo una formula che parla di se stessa; quella di Escher, con le sue mani che disegnano se stesse; quella di Borges. C'è infine un ultimo caso, ancora nascosto a chi legge: l'indice di un manuale di programmazione che rimanda a se stesso. E c'è un'autoreferenzialità che invece si sigilla su se stessa: quella di una setta che non risponde a nessuno fuori dai propri confini, o di un potere che si autolegittima senza mai sottoporsi a una verifica esterna. La differenza tra le due, a ben guardare, è la differenza tra relazione e autosufficienza.

È un tema che la teologia conosce da molto prima che esistesse la parola ricorsione. Nella lettura più classica, la sostanza del racconto della caduta non riguarda la disobbedienza in quanto tale, riguarda la pretesa di un'autosufficienza che l'uomo non possiede. Ed è una pretesa che, significativamente, non appartiene neppure a Dio: la teologia trinitaria descrive tre Persone in relazione perenne, non un'unità chiusa su se stessa, un dialogo che non si esaurisce mai in un solo interlocutore.

Anche sul piano biologico l'apertura verso ciò che è fuori di sé è una necessità strutturale, radicata più in profondità di qualunque estetica. Da qui discende, per una strada, il tabù dell'incesto, che impedisce alla generazione di richiudersi su un cerchio troppo stretto. E da qui discende, per un'altra, lo stigma culturale verso l'autoerotismo quando sostituisce, invece di preparare, la relazione con l'altro. In tutti questi casi, dal teorema di incompletezza alla Genesi, il problema non sta mai nel riferirsi a se stessi: sta nell'assenza di un'uscita verso qualcosa che non ci si è dati da soli. È di nuovo, spostato dal codice all'esistenza, un caso base assente.

Forse è proprio questo il punto che vale la pena portare in classe. La ricorsione non fa paura in sé: fa paura quando resta un gesto invisibile, una scatola chiusa di cui non si vede il fondo. Disegnare alla lavagna lo stack delle chiamate, con i livelli che si accumulano e poi si srotolano uno a uno all'indietro, trasforma la vertigine in un disegno concreto, misurabile, con tanto di numero di riga. La tartaruga più in basso smette di essere un mistero metafisico e diventa una voce precisa in una tabella. Miti, paradossi filosofici, quadri, romanzi e acronimi da terminale raccontano da secoli la stessa storia sotto travestimenti diversi: qualcuno, prima o poi, deve avere il coraggio di rispondere tartarughe fino in fondo e fermarsi lì. In un programma, quel qualcuno è il caso base. Se manca, non è la vertigine a fermarci: è lo stack a farlo per noi, con la delicatezza di un crollo improvviso.

Manca un'ultima tartaruga, ed è la più nascosta di tutte. Nell'indice analitico di The C Programming Language, Kernighan e Ritchie inserirono alla voce recursion un elenco di numeri di pagina, e tra questi, in coda, il numero della pagina dell'indice stesso, quella in cui la voce recursion compare. Una voce che rimanda a se stessa, un caso base mai scritto, lasciato lì di proposito, come ultima battuta di due autori che la ricorsione la conoscevano meglio di chiunque altro. Chi va a cercarla, la trova. E se cerca ancora, la ritrova.