Cap. 5 Deitel

Capitolo 5 (Deitel)
Le funzioni
Indice degli argomenti
5.1 - Introduzione
5.2 - Moduli nei programmi C
5.3 - Funzioni matematiche di libreria
5.4 - Funzioni
5.5 - Definizione di funzioni
5.6 - Dichiarazione di funzioni
5.7 - I file header
5.8 - Chiamare le funzioni: chiamata per valore e per riferimento
5.9 - Generazione di numeri casuali
5.10 - Esempio: un gioco di fortuna
5.11 - Regole di visibilità
5.12 - Ricorsione
 2000 Prentice Hall, Inc. All rights reserved.
5.1 - Introduzione
• “Divide et impera”
– Spesso i programmi possono essere davvero molto complessi
– E’ bene, ove possibile, costruire i programmi partendo da pezzi più piccoli
o componenti, meglio gestibili rispetto all’intero programma iniziale
• E’ più facile risolvere sotto-problemi di minore dimensione e complessità
• Volendo, si può suddividere il lavoro di sviluppo tra più programmatori
– Questi pezzi più piccoli sono chiamati “moduli” del programma
• Sono blocchi di codice indipendenti dagli altri, che svolgono azioni specifiche
• Vantaggi dell’usare i moduli
– I blocchi di codice dei moduli vengono scritti una volta sola ma si possono
riusare ovunque nel resto del programma, invocando il modulo stesso
– L’implementazione dei moduli è nascosta a chi li usa (main o altri moduli)
• Così per il chiamante conta solo “cosa fa il modulo” e non “come la fa”
• L’implementazione può stare anche all’esterno del programma corrente e/o
essere scritta e resa disponibile al programmatore da terze parti (es. libreria C)
– Si costruiscono delle pseudo-librerie di pezzi di programma significativi che
possono essere sempre utilizzate all’occorrenza
– Il codice del programma diventa così più leggibile e facile da modificare
 2000 Prentice Hall, Inc. All rights reserved.
5.2 - Moduli nei programmi C (1/2)
• Funzioni
– Implementano i moduli nel linguaggio C
– I programmi sono scritti combinando funzioni scritte dal programmatore e
funzioni predefinite della libreria standard del C
• La libreria del C contiene molte funzioni d’uso comune
• Semplificano la vita al programmatore, che non riscrive funzioni già esistenti
– Un programma C non è altro che una grossa funzione main() che ingloba
e usa al suo interno funzioni più piccole e/o ne chiama altre esterne
– L’idea è quella di invocare operazioni complesse chiamandole con un
“nome” opportuno e “spiegare” poi altrove come si fa a svolgerle
– La comunicazione tra i vari moduli avviene tramite i parametri passati in
input alle funzioni invocate, i loro valori di ritorno e variabili esterne
• Tipi di funzioni
– Una funzione può compiere un’azione
• Non ritorna nulla a chi la invoca, ma ha altri effetti (es. stampa a video)
– Oppure può anche svolgere calcoli
• Il risultato della computazione è restituito dalla funzione a chi l’ha invocata
 2000 Prentice Hall, Inc. All rights reserved.
5.2 - Moduli nei programmi C (2/2)
• Terminologia
– L’uso di una funzione si dice “chiamata” o “invocazione” della funzione
– Quando si chiama una funzione, si deve fornire il nome della funzione ed
eventuali argomenti (dati in input), chiamati “parametri” della funzione
– Le istruzioni che compongono il corpo della funzione costituiscono la sua
“definizione” e possono modificare i dati ricevuti in input
– La funzione può restituire un risultato (output), chiamato “valore di
ritorno”, che può essere di qualsiasi tipo
– Se non ritorna risultati, allora il tipo del valore di ritorno sarà void
• Esempio concettuale:
– Il capo chiede a un dipendente di svolgere un compito
– Il dipendente raccoglie le informazioni necessarie, esegue il lavoro e
comunica i risultati al capo
– Il capo beneficia di risultati ottenuti dal dipendente senza conoscere i
dettagli su come quest’ultimo li ha ottenuti (information hiding)
 2000 Prentice Hall, Inc. All rights reserved.
