Attivazione di funzioni
• La chiamata/attivazione di funzione viene indicata citando
il nome della funzione e precisando i parametri attuali
• I parametri formali rappresentano un riferimento
simbolico (identificatori) a “oggetti” utilizzati all’interno
della funzione
– il loro valore “iniziale” viene assegnato ad ogni chiamata della funzione
usando i valori dei parametri attuali forniti dal programma chiamante
– i parametri formali sono contenitori, quelli attuali sono i valori da copiarvi
• Nel corpo del main, o di un’altra funzione, la chiamata di
funzione indica il punto e la modalità in cui va eseguita
(attivata) la parte di codice presente nella sua definizione
• L’ambiente locale di una funzione è costituito da:
– parametri formali definiti nell’intestazione della definizione
– parte dichiarativa locale (variabili, costanti, ecc..)
 2000 Prentice Hall, Inc. All rights reserved.
Chiamata di sottoprogrammi (1)
• La chiamata di un sottoprogramma/funzione comporta:
– all’atto della chiamata, la cessione del controllo dell’esecuzione dal
chiamante al chiamato
– l’esecuzione del codice del chiamato, con un proprio ambiente di
esecuzione
– al termine dell’esecuzione il ritorno del controllo al chiamante,
all’istruzione o operazione successiva a quella di chiamata
• Per la corretta gestione del controllo dell'esecuzione è
indispensabile il salvataggio dell’indirizzo di ritorno del
chiamante
• In C l’ambiente locale di esecuzione di una funzione si
crea al momento della chiamata e “termina” al termine
dell’esecuzione della funzione
 2000 Prentice Hall, Inc. All rights reserved.
Chiamata di sottoprogrammi (2)
 2000 Prentice Hall, Inc. All rights reserved.
Scambio delle informazioni
• Lo scambio di informazioni tra funzione chiamante e
chiamata può avvenire mediante passaggio dei parametri
– per fornire i valori “in ingresso” al chiamato, ma anche per mettere in grado
il chiamato di fornire al chiamante i risultati di operazioni
– alla chiamata il valore dei parametri attuali viene copiato nei corrispondenti
parametri formali
• Oppure mediante il valore restituito da una funzione
– per fornire un valore al chiamante
– all’esecuzione dell’istruzione return <espressione> il valore di espressione
viene restituito al chiamante
• Oppure tramite l’uso di variabili globali, cioè visibili,
referenziabili, modificabili da tutte le parti del programma e
sottoprogrammi
– Nei programmi di buona qualità l’accesso e la modifica di variabili globali
da parte dei sottoprogrammi è ridotto al minimo
 2000 Prentice Hall, Inc. All rights reserved.
Esecuzione e ambienti locali (1)
int main() {
…
coeff = fattoriale(n) / (fattoriale(k) * fattoriale(n-k));
}
int fattoriale (int a){ // calcolo del fattoriale: versione iterativa
int i, fatt = 1;
if( a!=0 )
for( i=1; i<=a; i=i+1 ) fatt = fatt * i;
return fatt;
}
 2000 Prentice Hall, Inc. All rights reserved.
Esecuzione e ambienti locali (2)
 2000 Prentice Hall, Inc. All rights reserved.
Ambienti di esecuzione in C (1)
• L’ambiente di esecuzione di una funzione viene creato al
momento della chiamata e “rilasciato” al suo termine
• In una sequenza di chiamate annidate l’ultimo chiamato è
il primo a terminare
main
 funzione1
 funzione2
 funzione2
 funzione1
main
• Per gestire l'annidamento è necessaria una gestione specifica
degli indirizzi di ritorno, deve essere prevista una zona di
memoria di lavoro separata per il salvataggio di ogni
indirizzo di ritorno delle funzioni non ancora terminate
 2000 Prentice Hall, Inc. All rights reserved.
