Eterno ritorno e STOP

Dal mio manuale di programmazione (LISP Trek, 2007) voglio citare alcune pagine scritte sul pensare ricorsivo in linguaggio LISP. Anche in queste povere pagine ingenue, scritte nell’ormai lontano e mitico dicembre 2006, sono contenuti molti miei tic e manie, forse anche una profezia, insomma cose così, molto superficiali, ma le stesse pagine potranno essere lette estraendo un modo di vivere formale, che è sempre più minoritario nel nostro cosiddetto vivere civile.
Mi sto ripetendo?, non mi pare mica :)

E poi si parte e tutto è O.K.
Eugenio Montale, Prima del viaggio, Satura

Il primo itinerario introduce al modo di pensare ricorsivo in LISP. Una funzione ricorsiva è una funzione che chiama sé stessa. Come si individua in un codice sorgente una funzione ricorsiva? Facile, all’interno del codice della funzione da qualche parte deve esistere un’espressione che chiama la funzione stessa. Tutto qui? No, una caratteristica essenziale di una funzione ricorsiva è data dall’esistenza di una condizione di terminazione, il cui scopo consiste nel determinare quando la funzione non deve più essere definita in termini di sé stessa.
Il classico esempio di funzione ricorsiva è quella che calcola il fattoriale di un numero. Questo è indicato con la notazione n! ed è definito come:

n! = 1 se n=0
n! = n x (n - 1)! se n>0
quindi:
n! = 1 x 2 x 3 x ... x n

Visto che per calcolare n! si deve prima calcolare (n-1)! si usa una funzione che invoca sé stessa fino a quando n = 0, così definita:

fatt(n)
se n>0 n*fatt(n-1)
se n=0 1

L'esempio mostra una situazione ideale, cioè il programma termina con n = 0. Ma quando non è presente una condizione di terminazione la funzione chiamerà sé stessa all'infinito, generando un errore nel sistema. In altre parole una funzione ricorsiva non può essere definita esclusivamente in termini di sé stessa, altrimenti darebbe luogo ad una definizione circolare. Quando è utile usare una funzione ricorsiva? Quando ogni chiamata alla funzione rende il problema più semplice da affrontare e se il problema consente di determinare una condizione di terminazione. Nell’esempio fatt(n-1) è più semplice di fatt(n), e la condizione di terminazione è raggiunta con fatt(0). Leggendo con attenzione il listato in basso, vediamo che la funzione fattoriale è chiamata la prima volta (all’interno della funzione principale n!) con un argomento: la variabile numerica intera num (e il compito del programma è di calcolare il fattoriale di num). Lo scopo della variabile n (num), all’interno della funzione fattoriale, è di tenere il conto del numero delle chiamate alla funzione fattoriale. Ad ogni successiva chiamata alla funzione fattoriale (all’interno della stessa) il valore numerico contenuto nella variabile num decresce di un’unità fino ad arrivare a 0. Tutte le espressioni presenti nella funzione fattoriale sono nidificate all’interno della funzione if. Con n = 0 (ecco la condizione di terminazione) la funzione fattoriale termina. Con n maggiore di 0 la funzione fattoriale calcola il prodotto di n per il fattoriale di n-1.

(defun fattoriale ( n )
.(if (= n 0)
..(setq n 1) ; stop!
..(setq n (* n (fattoriale (- n 1))))
.)
)

(defun c:n! ( / num )
.(initget (+ 1 4)) ; 1=non nil, 4=non negativo
.(setq num (getint "\nInserisci un numero intero positivo: "))
.(princ (fattoriale num))
.(princ)
)
;;; eof

Mettendo l’espressione (initget (+ 1 4)) in forma di commento e digitando -1 alla richiesta di input il programma CAD stamperà il seguente messaggio di errore:

Comando: n!
Inserisci un numero intero positivo: -1
Errore irrecuperabile ***
raggiunto il limite della pila interna (simulato)

La chiamata alla funzione fattoriale con argomento -1 dà luogo ad un ciclo ricorsivo infinito, che viene spezzato dal programma CAD. Come test del programma digito questa serie di numeri: 0, 7, 10, 13, 14, 15, 16, 17:

Comando: n!
Inserisci un numero intero positivo: 0
1
Comando: n!
Inserisci un numero intero positivo: 7
5040
Comando: n!
Inserisci un numero intero positivo: 10
3628800
Comando: n!
Inserisci un numero intero positivo: 13
→1932053504
Comando: n!
Inserisci un numero intero positivo: 14
1278945280
Comando: n!
Inserisci un numero intero positivo: 15
2004310016
Comando: n!
Inserisci un numero intero positivo: 16
2004189184
Comando: n!
Inserisci un numero intero positivo: 17
-288522240

Consultando una tavola di fattoriali mi accorgo che il programma dà una risposta errata con n maggiore o uguale a 13 (questo perché il fattoriale di 13 ha superato la dimensione massima consentita ad una variabile intera in CAD). Una soluzione al problema è usare la funzione getreal al posto di getint. La funzione getreal restituisce un numero reale anche quando il numero digitato è un valore intero (per eliminare la parte decimale si userà la funzione fix).

(defun fattoriale ( n )
.(if (= n 0)
..(setq n 1) ; stop!
..(setq n (* n (fattoriale (- n 1))))
.)
)

(defun c:n! ( / num )
.(initget (+ 1 4)) ; 1=non nil, 4=non negativo
.(setq num (getreal "\nInserisci un numero intero positivo: "))
.(princ (fix (fattoriale num)))
.(princ)
)
;;; eof

Comando: N!
Inserisci un numero intero positivo: 13
6.22702e+009