5.3 - Funzioni matematiche di libreria
• Funzioni matematiche
– Eseguono i calcoli aritmetici più comuni
– Per importarne la libreria si deve aggiungere #include <math.h>
• Formato della chiamata di funzioni
Nome_funzione( argomento );
• Nel caso di più argomenti, stanno in una lista separati da virgole
• Gli argomenti o parametri attuali sono i valori effettivi su cui la funzione
chiamata deve agire o che le servono per svolgere le proprie operazioni
• Se la funzione ha un valore di ritorno, lo si può assegnare ad una variabile
double radice; radice = sqrt( 900.0 );
– Esempio:
printf( "%.2f", sqrt( 900.0 ) );
• Chiama la funzione sqrt, che ritorna la radice dell’argomento tra parentesi
• Tutte le funzioni matematiche ritornano sempre valori di tipo double
• %.2f indica il formato con cui stampare il risultato (i dettagli più avanti…)
– Gli argomenti possono essere variabili, costanti o espressioni
• printf( "%.2f", sqrt( a + 10 + b * c ) );
 2000 Prentice Hall, Inc. All rights reserved.
5.4 - Funzioni
• Funzioni
– L’uso di funzioni rende il programma modulare
– Tutte le variabili dichiarate all’interno di una funzione sono variabili locali
• Sono riconosciute e usabili solo da tale funzione
– Parametri o argomenti
• Comunicano delle informazioni utili alla funzione chiamata
• Sono a tutti gli effetti variabili locali della funzione
• Benefici
– Le funzioni semplificano lo sviluppo dei programmi
• Scompongono programmi complessi in sotto-problemi più facili da risolvere
• E’ possibile ottimizzare una parte “debole” del programma senza toccare il resto
– Il software modulare è riusabile
• Si usano funzioni già esistenti come “mattoni” per costruire nuovi programmi
• Astrazione: si nascondono i dettagli implementativi interni alle funzioni, per cui
spesso si usano funzioni senza conoscerne la definizione (funzioni di libreria)
• Ci si concentra sulla scelta dei mattoni giusti e non su come essi sono fatti
– Consentono di non replicare inutilmente il codice già esistente
• Evidente risparmio di tempo nella fase di sviluppo
 2000 Prentice Hall, Inc. All rights reserved.
5.5 - Definizione di funzioni (1/2)
• Formato della definizione di una funzione
Tipo_valore_ritorno Nome_funzione( Lista_parametri_formali ){
Dichiarazioni e istruzioni
Restituzione del controllo
}
– Nome_funzione: si può usare qualsiasi identificatore valido
• Secondo gli stessi criteri per i nomi di variabili (e non parole riservate del C)
– Tipo_valore_ritorno: è il tipo del risultato restituito dalla funzione
• Se viene omesso, di default viene impostato a int
• Si usa void se la funzione non ritorna alcun risultato al chiamante
– Lista_parametri_formali: contiene un solo parametro o una lista di
parametri separati da virgola o nessun parametro
• Sono variabili locali della funzione il cui valore effettivo è passato, ad ogni
chiamata di funzione, come input dal chiamante (parametri attuali)
• I parametri attuali sono associati ordinatamente ai relativi parametri formali e,
se il tipo del valore attuale non corrisponde al “tipo formale”, viene convertito
• Per ogni parametro vanno specificati tipo e nome
• Se il tipo viene omesso, di default viene impostato a int
• Se non si passano parametri, si mette ( )
 2000 Prentice Hall, Inc. All rights reserved.
