Ciao a tutti, dopo una breve “pausa” in cui abbiamo consolidato le informazioni fino ad ora acquisite tramite qualche esercizio pratico, iniziamo a parlare, con questa nuova lezione del nostro Corso Completo di Programmazione in C, di un argomento molto interessante. In questo articolo vorrei approfondire un concetto che in realtà abbiamo già trattato nella lezione 5, ma poi nelle successive lezioni è stato volutamente tralasciato. Sto parlando delle funzioni.

Abbiamo già imparato che un blocco di codice C ha questa sintassi:

valore_di_ritorno NOME_BLOCCO (parametro1, parametro2)

{

        operazioni nel blocco ;

        operazioni nel blocco ;

        ...

        return VALORE ;

}

ed in particolare il blocco principale (main) ha questa forma:

int main(int argc, char **argv)

{

// Qui  possiamo eseguire il nostro codice.

// Vi ricordo che le righe che iniziano con due "/" sono commenti.

return 0;        

}

I valori tra le parentesi tonde sono i parametri della funzione, vengono separati da virgole e possono essere in numero variabile, da zero fino a 253… ma siete davvero sicuri di voler scrivere una funzione con 253 parametri???

Ciascun blocco di questo tipo si chiama funzione, quindi anche il blocco main, di fatto, costituisce una funzione, anche se di solito tale termine è utilizzato per identificare tutti gli altri blocchi di codice eccetto il main.

All’interno della funzione viene scritto del codice che in qualche modo dipende dai parametri presenti tra parentesi, così quando la funzione verrà invocata (questo è il termine appropriato quando viene utilizzata una funzione) il suo comportamento sarà diverso a seconda dei parametri con i quali è stata invocata.

Non pensate di aver a che fare con un concetto nuovo, per chi tra di voi ha preso un voto più alto del 4 in matematica il concetto di funzione dovrebbe essere già ben chiaro, ma anche per tutti gli altri non dovrebbe essere difficile rendersi conto che tutto quello che ci circonda in qualche modo dipende dai parametri di ingresso…il comportamento del vostro ascensore dipende essenzialmente dal pulsante che avete pigiato, quindi possiamo ragionevolmente affermare che l’altezza raggiunta da un ascensore è funzione del pulsante premuto.

Dopo questa rischiosa divagazione, torniamo al nostro codice C e ci chiediamo: ma a cosa può essere utile avere una (o più) funzioni all’interno dei nostri programmi in C?

A due cose veramente importanti, cioè risparmiare linee di codice (e quindi tempo) e organizzare in maniera ordinata il codice sorgente.

Vediamolo subito con un esempio, supponiamo di dover scrivere un programma in C in cui avremo spesso a che fare con delle date e nel quale sarà molto importante stabilire se un anno è bisestile o meno.

Per chi non lo ricorda un anno è bisestile se è divisibile per 4, con l’eccezione che gli anni secolari (quelli divisibili per 100) che sono bisestili solo se divisibili per 400.

Sono cioè bisestili tutti gli anni la cui numerazione termina con le due cifre 04, 08, 12… fino a 96; gli anni che terminano con 00 sono bisestili solo se l’anno è divisibile per 400, cioè il 1600, il 2000, il 2400 eccetera.

Volete provare a trasformare questa condizione in un programma C? Forza non è difficile, fermatevi un attimo e provate, ma non sbirciate la soluzione! Quando avete fatto continuate pure a leggere.

Per testare se un anno è bisestile potremmo avere un approccio “ingenuo” tentando di tradurre dall’italiano al C

int anno = 1980; //digitiamo un anno di esempio.

if (anno % 4 == 0 ) { //testo se è multiplo di 4

        if ( anno % 100 != 0) { //testo che non sia multiplo di 100

        printf("L'anno %d è bisesto",anno);

}

else { //entra qui se è multplo di 100

        if (anno % 400 == 0) { //verifico che sia multiplo di 400

        printf("L'anno %d è bisesto", anno);

}

}

}

