Programmazione strutturata e costrutti fondamentali

Come descrivere il flusso con sequenza, selezione e iterazione

Come possiamo liberarci per sempre dal caos dello spaghetti code e dall’istruzione goto senza perdere la capacità di scrivere qualunque algoritmo?

La risposta arrivò nel 1966 grazie a due informatici italiani, Corrado Böhm e Giuseppe Jacopini, che dimostrarono uno dei teoremi più importanti della storia dell’informatica: non serve mai usare il goto! Qualunque algoritmo, per quanto complesso o aggrovigliato sia il suo diagramma di flusso, può sempre essere riscritto combinando esclusivamente tre mattoncini elementari:

  1. La Sequenza (fare un’azione dopo l’altra).
  2. La Selezione (scegliere tra due strade in base a una condizione).
  3. L’Iterazione (ripetere un blocco finché una condizione è vera).

Questa scoperta ha dato vita alla Programmazione Strutturata, il paradigma su cui si fondano il linguaggio C e tutti i linguaggi moderni.


Il Teorema di Böhm-Jacopini e il principio SESE

Enunciato del Teorema di Böhm-Jacopini (1966)

Teorema di Böhm-Jacopini: Qualunque diagramma di flusso (o algoritmo calcolabile da una Macchina di Turing), anche non strutturato e contenente salti arbitrari, può essere trasformato in un diagramma di flusso semanticamente equivalente (che calcola la stessa funzione sugli stessi dati) utilizzando esclusivamente la composizione (in serie e annidata) di tre strutture di controllo fondamentali:

  1. Sequenza
  2. Selezione (Struttura condizionale)
  3. Iterazione (Ciclo condizionato)
    ed eventualmente l’introduzione di variabili booleane ausiliarie.

Il principio Single-Entry Single-Exit (SESE)

Perché questi tre costrutti eliminano lo spaghetti code? Perché ciascuno di essi è una “scatola chiusa” che rispetta rigorosamente la proprietà SESE (Single-Entry, Single-Exit):

  • Ha un unico punto di ingresso (in alto).
  • Ha un unico punto di uscita (in basso).

Non è mai possibile saltare dall’esterno nel mezzo di una scatola, né scappare da una scatola verso un punto arbitrario del programma. Grazie a questa proprietà, un intero blocco if-else o un intero ciclo while può essere visto dall’esterno come una singola istruzione astratta, e può essere annidato dentro un’altra sequenza, selezione o iterazione come i mattoncini LEGO!


Analisi dettagliata dei 3 Costrutti Fondamentali

1. La Sequenza

È l’esecuzione lineare ordinata di due o più blocchi e : prima viene eseguito interamente , e solo quando termina inizia l’esecuzione di .
In C una sequenza di istruzioni racchiusa tra parentesi graffe { A; B; } costituisce un blocco composto (compound statement), sintatticamente equivalente a una singola istruzione.

flowchart LR
    IN(["Ingresso"]) --> A["Blocco A"] --> B["Blocco B"] --> OUT(["Uscita"])

2. La Selezione (if, if-else, switch)

Permette di scegliere quale blocco eseguire in base al valore di verità (Vero , Falso ) di un predicato logico :

a) Selezione binaria completa (if-else) e unaria (if)

if (condizione) {
    /* Ramo VERO: eseguito solo se 'condizione' != 0 */
    blocco_A;
} else {
    /* Ramo FALSO: eseguito solo se 'condizione' == 0 */
    blocco_B;
}

Se il ramo else viene omesso (if semplice), quando la condizione è falsa non si esegue alcuna azione e si procede direttamente al punto di uscita.

flowchart TD
    IN(["Ingresso"]) --> COND{"Condizione C ?"}
    COND -->|"Vero"| A["Blocco A (Ramo then)"]
    COND -->|"Falso"| B["Blocco B (Ramo else)"]
    A --> JOIN((" "))
    B --> JOIN
    JOIN --> OUT(["Uscita unica"])

b) Selezione multipla (switch-case)

Quando bisogna confrontare una singola espressione intera o carattere (int, char, enum) con un elenco di valori costanti noti a tempo di compilazione, invece di una lunga catena di if ... else if ... else si può usare il costrutto switch:

switch (espressione_intera) {
    case 1:
        printf("Scelta Uno\n");
        break; /* Fondamentale per uscire dallo switch! */
    case 2:
    case 3:
        printf("Scelta Due oppure Tre\n");
        break;
    default:
        printf("Scelta non riconosciuta\n");
        break;
}

Attenzione al fall-through nello switch: in C le etichette case funzionano come punti di ingresso; se si dimentica il break; alla fine di un case, l’esecuzione prosegue eseguendo anche tutte le istruzioni dei case successivi finché non incontra un break o la fine dello switch!


3. L’Iterazione (while, do-while, for)

Permette di ripetere l’esecuzione di un blocco (detto corpo del ciclo) finché permane vera una condizione di permanenza nel ciclo.

a) Iterazione pre-condizionale: il ciclo while

La condizione viene valutata prima di ogni esecuzione del corpo:

while (condizione) {
    corpo_del_ciclo;
}
  • Proprietà: se fin dall’inizio la condizione è Falsa, il corpo del ciclo viene eseguito zero volte ( iterazioni).

b) Iterazione post-condizionale: il ciclo do-while

Il corpo viene eseguito prima, e la condizione viene controllata alla fine di ogni giro:

do {
    corpo_del_ciclo;
} while (condizione); /* Nota il punto e virgola obbligatorio! */
  • Proprietà: il corpo del ciclo viene sempre eseguito almeno una volta ( iterazioni), anche se la condizione è falsa al primo controllo. È ideale per la validazione dell’input (es. “chiedi un numero positivo all’utente finché non lo inserisce correttamente”).
flowchart TD
    subgraph WHILE["Ciclo Pre-condizionale (while: 0 o più volte)"]
        W_IN(["Ingresso"]) --> W_C{"Condizione C ?"}
        W_C -->|"Vero"| W_A["Corpo A"]
        W_A --> W_C
        W_C -->|"Falso"| W_OUT(["Uscita"])
    end
    subgraph DOWHILE["Ciclo Post-condizionale (do-while: almeno 1 volta)"]
        D_IN(["Ingresso"]) --> D_A["Corpo A"]
        D_A --> D_C{"Condizione C ?"}
        D_C -->|"Vero"| D_A
        D_C -->|"Falso"| D_OUT(["Uscita"])
    end

Equivalenza teorica tra while e do-while

Nel Teorema di Böhm-Jacopini basta un solo tipo di ciclo (il while), perché do-while e while si possono sempre tradurre l’uno nell’altro usando sequenza e selezione:

  • Traduzione di do { A; } while (C); usando solo while:
    A;          /* Eseguiamo A la prima volta fuori dal ciclo */
    while (C) {
        A;      /* Ripetiamo A finché C è vera */
    }
  • Traduzione di while (C) { A; } usando solo do-while e if:
    if (C) {
        do {
            A;
        } while (C);
    }

c) Il ciclo for (Iterazione con contatore esplicito)

In C il ciclo for è una forma compatta ed espressiva del ciclo pre-condizionale while, che raccoglie in un’unica riga le tre operazioni fondamentali di gestione del ciclo:

for (inizializzazione; condizione; aggiornamento) {
    corpo_del_ciclo;
}

che è totalmente equivalente al seguente schema while:

inizializzazione;
while (condizione) {
    corpo_del_ciclo;
    aggiornamento;
}

Programmi propri ed equivalenza

Un programma proprio, nel modello dei diagrammi di flusso qui usato, ha un ingresso e un’uscita e tutti i suoi nodi stanno su percorsi dall’ingresso all’uscita. Questa proprietà del grafo non garantisce la terminazione di ogni esecuzione. Una guardia può restare vera indefinitamente.

Per verificare l’equivalenza fissiamo ingressi e risultati osservabili. Per ciascun ingresso, i due programmi devono terminare con lo stesso risultato oppure divergere entrambi. Se osserviamo anche le operazioni di I/O, va conservato il loro ordine. Un ciclo a test iniziale può fare zero iterazioni. Per ricavare un ciclo a test finale da sequenza e test iniziale, eseguiamo il corpo una volta e poi lo ripetiamo finché la guardia è vera, nel modello con corpo a ingresso e uscita singoli.

L’idea costruttiva del teorema è codificare il punto corrente del diagramma in una variabile di controllo. Un ciclo legge quel valore, esegue il blocco corrispondente e imposta il prossimo punto. A ogni iterazione simuliamo un passo del diagramma. La trasformazione dei salti mostra come isolare blocchi più grandi e usare flag solo quando servono.


Esempi guidati

Esempio 1: Somma dei primi numeri interi con while e con for

Scriviamo un programma strutturato che calcola verificando che sia equivalente alla formula di Gauss .

#include <stdio.h>
 
int main(void) {
    int n = 10;
    int somma = 0;
 
    /* Costrutto iterativo strutturato: inizializzazione, test e passo in testa */
    for (int i = 1; i <= n; i++) {
        somma = somma + i;
    }
 
    printf("Somma calcolata col ciclo: %d\n", somma);
    printf("Formula di Gauss n(n+1)/2: %d\n", n * (n + 1) / 2);
    return 0;
}

Esempio 2: Composizione annidata dei 3 costrutti (Verifica di numero primo)

Vediamo come sequenza, iterazione e selezione si annidano tra loro rispettando il principio Single-Entry Single-Exit per stabilire se un intero è un numero primo.

#include <stdio.h>
 
int main(void) {
    int n = 29;
    int e_primo = 1; /* 1 = Vero (ipotesi iniziale), 0 = Falso */
    int d = 2;
 
    /* ITERAZIONE: proviamo i divisori d da 2 fino a quando d*d <= n
       E finché non abbiamo ancora trovato alcun divisore (e_primo == 1) */
    while (d * d <= n && e_primo == 1) {
        /* SELEZIONE annidata dentro l'iterazione */
        if (n % d == 0) {
            e_primo = 0; /* Trovato un divisore! Non è primo */
        }
        d = d + 1;
    }
 
    /* SELEZIONE finale in sequenza dopo il ciclo */
    if (e_primo == 1 && n >= 2) {
        printf("%d e' un numero PRIMO.\n", n);
    } else {
        printf("%d NON e' un numero primo.\n", n);
    }
    return 0;
}