5.5 - Definizione di funzioni (2/2)
• Definizione di una funzione
– Dichiarazioni e istruzioni: sono il corpo della funzione (blocco di codice)
•
•
•
•
Si possono definire delle variabili nel corpo della funzione (locali)
Il corpo della funzione può contenere anche blocchi di codice annidati
Una funzione non può essere definita all’interno di un’altra funzione
Una funzione può usare solo le sue variabili locali, le globali e i parametri
– Restituzione del controllo: la chiamata di funzione fa si che il controllo
di esecuzione passi alla prima istruzione del corpo della funzione
• Esistono due modi per restituire il controllo alla funzione chiamante
• Se la funzione non ritorna valori, si usa return; altrimenti la funzione
restituisce automaticamente il controllo una volta raggiunta la } di chiusura
• Se la funzione ritorna una valore, si usa return espressione; dove
“espressione” è il valore restituito al chiamante
• Qualora il tipo finale dell’espressione fosse diverso dal tipo “dichiarato” del
valore di ritorno dalla funzione, il primo viene convertito nel secondo
– E’ opportuno controllare sempre che chiamata di funzione e valore di
ritorno siano coerenti/consistenti
• Se il valore di ritorno è void, non si può usare var = Funzione (…)
 2000 Prentice Hall, Inc. All rights reserved.
5.6 - Dichiarazione di funzioni (1/3)
• Prima di usare una funzione è necessario dichiararla
– Si deve scrivere il suo prototipo prima dell’istruzione che ne fa uso
– In genere il prototipo corrisponde alla prima riga della sua definizione
– Dichiarazioni e definizioni sono comunque due cose diverse
• Ogni dichiarazione di funzione contiene:
– Il nome della funzione, lo stesso indicato poi nella definizione
– I suoi parametri, ovvero quali dati riceve in ingresso la funzione
• Aventi lo stesso tipo e messi nello stesso ordine che si avrà nella definizione
• In realtà non serve indicarne i nomi, basta specificarne i tipi
– Il tipo del valore di ritorno (di default è int)
• Esempio:
int maximum( int, int, int );
• Riceve 3 valori int in ingresso
• Ritorna un valore int
 2000 Prentice Hall, Inc. All rights reserved.
5.6 - Dichiarazione di funzioni (2/3)
• E’ responsabilità del programmatore controllare che numero
e tipo dei parametri attuali corrispondano a quelli formali
– Comunque, tramite i prototipi, il compilatore è in grado di controllarli
• Il compilatore usa i prototipi per convalidare le chiamate di funzioni
• Se la chiamata non corrisponde al prototipo, si genera un errore di sintassi
che viene rilevato subito dal compilatore
• Il prototipo è una dichiarazione di funzione che anticipa la sua definizione il cui
scopo è proprio controllare la consistenza tra parametri formali e attuali
– Se numero/tipi dei parametri di prototipo e definizione sono inconsistenti:
• Se prototipo e definizione stanno nello stesso file, si genera un errore di sintassi
• Altrimenti sarà rilevato al più un warning e il codice viene compilato comunque
– L’uso del prototipo per una funzione è obbligatorio quando almeno una
sua chiamata anticipa la sua definizione
• In alternativa, se ne scrive solo la definizione, ma va posta prima del main()
• Senza i prototipi, si rinuncia alla convalida del numero/tipo dei parametri usati
• Convertire i tipi dei valori in tipi inferiori può causare errori
– E’ meglio che il programmatore si assicuri che i tipi dei parametri attuali e
dei valori ritornati dalle funzioni siano uguali a quelli “dichiarati”
• Piuttosto che affidarsi alle conversioni automatiche
 2000 Prentice Hall, Inc. All rights reserved.
