Funzioni in C: parametri, visibilità, pila delle chiamate e ricorsione

Un programma lungo scritto tutto nel main diventa presto illeggibile. Le funzioni permettono di dividere il problema in parti, ciascuna con un nome, dei parametri e un risultato, da scrivere, verificare e riusare separatamente. In questa lezione vediamo come si definiscono, come si passano i parametri, che cosa succede in memoria durante una chiamata (la pila) e la ricorsione.

Definizione e chiamata

#include <stdio.h>

/* prototipo: dice al compilatore nome, parametri e tipo del risultato */
double partitore(double vin, double r1, double r2);

int main(void)
{
    double vout = partitore(12.0, 10e3, 4.7e3);
    printf("Vout = %.2f V\n", vout);         /* Vout = 3.84 V */
    return 0;
}

/* tensione d'uscita di un partitore resistivo */
double partitore(double vin, double r1, double r2)
{
    return vin * r2 / (r1 + r2);
}

• Il prototipo prima del main permette di usare la funzione prima di averla definita. Di solito i prototipi si raccolgono in un file di intestazione .h.
• I parametri formali (vin, r1, r2) sono variabili locali che ricevono i valori degli argomenti passati nella chiamata.
• return termina la funzione e restituisce il valore. Una funzione che non restituisce nulla ha tipo void.

Il passaggio per valore

In C gli argomenti si passano per valore: la funzione riceve una copia, e modificarla non cambia la variabile del chiamante.

void raddoppia(int x) { x = 2 * x; }      /* modifica solo la copia locale */

int main(void)
{
    int n = 5;
    raddoppia(n);
    printf("%d\n", n);                    /* stampa 5, non 10 */
    return 0;
}

Per permettere a una funzione di modificare una variabile del chiamante, o di restituire più di un risultato, si passa il suo indirizzo: è l’argomento della lezione sui puntatori, ed è il motivo per cui scanf vuole &n.

Visibilità e durata delle variabili

• Le variabili locali, dichiarate dentro una funzione o un blocco, esistono solo durante l’esecuzione di quel blocco e sono visibili solo lì.
• Le variabili globali, dichiarate fuori da tutte le funzioni, esistono per tutto il programma e sono visibili ovunque. Comode, ma pericolose: qualsiasi funzione può modificarle, e trovare chi le ha cambiate è difficile.
• Una variabile locale static mantiene il valore tra una chiamata e l’altra: utile per un contatore interno a una funzione.

La pila delle chiamate

Ogni chiamata a funzione crea in memoria un record di attivazione (stack frame) che contiene i parametri, le variabili locali e l’indirizzo a cui tornare. I record si impilano nella pila (stack): quello in cima è la funzione in esecuzione; al return il record viene tolto e l’esecuzione riprende dal chiamante.

Per questo le variabili locali “spariscono” alla fine della funzione: il loro spazio viene riusato dalla chiamata successiva. Restituire l’indirizzo di una variabile locale è uno degli errori più gravi del C.

La ricorsione

Una funzione ricorsiva chiama se stessa su un problema più piccolo. Servono due ingredienti: un caso base che si risolve direttamente e un passo ricorsivo che riduce il problema verso il caso base.

unsigned long fatt(unsigned int n)
{
    if (n <= 1) return 1;          /* caso base */
    return n * fatt(n - 1);        /* passo ricorsivo */
}

La ricorsione è naturale per i problemi che contengono copie più piccole di se stessi: le strutture ad albero, gli algoritmi “dividi e conquista” come il merge sort e la FFT, l’esplorazione di un labirinto.

I costi. Ogni chiamata occupa spazio sulla pila. Con una ricorsione troppo profonda la pila si esaurisce (stack overflow) e il programma si blocca: un rischio concreto sui microcontrollori, dove la pila è di pochi kilobyte. Inoltre alcune ricorsioni ripetono molto lavoro: la formula di Fibonacci scritta come fib(n) = fib(n-1) + fib(n-2) ricalcola gli stessi valori un numero esponenziale di volte; fib(40) richiede oltre 300 milioni di chiamate. La versione con un ciclo ne fa 40.

unsigned long fib(unsigned int n)
{
    unsigned long a = 0, b = 1;
    for (unsigned int i = 0; i < n; i++) {
        unsigned long t = a + b;
        a = b;
        b = t;
    }
    return a;
}

Progettare con le funzioni

Una buona funzione fa una sola cosa, ha un nome che la descrive, pochi parametri e nessun effetto collaterale nascosto. Si può verificare da sola, con un piccolo programma di prova che la chiama con valori di cui si conosce il risultato: è l’idea dei test unitari. La libreria standard del C (<math.h>, <string.h>, <stdlib.h>) è un esempio di funzioni piccole e riusabili: prima di scriverne una, conviene controllare se esiste già.