else {

        printf("L'anno %d non è bisesto", anno);

}

Questo codice è paurosamente prolisso, direi che tutto può essere condensato in queste poche righe:

int anno = 1980;

/* spiegazione: se l'anno è multiplo di 4 AND non è multiplo di 100 OR

* l'anno è multiplo di 400 allora è bisestile.

* Commentate sempre le condizioni piuttosto complesse, risparmierete tempo

* successivamente.

*/

if (((anno % 4 == 0 && anno % 100 != 0) || anno % 400 == 0)) {

        printf("Anno bisesto");

}

else {

        printf("Anno non bisesto");

}

Anche se così condensato non è comodo scrivere tutto questo codice ogni volta che abbiamo bisogno di testare se un anno è bisestile o meno, inoltre cosa succederebbe se, dopo aver scritto 100 volte questo test nel nostro programma, ci accorgessimo che contiene un errore? Saremmo costretti a correggere tutte le 100 istanze…una vera seccatura e sicura fonte di errori. Perché non creare quindi una funzione, che accetti come parametro un numero intero che rappresenti l’anno da testare e restituisca il valore “VERO” se l’anno è bisestile e il valore “FALSO” se non lo è? Vi ricordo che in ANSI C non esiste una tipo di variabile specifica per memorizzare il concetto di “VERO” e “FALSO” ma il compilatore C accetta come “VERO” un qualsiasi valore numerico diverso da 0, mentre 0 significa “FALSO”.

Quindi la nostra funzione per testare la bisestività 😀 di un anno accetterà come parametro un numero intero (l’anno da testare) e restuitirà un numero intero. Secondo lo schema precedente allora la struttura dovrebbe essere la seguente:

int isLeapYear(int anno) //mi scuso per gli inglesismi :)

{

        return 0;

}

non ci resta che aggiungere il codice precedente ed avremo creato la nostra prima funzione:

int isLeapYear(int anno)

{

        if (((anno % 4 == 0 && anno % 100 != 0) || anno % 400 == 0)) {

                return 1; //restituiamo TRUE visto che l'anno è bisesto

}

else {

                return 0; //restituiamo FALSO

}

}

Una piccola precisazione, quando in una funzione viene eseguita l’istruzione return tutte le istruzioni successive non vengono eseguite, si dice che la funzione “esce restituendo il valore al chiamante”.

Questa funzione potrà essere utilizzata all’interno del nostro programma per tenere tutto il codice più ordinato e per centralizzare il calcolo in un singolo punto, guardate questo esempio:

int anno = 1980;

if ( isLeapYear(anno) ) {

        printf("Anno bisestile");

}

else {

        printf("Anno non bisestile");

}

non notate com’è più chiaro, sintetico e intuibile? Il codice sorgente completo lo trovate qui.