5.6 - Dichiarazione di funzioni (3/3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* Fig. 5.4: fig05_04.c
Trova il massimo tra tre interi */
#include <stdio.h>
int calcolaMax( int, int, int );
/* Prototipo funzione */
1. Prototipo di
funzione a 3
parametri
int main(){
int a, b, c;
printf( “Inserisci tre interi: " ); /* Riceve i tre interi */
scanf( "%d%d%d", &a, &b, &c );
printf( “Il massimo è: %d\n", calcolaMax(a, b, c));
return 0;
2. Acquisizione
valori di input
3. Chiamata
alla funzione
}
/* Definizione della funzione maximum */
int calcolaMax( int x, int y, int z ){
int max = x;
4. Definizione
della funzione
if ( y > max ) max = y;
if ( z > max ) max = z;
return max;
}
Inserisci tre interi: 22 85 17
Il massimo è: 85
 2000 Prentice Hall, Inc. All rights reserved.
Visualizzazione
del programma
5.7 - File header
• File header (.h) o di intestazione
– Contengono i prototipi delle funzioni nella libreria specificata
stdlib.h, stdlib.h , math.h , ecc.
– Sono caricati nel programma con l’istruzione #include <filename>
#include <math.h>
• Il programmatore può creare dei file header personalizzati
– Deve implementare a parte le definizioni delle funzioni e compilarle
– Deve creare il file contenente i prototipi delle funzioni e i riferimenti a
dove si trovano i file contenenti le rispettive definizioni compilate
– Deve salvare tale file col nome filename.h
– Deve importare i prototipi delle funzioni nel programma che ne fa uso,
con la direttiva al pre-processore #include "filename.h"
– In questo modo è possibile riusare più volte le stesse funzioni esterne in
molteplici programmi differenti
 2000 Prentice Hall, Inc. All rights reserved.
5.8 - Chiamare le funzioni:
chiamata per valore e per riferimento
• Chiamata per valore (quella di default vista finora)
– I parametri passati alla funzione sono copie locali delle variabili originali
– Qualsiasi modifica ai valori di tali copie locali all’interno del corpo della
funzione non ha effetto sui valori delle rispettive variabili originali
– Si usa questa modalità quando la funzione deve usare gli argomenti
ma non necessita di modificarli
• In questo modo si evita qualsiasi modifica accidentale delle variabili
• Chiamata per riferimento
– I parametri passati alla funzione sono riferimenti alle variabili originali
– Eventuali modifiche apportate ai parametri dalla funzione si riflettono
sulle rispettive variabili originali
– Si usa questa modalità solo per le funzioni “affidabili” che necessitano
di modificare le variabili originali
• Affidabile significa scritta in modo consapevole evitando qualsiasi modifica accidentale
• Per ora tratteremo solo la chiamata per valore
– La chiamata per riferimento viene affrontata più avanti (con i puntatori)
 2000 Prentice Hall, Inc. All rights reserved.
5.9 - Generazione di numeri casuali (1/4)
• Si usa la funzione rand
– Non riceve parametri ma ritorna un numero intero “casuale” compreso tra
0 e la costante RAND_MAX (che vale almeno 32767), estremi inclusi
int i = rand();
• Il valore di RAND_MAX fa parte delle impostazioni del compilatore e pertanto
non va cambiato per nessun motivo
– Per disporre di questa funzione occorre caricare la libreria <stdlib.h>
• Il valore di ritorno è pseudo-casuale
– Sembra casuale ma non è veramente casuale
• Ogni chiamata della rand() prende un numero (il successivo) da una sequenza
disordinata ma predefinita (la stessa) di numeri, generata con un algoritmo
• Quindi, ad ogni esecuzione del programma, l’i-esima chiamata della rand()
dà sempre lo stesso valore, ad esempio la seconda chiamata darà sempre 130
– Nessun calcolatore è in grado di per sé di generare numeri casuali
• Casuale significa completamente impredicibile a priori, ovvero che il numero è
scelto da un insieme di valori equiprobabili (da una sequenza non predefinita)
• Usa un algoritmo (deterministico - fa ogni volta le stesse azioni) per generarli
• Per generare numeri davvero casuali deve necessariamente appoggiarsi ad una
“fonte di casualità” esterna (es. il tempo) con cui creare sequenze impredicibili
 2000 Prentice Hall, Inc. All rights reserved.
5.9 - Generazione di numeri casuali (2/4)
• Modificare l’intervallo della rand
– In generale, per ottenere un numero pseudo-casuale nell’intervallo [a,b]
a + ( rand() % ( b – a + 1 ) )
• rand % (b–a+1) ritorna ovviamente un numero compreso tra 0 e (b-a)
• Si aggiunge a per ottentere un numero compreso tra a e b
Esempio: 6 + (rand() % 20) restituisce un numero compreso tra 6 e 25
• Funzione srand(argomento)
– Anche essa è inclusa nella libreria <stdlib.h>
– Riceve come argomento un unsigned int (seme) e lo usa come parametro
nell’algoritmo di generazione della sequenza disordinata di numeri
• Passando valori diversi del parametro si generano sequenze sempre differenti
• Anche usando il seme, se esso non cambia ad ogni esecuzione del
programma, purtroppo la sequenza generata è ancora la stessa ogni volta
– Quindi un’ottima scelta del parametro è srand( time( NULL ) );
• Per usare time(NULL), che restituisce un intero senza segno indicante l’ora
corrente espressa in secondi, è necessario caricare la libreria <time.h>
• Fornisce la fonte di casualità esterna (seme casuale) necessaria a generare
sequenze davvero impredicibili e quindi numeri effettivamente casuali
 2000 Prentice Hall, Inc. All rights reserved.
5.9 - Generazione di numeri casuali (3/4)
1
/* Fig. 5.9: fig05_09.c
2
Ciclo di generazione casuali di numeri tra 0 e 6*/
3
#include <stdlib.h>
4
#include <stdio.h>
5
6
int main(){
7
int i;
8
unsigned seme;
1. Definisce il seme
10
printf( “Inserire il numero da usare come seme di srand: " );
2. Acquisisce in input
il valore del seme
11
scanf( "%u", &seme );
12
srand( seme );
13
for( i = 1; i <= 10; i++ ){
9
14
printf( "%10d", 1 + ( rand() % 6 ) );
15
if( i % 5 == 0 ) printf( "\n" ); /* Va a capo ogni 5 numeri */
16
}
17
return 0;
18 }
 2000 Prentice Hall, Inc. All rights reserved.
3. Usa il seme e srand
per cambiare la
sequenza di numeri
pseudo-casuali
4. Genera e stampa
10 numeri casuali
5.9 - Generazione di numeri casuali (4/4)
Inserire il numero da usare come seme di srand: 67
6
1
4
6
2
1
6
1
6
4
Prima esecuzione
del programma
Inserire il numero da usare come seme di srand: 867
2
4
6
1
6
1
1
3
6
2
Seconda esecuzione
del programma
Inserire il numero da usare come seme di srand: 67
6
1
4
6
2
1
6
1
6
4
Terza esecuzione
del programma
• Riassumendo, per generare sequenze sempre differenti:
– O si richiede il seme all’utente ad ogni esecuzione del programma
• Presuppone che l’utente inserisca sempre numeri diversi
• Il range di valori che in genere l’utente inserisce è in genere molto ristretto
• Quindi la simulazione della casualità che ne deriva non è molto efficiente
– Oppure si usa come seme l’ora corrente
• Non richiede interazioni inutili e poco proficue con l’utente
• Assicura la copertura di tutto il range di valori ammissibili per il parametro
• Garantisce un’eccellente simulazione della casualità in quanto la probabilità
di avere semi uguali e quindi sequenze uguali è praticamente nulla
 2000 Prentice Hall, Inc. All rights reserved.
5.10 - Esempio: un gioco di fortuna (1/4)
• Creare un simulatore del gioco dei dadi con queste regole:
– Si lanciano due dadi (primo lancio)
• Se si ottiene direttamente 7 o 11 al primo lancio, il giocatore vince
• Se si ottiene direttamente 2, 3, o 12 al primo lancio, il giocatore perde
• Negli altri casi, il valore ottenuto diventa il “punteggio” del giocatore
– Dal secondo lancio in poi (se il giocatore non vince/perde al primo)
• Se si ottiene un numero pari al punteggio del giocatore, si vince
• Se si ottiene 7, il giocatore perde
• Negli altri casi si devono lanciare i dadi un’altra volta
• Come fare?
– Il punteggio di ogni lancio è la somma dei 2 punteggi dati dai 2 dadi
– Il numero casuale dato da ciascun lancio di ogni dado è simulato da rand()
• Per garantire la vera casualità si usa l’ora corrente come parametro di srand()
– Si usa una variabile per indicare lo stato del giocatore
• 1=vince, 2=perde, 0=deve rilanciare i dadi
– Si usa un ciclo con sentinella per ripetere il lancio dei dadi, in cui si esce e
si comunica l’esito della giocata solo se lo stato del giocatore vale 1 o 2
 2000 Prentice Hall, Inc. All rights reserved.
5.10 - Esempio: un gioco di fortuna (2/4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/* Fig. 5.10: fig05_10.c - Craps */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int lanciaDadi( void );
int main(){
int statoGiocatore, esitoLancio, punteggio;
srand( time( NULL ) );
esitoLancio = lanciaDadi();
/* primo lancio dei dadi */
switch ( esitoLancio ){
case 7: case 11:
/*
statoGiocatore = 1;
break;
case 2: case 3: case 12: /*
statoGiocatore = 2;
break;
default:
/*
statoGiocatore = 0;
punteggio = esitoLancio;
printf( “Il tuo punteggio
break;
}
 2000 Prentice Hall, Inc. All rights reserved.
vince al primo lancio */
perde al primo lancio */
memorizza il punteggio */
è %d\n", punteggio );
1 Definisce le variabili
2. Utilizza srand() per
randomizzare rand()
3. Chiama la funzione
che simula il lancio
4. Definisce la struttura
switch per stabilire
cosa fare dopo il
primo lancio
5.10 - Esempio: un gioco di fortuna (3/4)
26
27
28
29
30
31
while (statoGiocatore == 0 ){
esitoLancio = lanciaDadi();
if ( esitoLancio == punteggio )
/* continua a lanciare */
/* vince se uguali */
5. Ciclo per ripetere
il lancio finchè si
vince o si perde
statoGiocatore = 1;
else if ( esitoLancio == 7 )
/* perde ottenendo un 7 */
statoGiocatore = 2;
32
33
34
}
if ( statoGiocatore == 1 ) printf( “Hai vinto\n" );
else printf( “Hai perso\n" );
35
return 0;
6. Stampa l’esito
della giocata
(vince/perde)
36 }
37
38 int lanciaDadi( void ){
39
int dado1, dado2, sommaDadi;
40
41
dado1 = 1 + ( rand() % 6 );
42
dado2 = 1 + ( rand() % 6 );
43
sommaDadi = dado1 + dado2;
44
printf(“Hai ottenuto %d + %d = %d\n", dado1, dado2, sammaDadi);
45
return sommaDadi;
46 }
 2000 Prentice Hall, Inc. All rights reserved.
7. Definizione della
funzione che simula
il lancio dei dadi
5.10 - Esempio: un gioco di fortuna (4/4)
Hai ottenuto 6 + 5 = 11
Hai vinto
Prima esecuzione
del programma
Hai ottenuto 6 + 6 = 12
Hai perso
Seconda esecuzione
del programma
Hai ottenuto 4 +
Il tuo punteggio
Hai ottenuto 2 +
Hai ottenuto 6 +
Hai ottenuto 3 +
Hai ottenuto 6 +
Hai vinto
6
è
4
5
3
4
= 10
10
= 6
= 11
= 6
= 10
Terza esecuzione
del programma
Hai ottenuto 1 +
Il tuo punteggio
Hai ottenuto 1 +
Hai ottenuto 5 +
Hai ottenuto 4 +
Hai ottenuto 6 +
Hai ottenuto 1 +
Hai ottenuto 5 +
Hai perso
3
è
4
4
6
3
2
2
=
4
=
=
=
=
=
=
4
5
9
10
9
3
7
 2000 Prentice Hall, Inc. All rights reserved.
Quarta esecuzione
del programma
5.11 - Regole di visibilità (1/2)
• In C, ogni funzione ha il suo ambiente locale
– Comprende i suoi parametri e le variabili definite all’interno funzione
– Variabili locali e parametri formali sono visibili solo all’interno della
funzione di cui fanno parte
• Esiste anche un ambiente globale
– Quello in cui sono definite tutte le funzioni
– Qui si possono definire anche delle variabili, dette variabili globali
• Si chiamano globali proprio perché l’ambiente di definizione di tali variabili
non coincide con quello di nessuna funzione, nemmeno il main()
• Infatti esistono già prima della chiamata del main()
• Per essere tali vengono quindi definite nel punto in cui si scrivono i prototipi
• Sono inizializzate di default a 0, salvo diversa indicazione
– Le variabili globali sono visibili ovunque all’interno del programma
• Ovvero nel main() e in tutte le funzioni il cui corpo è scritto fisicamente dopo
la definizione della variabile globale
– L’unico modo per mascherare una variabile globale all’interno di una
funzione è dichiarare in essa variabili locali omonime
 2000 Prentice Hall, Inc. All rights reserved.
5.11 - Regole di visibilità (2/2)
• Ciclo di vita di una variabile
– Va dall’istante in cui viene allocato lo spazio di memoria per ospitare i valori
della variabile al momento in cui tale spazio viene liberato
• Il ciclo di vita di una variabile globale è l’intera esecuzione del programma
• Il ciclo di vita di una variabile locale va dal momento in cui la funzione in cui
è definita viene invocata all’istante in cui il controllo torna al chiamante
• Visibilità di una variabile (scope)
– Va dalla prima all’ultima riga di codice del programma in cui possibile fare
riferimento alla variabile, per usarne il valore o per modificarla
• Lo scope di una variabile globale è l’intero file in cui è definita
• Lo scope di una variabile locale è il corpo della funzione in cui è definita
– Note sulla visibilità:
• Se in una funzione si cerca di usare una variabile definita localmente in
un’altra funzione, si ha un errore in compilazione
• Se in una funzione si definisce una variabile con lo stesso nome di una locale ad
un’altra funzione, non si hanno errori perché quella esterna non è visibile
• Se dentro una funzione si definisce una variabile locale con lo stesso nome di una
globale non si hanno errori, la globale diventa non visibile e fa fede quella locale
• Le stesse regole valgono per i parametri formali che hanno lo stesso nome di altri
 2000 Prentice Hall, Inc. All rights reserved.
5.12 - Ricorsione (1/5)
• 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
 2000 Prentice Hall, Inc. All rights reserved.
5.12 - Ricorsione (2/5)
• 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.
5.12 - Ricorsione (3/5)
• 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.
5.12 - Ricorsione (4/5)
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
5.12 - Ricorsione (5/5)
1 /* Fig. 4.12: fig04_12.c – Funzione ricorsiva di Fibonacci */
2 #include <stdio.h>
3 long fibonacci(long);
1.
Prototipo della
funzione
long result, number;
2.
Chiamata della
funzione
8
printf(“Inserisci un intero: ");
3.
9
scanf("%ld", &number);
Definizione della
funzione ricorsiva
4
5 int main()
6
7
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.
Esecuzione
del programma