Follow

Ora che conosciamo tutte le basi di Scheme dobbiamo iniziare la parte più difficile, abituare la nostra testa a ragionare secondo il modello funzionale. Per fare questo non possiamo prescindere dall’uso di un linguaggio un po più matematico ma che, vi assicuro, dopo l’impatto iniziale si rivelerà piuttosto automatico (e se avete dubbi potete sempre chiedere su LQH).

La base di scheme, come sapete, è funzionale. In quanto linguaggio funzionale esso va programmato secondo i canoni della teoria delle funzioni ricorsive. Le funzioni ricorsive sono un argomento molto esteso ma di importanza fondamentale nella teoria della calcolabilità. In questa lezione non ci occuperemo della totalità delle funzioni ricorsive ma ci limiteremo a trattare il sottoinsieme delle funzioni ricorsive primitive. Queste funzioni ricorsive hanno, fra le tante, la non trascurabile proprietà di terminare sempre. Ovvero data una qualunque funzione ricorsiva primitiva e un qualsiasi input la funzione cesserà la propria esecuzione restituendoci un risultato.

Senza addentrarci troppo nella teoria sappiate che una funzione ricorsiva è una funzione nella quale esiste un caso in cui la soluzione è diretta e nel caso generale il risultato è ricavabile passando ad un’altra funzione tutti gli argomenti della funzione ricorsiva più il risultato della stessa calcolato su un insieme più piccolo degli argomenti originali. Ovvero:

Detto così sembra enormemente complicato. In realtà nella maggior parte dei casi una funzione ricorsiva può essere riportata alla ricorsione di una funzione ad un argomento e quindi.

Se anche così la cosa vi crea problemi cercherò di risolverli con il più semplice degli esempi: il fattoriale. Ricordate inoltre che la funzione g(y,x) solitamente è implicita.

Il fattoriale espresso ricorsivamente apparirà come:

Che penso sia di facile interpretazione.

I casi in cui risaliamo direttamente al risultato si chiamano casi base, i casi in cui è necessario usare la ricorsione sono detti casi ricorsivi.

Poiché questo è un corso di Scheme vediamo come trasportare questa funzione matematica in una funzione di Scheme. Il passo è semplice.

1
2
3
4
5
(define (fattoriale y)

    (cond ((= y 0) 1)

    (else (* y (fattoriale (- y 1))))

    )

)

Come vedete ci basta inserire in un COND tutti i casi base e tutti i casi ricorsivi. Il caso base, in questo esempio, equivale a y=0, in questo caso infatti il fattoriale è semplicemente 1. Se y non è nulla allora dobbiamo eseguire il passo ricorsivo. Notate che in questo caso la funzione g(y,x) è semplicemente la funzione prodotto.

Il meccanismo di funzionamento è semplice. Le chiamate ricorsive hanno sempre due stati:

• Uno stato di crescita in cui si fanno le chiamate ricorsive inserendo tutto sullo stack.
• Uno stato di calcolo in cui partendo dalla cima dello stack si effettuano i calcoli ripercorrendo le varie chiamate ricorsive a ritroso.

Nel caso di funzioni ricorsive semplici questi stati sono raggruppati in due fasi distinte. Lo stato di crescita continua fino al raggiungimento di un caso base dopo il quale tutte le chiamate sullo stack terminano a cascata.

Facciamo un esempio. Riprendiamo la nostra funzione fattoriale e vediamo come si comporta nel fare il fattoriale di 4.

La prima chiamata sarà

(fattoriale 4)

A questo punto si entra nel COND. Y è chiaramente diverso da zero, quindi viene eseguito il ramo else. La funzione esegue:

(* 4 (fattoriale 3) )

A questo punto viene invocato nuovamente fattoriale. L’esecuzione corrente viene quindi sospesa mentre viene avviata una nuova esecuzione di fattoriale. A questo punto i passi vengono rieseguiti nella nuova chiamata. Y è ancora diverso da zero quindi viene eseguito ancora il ramo else.

( * 4 ( * 3 (fattoriale 2) ) )

Viene aggiunta una nuova chiamata in pila. E così via.

( * 4 ( * 3 ( * 2 ( * 1 (fattoriale 0) ) ) ) )

A questo punto però ci troviamo nella situazione in cui la nuova chiamata di fattoriale è esattamente il caso base. A questo punto la chiamata termina restituendo 1 senza eseguire una nuova chiamata a fattoriale.

( * 4 ( * 3 ( * 2 ( * 1 1 ) ) ) )

Inizia così la fase di calcolo e distruzione. Terminata l’ultima chiamata di fattoriale si riprende dalla chiamata precedente che non fa altro che calcolare 1 x 1 e terminare. E così via a cascata fino alla chiamata originale che termina con il risultato complessivo. Ovvero 24.

Questo è il meccanismo generale di una funzione ricorsiva.

RICAPITOLANDO

• Una funzione ricorsiva è una funzione che richiama se stessa su una porzione più piccola degli argomenti.
• Una funzione ricorsiva primitiva termina sempre.
• Una funzione ricorsiva primitiva è sempre composta da uno o più casi base e uno o più casi ricorsivi.
• Una funzione ricorsiva senza casi ricorsivi non è ricorsiva. Una funzione senza casi base non termina mai.
• Una funzione ricorsiva presenta nella sua esecuzione due stati: uno stato di crescita e uno stato di calcolo e distruzione.

RISORSE

Allego di seguito un file Scheme che contiene alcune piccole funzioni ricorsive numeriche. Potete dargli un occhiata, prima però potete provare a farle da voi. Le funzioni sono:

• Fattoriale (fatto)
• Serie di Fibonacci
• Moltiplicazione
• Somma
• Elevazione a potenza

Il file lo trovate QUI.

Nella prossima lezione continueremo questo argomento cercando di chiarire molti altri aspetti pratici di una funzione ricorsiva e vedremo come applicarla a compiti più complessi del semplice calcolo delfattoriale di un numero.