In alcuni casi le funzioni non necessitano di valori di ritorno e/o di parametri in ingresso, in quel caso è buona norma specificare questa situazione inserendo la parola “void” (come ad esempio questa funzione, che non restituisce alcun valore ma accetta in input un numero intero che specifica quanti ” * ” stampare.

void printStar(int numStar) {

        int i ;

        for ( i = 0; i < numStar; i++) {

        printf("*");

}

}

NOTA: in alcuni linguaggi di programmazione esistono delle differenze tra le funzioni e le procedure, una procedura è una funzione che non restituisce alcun valore. In questo caso la funzione che abbiamo appena visto verrebbe chiamata procedura in un altro linguaggio. In C non viene fatta questa differenza.

Questa funzione, invece, non accetta valori in input e non restituisce alcun valore

void sayHello(void) {

        printf("Ciao e buono studio!");

}

Queste funzioni potrebbero sembrare inutili, ed infatti lo sono, ma sottolineo per l'ennesima volta che in un programma non dovrebbero esserci mai due righe uguali, tutte le ripetizioni dovrebbero essere gestite tramite apposite funzioni, così se c'è un errore c'è un unico posto dove andare a correggerlo.

I parametri

Cosa succede se una funziona modifica il valore che le è stato passato come parametro? Se provo ad eseguire questo codice:

#include 

void incrementa(int value) {

        value = value + 10;

}

int main (int argc, const char * argv[])

{

        int k = 5;

        printf("Valore prima di eseguire incrementa %d\n",k);

        incrementa(k);

        printf("Valore dopo aver eseguito incrementa %d\n",k);

           return 0;

}

Sembrerebbe chiaro che la funzione "incrementa" si occupi di aggiungere 10 al valore della variabile passata come parametro, ma soprendentemente l'output del programma sarà:


Valore prima di eseguire incrementa 5
Valore dopo aver eseguito incrementa 5


sembra che non ci sia stato alcun incremento, come mai?

Presto detto: il linguaggio C utilizza una tecnica denominata "passaggio parametri per valore" secondo la quale quello che succede quando viene invocata la funzione incrementa(k) è che il valore della variabile k viene copiato nella variabile value della funzione. Tutte le modifiche che la funzione apporterà quindi alla variabile value non si ripercuoteranno quindi sulla variabile k, perché non c'è nessun legame tra le due, ecco perché quindi il valore di k è lo stesso sia prima che dopo aver invocato la funzione incrementa(k).

Quindi è impossibile scrivere delle funzioni che modifichino il valore delle variabili passate come parametri? La risposta è no, non è impossibile, ma al momento non abbiamo ancora parlato dei puntatori e quindi la spiegazione è rimandata a tra qualche lezione.

Le funzioni ricorsive

Sicuramente avrete già visto l'immagine qui affianco, affascinante, vero?

Non è una illusione ottica, ma la migliore rappresentazione grafica che io abbia mai trovato del concetto di ricorsione.

Personalmente mi ritengo molto affascinato dal concetto di ricorsione, e autori come Douglas Hofstadter con il suo Gödel, Escher, Bach: un'eterna ghirlanda brillante e Anelli nell'io, artisti come Escher con i suoi quadri hanno accentuato il mio interesse verso qualsiasi cosa che abbia un comportamento ricorsivo.

Non mancano poi esempi cinematografici come il recente inception oppure roba meno colta come South Park in cui producono un "hamburger al quadrato" utilizzando la carne di mucche nutrite con hambuger.

Anche google ci scherza su, provate a cercare "recursion" su google inglese 🙂

Ma in fondo cos'è la ricorsione? Wikipedia definisce algoritmo ricorsivo come un algoritmo espresso in termini di se stesso... a questo punto di solito il cervello parte per la tangente, cercando di trovare il bandolo della matassa come nel quadro mani che si disegnano...non a caso viene spesso citata una frase "Iterare è umano, usare la ricorsione è divino" [L. Peter Deutsch] perché l'utilizzo della ricorsione per la risoluzione di un problema, piuttosto che un approccio iterativo all'inizio può sembrare incomprensibile.

In questo momento non mi sembra il caso di dilungarmi in spiegazioni teoriche sul funzionamento della ricorsione oppure, devo ammetterlo, non mi sento in grado di spiegarlo in termini semplici senza poter gesticolare e scarabocchiare su una lavagna 🙂 ma vorrei quantomeno fornirvi un esempio.

Alcuni problemi più di altri si prestano ad essere risolti con un approccio ricorsivo, primo tra questi è il problema di calcolare il fattoriale di un numero.

Wikipedia ci fornisce sempre la definizione:

In matematica, se n è un intero positivo, si definisce n fattoriale e si indica con n! il prodotto dei primi n numeri interi positivi minori o eguali di quel numero.

In termini più pratici, con un esempio pratico: il fattoriale di 10 è il prodotto di 1*2*3*4*5*6*7*8*9*10

Per scivere un programma che calcoli il fattoriale di un numero possiamo utilizzare l'approccio iterativo, per esempio scrivendo questo codice:

int fattoriale(int n)

{

int i,risultato=1;

for ( i=1 ; i<=n ; i++ ) {

             risultato = risultato * i;

}

return risultato;

}

Ma un approccio ricorsivo risulta più elegante e rispecchia meglio la definizione matematica:

int fattoriale(int n)

{

int risultato;

if (n == 0) {

        risultato = 1;

}

else {

        risultato = n * fattoriale(n-1); // ricorsione!!

}

return risultato;

}

in questo esempio vediamo che la funzione richiama sè stessa passando come parametro una volta n-1, questo è il cuore della ricorsione, quello che avviene è che il computer interrompe l'esecuzione della funzione "principale" ed inizia ad eseguire la funzione richiamata su n-1, a sua volta anche questa verrà interrotta per calcolare via via il fattoriale di n-2, n-3 etc fino ad arrivare a calcolare fattoriale(0). A quel punto l'ultima funzione, finalmente, termina senza effettuare ulteriori chiamate ricorsive quindi la precedente può finalmente chiudersi, così termina la precendente ancora e così via fino a quanto non termina la fattoriale(n-1) e la funzione principale può finalmente fornire in return il risultato.

Un secondo esempio che viene spesso risolto con al programmazione ricorsiva è quello di calcolare l'n-esimo numero della serie di fibonacci. Questo perché già nella definizione dei numeri di Fibonacci c'è il concetto di ricorsione, infatti i numeri di fibonacci sono:

0,1, 1, 2, 3, 5, 8, 13, 21, 34......

la regola è che i primi due sono 0 e 1, i termini successivi sono dati dalla somma dei due termini precedenti. In "matematichese":

fb(0) = 0
fb(1) = 1
fb(n) = fb(n-1) + fb(n-2)

possiamo notare quindi la natura ricorsiva della definizione.

Se volessimo quindi scrivere in C una funzione per calcolare l'n-esimo numero della serie di fibonacci potremmo scrivere:

int fibonacci(int n)

{

if (n==1) {

return 0;

}

else if (n==2) {

return 1;

}

        else {

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

}

}

Spero di non avervi perso per strada e che siate arrivati fino in fondo alla lettura di questo capitolo!

Esercizi

Prima di concludere questa lezione vorrei lasciarvi qualche esercizio, per le soluzioni come sempre vi faremo aspettare un pò di giorni, magari la curiosità potrebbe spingervi intanto a provare a risolversi scrivendo quache riga di codice!

1. Scrivere un programma che utilizzi una funzione per stampare a schermo un quadrato composto da tutti "+". Inoltre la funzione dovrà essere realizzata in moto tale che modificando un solo numero si possa ottenere un quadrato di "+" della dimensione preferita.
2. Scrivere un programma che utilizzi una funzione con due parametri, uno di tipo char e uno di tipo int, passando alla funzione un carattere e un numero la funzione dovrà stampare un quadrato di lato uguale a tale numero e composto dal carattere passato come parametro.

   Ad esempio, chiamando la funzione in questo modo:

   mia_funzione('A', 5)

   il risultato dovrà essere:

   AAAAA
   AAAAA
   AAAAA
   AAAAA
   AAAAA

3. Scrivere un programma che preso in input un intero n calcoli con una funzione ricorsiva la sommatoria da 1 a n

   esempio: n = 10; 1+2+3+4+5+6+7+8+9+10 = ?

   Consiglio: il suo calcolo è analogo a quello per il fattoriale.

Alla prossima 🙂

Letture consigliate:

Il linguaggio C. Principi di programmazione e manuale di riferimento (Accademica)
Brian W. Kernighan - Dennis M. Ritchie
Editore: Pearson | Lingua: Italiano | Brossura: 313 pagine
Prezzo Listino: EUR 27,00
Prezzo Promozione: EUR 22,95 con Spedizione gratuita

C. Corso completo di programmazione
Paul J. Deitel - Harvey M. Deitel
Editore: Apogeo | Lingua: Italiano | Brossura: 640 pagine
Prezzo Listino: EUR 39,00
Prezzo Promozione: EUR 33,15 con Spedizione gratuita