Nota come il ciclo while non usi alcun goto o break per fermarsi appena trova un divisore: incorpora elegantemente la variabile booleana e_primo == 1 nella condizione in testa al ciclo!


Errori frequenti

Errori da evitare

  1. Mettere un punto e virgola ; subito dopo if (...) o while (...) o for (...)
    Scrivere:
    while (i < 10); { /* ERRORE CRITICO: quel ';' dopo la parentesi chiude il while! */
        i++;
    }
    Il punto e virgola ; è l’istruzione vuota: il compilatore interpreta while (i < 10); come “ripeti l’istruzione vuota finché i < 10”, bloccando il programma in un ciclo infinito perché i++ (che sta nel blocco successivo, ormai fuori dal while) non viene mai raggiunto!
  2. Dimenticare le parentesi graffe {} quando un if o un while contiene più di un’istruzione
    Senza { }, in C solo la prima istruzione immediatamente successiva appartiene all’if o al while, indipendentemente dall’indentazione visiva!
    if (x > 0)
        printf("Positivo\n");
        x = 0; /* ATTENZIONE: questa riga viene eseguita SEMPRE, anche se x <= 0! */
    Buona pratica: usa sempre le parentesi graffe { } anche per una sola riga!
  3. Il problema del Dangling Else (Else pendente)
    In due if annidati senza parentesi graffe:
    if (c1) if (c2) A; else B;
    A quale if appartiene quell’else? In C la regola sintattica stabilisce che l’else si lega sempre all’if aperto più vicino (quindi a if (c2)), anche se lo avevate incolonnato sotto if (c1)! Anche qui, le parentesi graffe { } eliminano ogni ambiguità.
  4. Dimenticare break; nei rami di uno switch
    Causa l’esecuzione involontaria (fall-through) dei casi successivi.

Esercizi di prova

Esercizio 1. Differenza tra while e do-while (Base)

Determina cosa stampano i seguenti due frammenti di codice quando entrambi partono con int x = 10;:

/* Frammento A */              /* Frammento B */
int x = 10;                    int x = 10;
while (x < 5) {                do {
    x = x + 1;                     x = x + 1;
}                              } while (x < 5);
printf("A: %d\n", x);          printf("B: %d\n", x);

Esercizio 2. Il pericolo del Dangling Else (Base)

Senza eseguire il codice, determina cosa stampa il seguente programma (fai attenzione all’indentazione ingannevole!) e riscrivilo con le parentesi graffe per far sì che l’else si riferisca effettivamente al primo if:

#include <stdio.h>
int main(void) {
    int a = 5, b = -3;
    if (a > 0)
        if (b > 0)
            printf("Caso 1\n");
    else
        printf("Caso 2\n");
    return 0;
}

Esercizio 3. Conversione da for a while e da while a do-while (Intermedio)

Dato il seguente ciclo for:

int s = 1;
for (int k = 1; k <= 4; k++) {
    s = s * k;
}

a) Riscrivilo in modo semanticamente identico usando un ciclo while.
b) Riscrivilo per il caso generale k <= n (con n intero qualsiasi, anche ) usando esclusivamente if e do-while.

Esercizio 4. Uso corretto di switch-case con raggruppamento (Intermedio)

Scrivi un programma C strutturato che, dato un numero intero mese (da 1 a 12) e una variabile bisestile (1 se l’anno è bisestile, 0 altrimenti), usi un costrutto switch per determinare e stampare il numero di giorni di quel mese (oppure un messaggio di errore se mese non è compreso tra 1 e 12).

Esercizio 5. Costruzione della Successione di Fibonacci strutturata (Avanzato)

La successione di Fibonacci è definita da e per ogni . Scrivi un programma C strutturato che, dato , calcoli e stampi usando solo i costrutti di selezione e iterazione.

Esercizio 6. Teorema di Böhm-Jacopini: dimostrazione costruttiva con variabile di stato (Avanzato)

Spiega come il Teorema di Böhm-Jacopini permette, nel caso più generale in cui un diagramma di flusso abbia blocchi collegati da salti arbitrari non riducibili, di simulare l’intero diagramma usando un unico ciclo while esterno e una variabile intera di stato pc (Program Counter simulato).


Provenienza del materiale

  • Slide e dispensa ufficiale del corso: C1PROG1U1L5_Programmazione_Strutturata_Costrutti_Fondamentali.pdf (Unità 1, Lezione 5 — Teorema di Böhm-Jacopini, programmazione strutturata e costrutti fondamentali).
  • Marco Anisetti, Fondamenti, Appunti_di_fine_Unita_1.pdf, §§ 3.7–3.9.
  • Guida unica di studio – Fondamenti, Guida_Unita_1_teoria_approfondimenti_per_argomento.pdf, §§ 8–9.