2000 Prentice Hall, Inc. All rights reserved. Capitolo 5 (Deitel) Le funzioni Indice degli argomenti...

2000 Prentice Hall, Inc. All rights reserved.

Capitolo 5 (Deitel) Le funzioni

Indice degli argomenti

5.1 - Introduzione5.2 - Moduli nei programmi C5.3 - Funzioni matematiche di libreria5.4 - Funzioni5.5 - Definizione di funzioni5.6 - Dichiarazione di funzioni5.7 - I file header5.8 - Chiamare le funzioni: chiamata per valore e per riferimento5.9 - Generazione di numeri casuali5.10 - Esempio: un gioco di fortuna5.11 - Regole di visibilità5.12 - Ricorsione


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


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


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)


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 funzioniNome_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 ) );


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


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 ( )


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 (…)


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



• 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



1 /* Fig. 5.4: fig05_04.c2 Trova il massimo tra tre interi */3 #include <stdio.h>45 int calcolaMax( int, int, int ); /* Prototipo funzione */67 int main(){8 int a, b, c;910 printf( “Inserisci tre interi: " ); /* Riceve i tre interi */11 scanf( "%d%d%d", &a, &b, &c );12 printf( “Il massimo è: %d\n", calcolaMax(a, b, c));13 return 0;14 }1516 /* Definizione della funzione maximum */17 int calcolaMax( int x, int y, int z ){

18 int max = x;19

20 if ( y > max ) max = y;

21 if ( z > max ) max = z;22 return max;23 }

Inserisci tre interi: 22 85 17Il massimo è: 85

1. Prototipo di funzione a 3 parametri

2. Acquisizione valori di input

3. Chiamata alla funzione

4. Definizione della funzione

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


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)


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 inclusiint 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



• 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



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;

9

10 printf( “Inserire il numero da usare come seme di srand: " );

11 scanf( "%u", &seme );

12 srand( seme );

13 for( i = 1; i <= 10; i++ ){

14 printf( "%10d", 1 + ( rand() % 6 ) );

15 if( i % 5 == 0 ) printf( "\n" ); /* Va a capo ogni 5 numeri */

16 }

17 return 0;

18 }

1. Definisce il seme

2. Acquisisce in input il valore del seme

3. Usa il seme e srand per cambiare la sequenza di numeri pseudo-casuali

4. Genera e stampa 10 numeri casuali



Inserire il numero da usare come seme di srand: 867 2 4 6 1 6 1 1 3 6 2



Prima esecuzionedel programma

Seconda esecuzionedel programma

Terza esecuzionedel 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


• 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

5.10 - Esempio: un gioco di fortuna (1/4)


1 /* Fig. 5.10: fig05_10.c - Craps */

2 #include <stdio.h>3 #include <stdlib.h>4 #include <time.h>56 int lanciaDadi( void );78 int main(){

9 int statoGiocatore, esitoLancio, punteggio;1011 srand( time( NULL ) );12 esitoLancio = lanciaDadi(); /* primo lancio dei dadi */

13 switch ( esitoLancio ){14 case 7: case 11: /* vince al primo lancio */15 statoGiocatore = 1;16 break;17 case 2: case 3: case 12: /* perde al primo lancio */18 statoGiocatore = 2;19 break;20 default: /* memorizza il punteggio */21 statoGiocatore = 0;22 punteggio = esitoLancio;23 printf( “Il tuo punteggio è %d\n", punteggio );24 break;25 }

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. Ciclo per ripetere il lancio finchè si vince o si perde

6. Stampa l’esito della giocata (vince/perde)

7. Definizione della funzione che simula il lancio dei dadi

28 if ( esitoLancio == punteggio ) /* vince se uguali */

29 statoGiocatore = 1;

30 else if ( esitoLancio == 7 ) /* perde ottenendo un 7 */

31 statoGiocatore = 2;

32 }

33 if ( statoGiocatore == 1 ) printf( “Hai vinto\n" );

34 else printf( “Hai perso\n" );

35 return 0;

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 }

26 while (statoGiocatore == 0 ){ /* continua a lanciare */

27 esitoLancio = lanciaDadi();




Hai ottenuto 6 + 5 = 11Hai vinto

Prima esecuzionedel programma

Seconda esecuzionedel programma

Terza esecuzionedel programma

Quarta esecuzionedel programma

Hai ottenuto 6 + 6 = 12Hai perso

Hai ottenuto 4 + 6 = 10Il tuo punteggio è 10Hai ottenuto 2 + 4 = 6Hai ottenuto 6 + 5 = 11Hai ottenuto 3 + 3 = 6Hai ottenuto 6 + 4 = 10Hai vinto

Hai ottenuto 1 + 3 = 4Il tuo punteggio è 4Hai ottenuto 1 + 4 = 5Hai ottenuto 5 + 4 = 9Hai ottenuto 4 + 6 = 10Hai ottenuto 6 + 3 = 9Hai ottenuto 1 + 2 = 3Hai ottenuto 5 + 2 = 7Hai perso


• 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

5.11 - Regole di visibilità (1/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

5.11 - Regole di visibilità (2/2)


• 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

5.12 - Ricorsione (1/5)


• Esempio: il fattoriale5! = 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



• Esempio: la serie di Fibonacci0, 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);

}




f( 3 )

f( 1 )f( 2 )

f( 1 ) f( 0 ) return 1

return 1 return 0

return +

+return



1 /* Fig. 4.12: fig04_12.c – Funzione ricorsiva di Fibonacci */

2 #include <stdio.h>

3 long fibonacci(long);

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){ /* Definizione della funzione ricorsiva */

16 if (n == 0 || n == 1) return n;

17 else return fibonacci(n - 1) + fibonacci(n - 2);

18 }

1. Prototipo della funzione

2. Chiamata della funzione

3. Definizione della funzione

ricorsiva

Esecuzione del programma

Inserisci un intero: 10Fibonacci(10) = 55

2000 Prentice Hall, Inc. All rights reserved. Capitolo 5 (Deitel) Le funzioni Indice degli argomenti...

Documents

Transcript of 2000 Prentice Hall, Inc. All rights reserved. Capitolo 5 (Deitel) Le funzioni Indice degli argomenti...