Ambienti di esecuzione in C (2)
• Il C prevede che esista un ambiente di esecuzione per ogni
attivazione di funzione ed essendo l’ultima chiamata la
prima a terminare in C la gestione degli indirizzi di ritorno
è a pila LIFO (Last In First Out)
• La pila di gestione dell’ambiente di esecuzione di funzioni
C è costituita da un insieme di record di attivazione
– esiste un record per ogni sottoprogramma attivo e non ancora terminato
– l’ultimo sottoprogramma attivato è il primo a terminare
– l'indirizzo di ritorno in cima alla pila è sempre relativo all'ultimo
sottoprogramma attivato (cioè il primo che deve terminare)
– questa modalità di gestione degli ambienti di esecuzione consente anche di
supportare la ricorsione
• Un record di attivazione è un’area di memoria contenente:
– l’ambiente locale della funzione (variabili locali e parametri formali)
– l’indirizzo di ritorno al chiamante
– Le informazioni per gestire la memoria nella modalità a stack (pila)
 2000 Prentice Hall, Inc. All rights reserved.
Record di attivazione
• Ad ogni attivazione di una funzione viene allocato in cima
alla pila un record di attivazione con:
– l’indirizzo di ritorno al chiamante che viene scritto nell’apposita locazione
– i parametri formali che ricevono i valori iniziali da quelli dei parametri
attuali della chiamata
– le variabili locali che, al momento della chiamata, hanno un valore non
significativo
• Al termine dell’attivazione il record viene rilasciato, cioè
tolto dalla pila (liberando la memoria) e quindi le variabili
locali vengono “perse”
• La dimensione del record di attivazione di una funzione è
nota e fissa e viene determinata in fase di compilazione
• Non è noto il numero di chiamate (di attivazioni) annidate
dei sottoprogrammi: tale numero dipende dall’esecuzione
del programma
 2000 Prentice Hall, Inc. All rights reserved.
Gestione a pila della memoria (1)
• I record vengono allocati in memoria “uno sopra l’altro”
– la pila dei record cresce dal basso verso l’alto
– il primo record accessibile dello stack è relativo all’ultima funzione attivata
e non ancora terminata
– inizialmente il primo record di attivazione allocato è quello per il main()
• Esiste un registro della CPU chiamato Stack Pointer che
contiene l’indirizzo della cima della pila
• In ogni record di attivazione è memorizzato anche il valore
di stack pointer relativo all’elemento sottostante nella pila
– cioè l’indirizzo nella pila del record di attivazione della funzione chiamante
contenente il suo stato prima della chiamata (da non confondere con
l’indirizzo di ritorno al chiamante che indica dove riprendere l’esecuzione)
• Una parte di memoria RAM è dedicata a contenere l’area di
stack, che ha dimensioni prefissate in fase di compilazione
– si parla di stack overflow quando questa capacità viene superata (“troppi”
annidamenti di chiamate con record di attivazione troppo “grossi”)
 2000 Prentice Hall, Inc. All rights reserved.
Gestione a pila della memoria (2)
 2000 Prentice Hall, Inc. All rights reserved.
Ricorsione (1/9)
• La soluzione ad un problema si dice ricorsiva (l’algoritmo è
ricorsivo) se fa uso di se stessa
ES: ordinare alfabeticamente un elenco di nomi.
Soluzione con algoritmo in forma ricorsiva:
Se l’elenco è vuoto il procedimento è terminato
Altrimenti
Cercare primo elemento nell’insieme dato
Spostare l’elemento in prima posizione
Ordinare alfabeticamente l’insieme rimanente
Fine procedimento
• La soluzione ad un problema (l’algoritmo) può ammettere o
non ammettere formulazione ricorsiva
• Tutti i problemi che ammettono soluzioni ricorsive
ammettono anche soluzioni di tipo iterativo
 2000 Prentice Hall, Inc. All rights reserved.
