“To iterate is human, to recurse divine” (L Peter Deutsch).

Gli informatici amano la ricorsione, almeno finché i loro programmi non vanno in stack overflow. Ecco un facile esempio di calcolo ricorsivo dei numeri di Fibonacci in Java (intuitivo anche per i non programmatori)

   int fib(int n) {         if (n < 2) {             return n;         }         return fib(n-1) + fib(n-2);     } 
Cosa c'è di così divino? Il fatto che la funzione  sia definita in termini di se stessa: il numero di Fibonacci di n si ottiene sommando i numeri di Fibonacci dei due predecessori di n, i quali a loro volta si definiscono sommando i numeri di Fibonacci dei due predecessori, e così via fino ad arrivare a 0 e 1.
Ora notate invece la mondana bruttezza del calcolo iterativo della medesima funzione:
   int fib(int n) {
        if (n < 2) {
            return n;
        }
         int f2 = 0;
         int f1 = 1;
         int fn = f2 + f1; // inutile, ma tanto qualcosa ci andava messo
         for (int i = 1; i < n; i++) {
            fn = f2 + f1;
            f2 = f1;
            f1 = fn;
         }
         return fn;
       }
   } 
 L'algoritmo iterativo ha un'efficienza incomparabilmente superiore e non comporta rischi per lo stack, ma guardate quante variabili, quanti caveat per inizializzarle con i valori giusti, e quel tedioso gioco delle tre carte per mantenerne l'allineamento all'interno del ciclo di iterazione. Mettete a confronto tutto questo con l'adamantina essenzialità, il nitore metafisico dell'algoritmo ricorsivo. Siete ora convinti che la ricorsione sia divina?
E la divinità della ricorsione non si limita di certo ai linguaggi programmazione: essa risplende nel Linguaggio tout-court. Ce lo ricorda Andrea Moro nel suo recente libro Parlo dunque sono per il bene di tutti quelli che avessero messo Chomsky in seconda fila, o addirittura meditassero (dopo certi recenti successi della linguistica statistica) di riporlo in soffitta.   
Un esempio dove si vede bene che il linguaggio è ricorsivo è  Alla fiera dell'Est, la famosa canzone di Branduardi, che poi sarebbe un canto pasquale ebraico. 
Per chi non avesse tempo da dedicare all'ascolto, riporto il testo che ci interessa:
Venne il macellaio, che uccise il toro, che bevve l'acqua, che spense il fuoco, che bruciò il bastone, che picchiò il cane, che morse il gatto, che mangiò il topo che al mercato mio padre comprò.
La struttura sintattica di questo lungo periodo è più o meno questa: c'è una proposizione dichiarativa con verbo finito e gruppo nominale, a cui è subordinata una dichiarativa con verbo finito e gruppo nominale, a cui è subordinata una dichiarativa con verbo finito e gruppo nominale, e così via, finchè si arriva a una costruzione un po' invertita (tralascio i dettagli) che chiude la porta ad ulteriori subordinate.
Il cuore della lunga filastrocca di Branduardi (in realtà frutto della mente algerbica di un ignoto ebreo) si può analizzare con un paio di semplicissime regole (qui sotto fornite  in stile Backus-Naur, dove D sta per dichiarazione, F per filastrocca – prendetelo per buono altrimenti la faccenda si complica):
1) D  :=  verbo + gruppo nominale
2) F  :=    D | D che F
Ai più accorti non sarà sfuggito che la regola (2) è ricorsiva: una filastrocca può essere una frase dichiarativa, oppure una frase dichiarativa, la congiunzione che e un'altra filastrocca. La regola dunque è definita nei termini di se stessa. Ed ecco il miracolo: con un sistema di regole così semplice potete interpretare (o produrre) infinite filastrocche, e perfino, se non avete di meglio da fare, filastrocche infinite.
 Il libro di Andrea Moro è per lo più una collezione di ritratti di viris illustribus del pensiero linguistico, ma è attorno alla figura di Noam Chomsky che il suo ragionamento si sviluppa. Com'è noto, Chomsky sostiene che la capacità di costruire e interpretare frasi sintatticamente ben formate sia innata, che la grammatica, insomma, ce l'abbiamo incorporata nel cervello, fin dalla nascita, come feature distintiva del nostro appartenere al genere umano. Moro però va oltre e dice che la precipua caratteristica di questa sintassi è la ricorsività, la quale non può essere il risultato di un processo di adattamento evolutivo. Ora, se si fa caso alla circostanza che il primo personaggio presentato da Moro nel suo libro non sia esattamente un vir ma Dio in persona, la suggestione sembra chiara: la ricorsività linguistica fa parte del disegno intelligente.
Ma se la ricorsività del linguaggio fa parte del disegno di Dio, allora delle due l'una: o si tratta di un dettaglio trascurabile, oppure è una delle cose che maggiormente ci istiga alla trasgressione. Il nostro intelletto linguistico infatti fa pessimo uso del dono della ricorsione: a parte le filastrocche ebraiche o le orazioni di Cicerone, la nostra sintassi è alquanto piatta: due o tre subordinate già ci fanno girare la testa (la filastrocca fa ridere proprio per la sua costruzione inusuale). Un meccanismo infinitario divinamente potente usato in modo così povero che i suoi prodotti potrebbero essere facilmente ricondotti a due o tre squallide iterazioni. Che spreco.
Dati alla mano, grazie all'analisi automatica dei testi, Maurice Gros mostrava già negli anni '70 che le frasi sono combinazioni di strutture  lessico-grammaticali locali e superficiali, che insomma è impossibile separare competenza sintattica e semantica nel modo algebrico che Chomsky aveva suggerito. La linguistica computazionale di oggi è alquanto shallow (detto ai teenager: scialla) nei confronti della sintassi. E vorrà pur dire qualcosa. I doni che ci servono per avere a che fare col linguaggio per come effettivamente lo usiamo sono più probabilmente la memoria e la capacità di astrazione, le quali ci accomunano in qualche modo ai nostri amici animali (con buona pace di Chomsky e d

i Moro). O forse ci si vuol dire che usiamo il linguaggio in modo peccaminoso?