laboratorio caffeina

Argomenti trattati :

# Stack
# Chiamate di procedure
# Ricorsione

Conoscenze minime :

# Un pò di C
# Concetti di programmazione

Inizio :

Come sappiamo,un programma in C per essere eseguito deve essere prima compilato,cioè tradotto in linguaggio macchina equivalente. Oggi voglio accennarvi brevemente ( per ora ) al modo in cui vengono gestite dal compilatore le chiamate di procedure,in tal modo capiremo meglio i problemi da affrontare e come sia vitale per la soluzione l'utilizzo di una struttura dati,lo stack.

Supponiamo che un a procedura Main chiami a un certo punto una procedura A1,la quale chiama a sua volta A2, la quale infine chiama A3. Possiamo schematizzare la situazione come segue :

Quando A3 termina la sua esecuzione l'istruzione che deve essere eseguita è quella,nella procedura A2, successiva alla chiamata A3 e di indirizzo t. Quando A2 termina,l'istruzione successiva deve essere quella di indirizzo s, e infine quando A1 termina va eseguita l'istruzione di indirizzo r.

I ritorni avvengono dunque in ordine inverso alle chiamate.

E' perciò importante che quando vengono chiamate le procedure gli indirizzi di ritorno vengono salvati in un recipiente da cui verranno prelevati in ordine inverso a quello di inserimento. Questo recipiente prende il nome di stack ed è una struttura dati cioè un oggetto su cui sono lecite operazioni particolari.

Uno stack viene anche detto una struttura LIFO ( Last In First Out ) in quanto l'ultimo elemento inserito nello stack è il primo ad uscire. Inizialmente lo stack è vuoto,quando la procedura Main chiama A1,l'indirizzo di ritorno r viene inserito ( push ) nello stack,quando A1 chiama A2 push dell'indirizzo s,quando A2 chiama A3 push di t. Lo stack durante l'esecuzione di A3 è il seguente :

Nel momento in cui A3 termina viene prelevato ( pop ) dallo stack l'indirizzo che sta in cima ( top ) e va in esecuzione l'istruzione di indirizzo t. Quando A2 termina,pop di nuovo e va in esecuzione l'istruzione di indirizzo s,quando termina A1,pop ancora e va in esecuzione l'istruzione r.

Ogni volta che va effettuato un return,l'indirizzo a cui tornare si trova al top dello stack.

Ora passiamo ai progammi ricorsivi. Un programma è detto ricorsivo diretto se viene chiamato all'interno del programma stesso. Un programma F1 è detto ricorsivo indiretto se chiama un programma F2,che chiama a sua volta F3,e così via,finchè Fk chiama F1. Spesso si pensa che è più semplice programmare senza la ricorsione ( infatti molti linguaggi di programmazione non la permettono ) ed è vero in MOLTI casi. Spesso però la versione ricorsiva di un programma è più compatta e facile da capire. Il motivo più importante per usare la ricorsione è che vi sono problemi che sono più facilmente risolvibili utilizzandola.

Per farvi capire meglio,vi mostrerò forse il programma ricorsivo per eccellenza : Il fattoriale.

Possiamo scrivere una semplice funzione C di fattoriale in questo modo :

per capire però bene il meccanismo di ricorsione scriviamo la funzione in modo meno compatto,utilizzando un'altra variabile. I passaggi risultano in tal modo più chiari:

ed ecco cosa succede eseguendo l'istruzione fattor=fact(3) :

Per effetto della chiamata,si entra per la prima volta nella funzione,n vale 3: poichè n non vale 1, la funzione viene chiamata una seconda volta con l'istruzione fact(n-1). Il parametro attuale vale (3-1)=2 per cui,quando entro nella funzione,n vale 2. Chiamo pertanto per la terza volta la funzione con l'istruzione fact(n-1), questa volta il parametro attuale vale (2-1) = 1. Riassumendo,le tre chiamate sono :

prima : fattor = fact(3);
seconda : k = fact(n-1) ( n vale 3 per cui (n-1)=2)
terza : k = fact(n-1) ( n vale 2 per cui (n-1)=1)

quando entro per la terza volta in fact,n vale 1 per cui esco subito dalla funzione restituendo il valore 1,torno all'ultima chiamata fatta,cioè la terza, e il valore 1 viene assegnato a k. Nel contempo,n automaticamente riassume il valore che aveva all'atto della terza chiamata(2).

Va quindi in esecuzione l'istruzione return n*k e viene restituito il valore 2*1=2. Si torna ora all'ultima chiamata fatta,cioè la seconda,k assume il valore 2 e n automaticamente riassume il valore 3. Va ora in esecuzione return n*k e viene restituito il valore 3*2=6. Si torna all'ultima chiamata fatta,questa volta è la prima,fattor = fact(3),e il valore 6 viene assegnato a fattor.

Vi ho mostrato la gestione delle chiamate di procedure mediante stack. Nel momento in cui abbiamo programmi ricorsivi le cose si complicano grandemente : infatti all'atto della chiamata ricorsiva oltre all'indirizzo di ritorno vanno salvati tutti i valori dei parametri in quel momento,e tali valori ripristinati al momento del return.

Per questo,anche se a volte sembra che ci " convenga " usare la ricorsione,dobbiamo stare attenti.

Programmi ricorsivi complessi richiedono il salvataggio di tutto un set di parametri per un numero di volte che dipende dal numero di livelli di ricorsione,questo complica molto il lavoro del compilatore per cui molti linguaggi di programmazione,come già detto,hanno " risolto " il problema alla radice non consentendo l'uso della ricorsione.

Questo è solo una prima parte,alla prossima,ciao !

Condividi