Ricorsione (2/9)
• Funzioni ricorsive
– Sono funzioni che richiamano se stesse al loro interno (nella definizione)
– La funzione di per sé è in grado solo di risolvere un caso base, ovvero un
problema molto semplice
– Il problema complesso viene comunque risolto perché viene suddiviso in:
• Cosa la funzione può risolvere/fare
• Cosa la funzione non può fare, parte che assomiglia molto al problema originale
• Per risolvere la seconda parte, la funzione lancia una copia di se stessa sul sottoproblema
(passo ricorsivo)
• La divisione è reiterata finchè il sottoproblema del passo ricorsivo non lavora sul caso base
che invece è immediatamente risolvibile
• Quando finalmente il caso base viene risolto
– Il risultato del caso base viene ritornato alla chiamata dell’ultimo passo
ricorsivo e cosi via a ritroso i risultati ottenuti per i sottoproblemi vengono
passati alle varie chiamate ricorsive della funzione
– Ogni chiamata ricorsiva lavora via via su un problema più piccolo fino a
risolvere l’intero problema (N istanze di attivazione della funzione)
 2000 Prentice Hall, Inc. All rights reserved.
Ricorsione (3/9)
• Esempio: il fattoriale
5! = 5 * 4 * 3 * 2 *1
Tenendo conto che
5! = 5 * 4!
4! = 4 * 3!
– E’ evidente che il problema del fattoriale può essere risolto con un algoritmo
di ricorsione
• Come funziona?
– Si risolve il caso base: 1! = 0! = 1
– Si inserisce questo risultato a ritroso nei calcoli ricorsivi più complessi
2! = 2 * 1! = 2 * 1 = 2
3! = 3 * 2! = 3 * 2 = 6
 2000 Prentice Hall, Inc. All rights reserved.
Ricorsione (4/9)
• Esempio: la serie di Fibonacci
0, 1, 1, 2, 3, 5, 8, 13, 21, …
– La regola è che ogni numero della serie è la somma dei 2 precedenti
• Come funziona?
– Fib(n) = Fib(n-1) + Fib(n-2) che è una formula ricorsiva, dove n è l’indice
del numero nella serie partendo dal primo numero che ha indice zero
– Fib(0) = 0, Fib(1) = 1 che è la soluzione del caso base
int fibonacci(int n){
if (n==0 || n==1)
//caso base
return n;
else
return fibonacci(n-1) + fibonacci(n-2);
}
 2000 Prentice Hall, Inc. All rights reserved.
Ricorsione (5/9)
f( 3 )
return
return
f( 1 )
return 1
 2000 Prentice Hall, Inc. All rights reserved.
f( 2 )
+
f( 0 )
return 0
+
f( 1 )
return 1
Ricorsione (6/9)
1 /* Fig. 4.12: fig04_12.c – Funzione ricorsiva di Fibonacci */
2 #include <stdio.h>
3 long fibonacci(long);
1. Prototipo della
funzione
4
5 int main()
6
long result, number;
7
8
printf(“Inserisci un intero: ");
9
scanf("%ld", &number);
10
result = fibonacci(number);
11
printf("Fibonacci(%ld) = %ld\n", number, result);
12
return 0:
13 }
14
15 long fibonacci(long n){
16
if (n == 0 || n == 1)
17
else
/* Definizione della funzione ricorsiva */
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
18 }
Inserisci un intero: 10
Fibonacci(10) = 55
 2000 Prentice Hall, Inc. All rights reserved.
2. Chiamata della
funzione
3. Definizione
della
funzione
ricorsiva
Ricorsione (7/9)
• Esempio: Procedura ricorsiva per visualizzare la
rappresentazione binaria pesata di un numero intero positivo
– riceve un intero positivo da convertire in binario
– ne restituisce la rispettiva sequenza di 0 e 1 della forma binaria
void Converti_bin (int num) {
int resto;
// variabile dell’ambiente locale
resto = num%2;
if (num >= 2)
// costrutto condizionale
Converti_bin (num/2); // chiamata ricorsiva
else { }
// ramo senza chiamata ricorsiva (si può omettere)
printf("%d", resto);
}
 2000 Prentice Hall, Inc. All rights reserved.
Ricorsione (8/9)
 2000 Prentice Hall, Inc. All rights reserved.
Ricorsione (9/9)
 2000 Prentice Hall, Inc. All rights reserved.