Note Ingegneria Informatica · UniTN
Programmazione 1
Esercizi
Lezione
ott, giorno?
bozza

Ricorsione

Argomento di Programmazione 1. Fatto a lezione a ottobre, deck 8.1 intero: slide 1-122. Prima: Funzioni, dove ci sono la chiamata, i parametri per valore e per indirizzo e la pila dei record di attivazione. La versione con il ciclo della scala a passi da 1, 2 o 3 è in Ciclo while ed esempi › La scala a passi da 1, 2 o 3.

Il filo del deck:

ricorsione fuori dal C     scatole cinesi, albero genealogico,        slide 3-15
   |                       fiocco di Koch, H-tree
Torri di Hanoi             gioco, soluzione con 4 dischi, 15 mosse    slide 16-36
   |
formulazione induttiva     caso base + caso induttivo                 slide 37-59
   |                       Hanoi in C, 2^n - 1 mosse, pseudocodice
ricorsione in C            diretta e indiretta                        slide 60-62
   |
esempi                     sommatoria su array, fattoriale,          slide 63-79
   |                       lista inversa, MCD (due versioni)
esecuzione                 record di attivazione, passaggio per       slide 80-91
   |                       indirizzo, gestione a pila della memoria
Fibonacci                  albero delle chiamate, tempo esponenziale, slide 92-106
   |                       memoization
esercizi                   scala 1-2-3 ricorsiva, cammini del robot   slide 107-122
                           su una griglia, con memoization

1Definizioni

Ricorsione (slide 3-15). Un concetto è ricorsivo quando si definisce usando se stesso, su un caso più piccolo. Il prof parte da esempi fuori dalla programmazione:

L’H-tree si costruisce partendo da un segmento di lunghezza arbitraria e disegnando due segmenti più corti, ad angolo retto, alle estremità; a ogni turno i segmenti si riducono di 2\sqrt 2. Si usa nel progetto di circuiti integrati VLSI e di antenne stampate: occupa lo spazio in modo efficiente, arriva quasi a tutti i punti del rettangolo esterno, e porta il segnale di clock a tutte le foglie con lo stesso ritardo, perché ogni foglia è alla stessa distanza dalla radice (slide 15).

In tutti gli esempi c’è la stessa struttura: un oggetto grande fatto da copie più piccole dello stesso oggetto, e un punto in cui ci si ferma (cba non è controllata da nessuno; il segmento diventa troppo corto per disegnarlo).

Formulazione induttiva di un algoritmo (slide 38 e slide 56). Con le parole del prof, si specificano due passi fondamentali:

Prima di tutto bisogna trovare “la dimensione lungo la quale muoversi” (slide 56): il numero di dischi in Hanoi, nn nel fattoriale, la lunghezza dell’array nella sommatoria. Il caso induttivo deve far scendere quella dimensione, altrimenti non si arriva mai al caso base.

Il caso induttivo in tre passi (slide 57).

  1. Dall’istanza di dimensione nn si ricavano una o più istanze dello stesso problema di dimensione più piccola (n−1n-1, n−2n-2, …, 1).
  2. Si suppone di saper già risolvere quelle istanze più piccole.
  3. Si compongono le loro soluzioni, con i calcoli che servono, per ottenere la soluzione dell’istanza di partenza.

Il passo 2 è quello che sembra un imbroglio e non lo è. È lo stesso ragionamento dell’induzione in matematica: se il caso base è giusto, e se “giusto per n−1n-1” implica “giusto per nn”, allora è giusto per ogni nn. Quando scrivi la funzione non devi seguire con la testa tutte le chiamate: ti basta fidarti che la chiamata sul caso più piccolo restituisca il risultato giusto.

Pseudocodice generale (slide 58-59):

SOLUZIONE funzione_ricorsiva(PROBLEMA p, altri parametri...)
{
    if (siamo nel caso base) {
        risolvi direttamente il problema p: sia "sol" la soluzione;
        return sol;
    }
    else {  // siamo nel caso induttivo
        estrai da p uno o più sottoproblemi pi di dimensione minore di p;
        per ogni i, sia:
            si = funzione_ricorsiva(pi, altri parametri...);
        componi le soluzioni si ed effettua gli altri calcoli necessari
        ad ottenere una soluzione "sol" del problema p;
        return sol;
    }
}

Ricorsione diretta e indiretta (slide 61-62). Un sottoprogramma P chiama, durante la sua esecuzione, un altro sottoprogramma Q; Q a sua volta chiama un terzo R, …; se R chiama nuovamente P la ricorsione è indiretta. Se invece P chiama se stesso durante la propria esecuzione la ricorsione è diretta. Tutti gli esempi del deck sono diretti.

diretta      P ──> P ──> P ──> ...
indiretta    P ──> Q ──> R ──> P ──> ...

Record di attivazione (slide 80-82). Il prof si chiede se il modello di esecuzione delle funzioni visto prima basti per una funzione che chiama se stessa. Con lo schema conosciuto, per FattRic(3)FattRic(3): il valore del parametro attuale 3 viene copiato nel parametro formale n, inizia l’esecuzione, arriva la nuova chiamata FattRic(2)FattRic(2), e il nuovo valore 2 dovrebbe essere copiato “nella cella n”. Ma la cella n contiene ancora il 3, che servirà dopo per fare 3 * .... Se ci fosse una sola cella n il 3 andrebbe perso.

La risposta è la gestione dinamica dell’area dati: lo stato dipende da ciascuna attivazione della funzione. A ogni chiamata si crea un nuovo record di attivazione, una zona di memoria con i parametri, le variabili locali e il punto in cui tornare. Quattro chiamate attive di FattRic vogliono dire quattro celle n diverse, ognuna col suo valore.

Gestione a pila della memoria (slide 86-90). La memoria che serve per eseguire un programma ha una componente statica (le variabili globali, note prima di partire) e una dinamica, per tutto ciò che non è noto a priori (slide 87): quante attivazioni ci saranno dipende dai dati. I record di attivazione si impilano come i sassi della foto della slide 86: l’ultimo messo è il primo tolto (LIFO, last in first out). Una chiamata mette un record in cima; quando la funzione finisce il suo record viene tolto, e si riprende la funzione del record sotto, che è proprio quella che aveva fatto la chiamata.

2Concetti

2.1La pila chiamata per chiamata

La figura segue FattRic(3) (slide 82), una colonna per ogni momento. Il record in rosso è quello in esecuzione.

int FattRic(int n)
{
    if (n == 0)
        return 1;
    else
        return n * FattRic(n - 1);
}

La stessa cosa come tabella, una riga per evento. La colonna “pila” elenca i record dal fondo alla cima.

passoeventopila (fondo → cima)cosa resta in sospeso
1main chiama FattRic(3)main, n=3
23 == 0 falso, serve FattRic(2)main, n=3, n=23 * ?
32 == 0 falso, serve FattRic(1)main, n=3, n=2, n=13 * ?, 2 * ?
41 == 0 falso, serve FattRic(0)main, n=3, n=2, n=1, n=03 * ?, 2 * ?, 1 * ?
50 == 0 vero: caso base, ritorna 1main, n=3, n=2, n=13 * ?, 2 * ?, 1 * 1
6n=1 calcola 1 * 1, ritorna 1main, n=3, n=23 * ?, 2 * 1
7n=2 calcola 2 * 1, ritorna 2main, n=33 * 2
8n=3 calcola 3 * 2, ritorna 6main

Due fasi da tenere separate:

Nella slide 82 il prof disegna proprio questo: a sinistra la colonna dei valori di n (3, 2, 1, 0) con le frecce verso il basso, a destra la colonna dei risultati (1, 11 = 1, 21 = 2, 3*2 = 6) con le frecce verso l’alto.

Esempio 1, la profondità della pila. Con FattRic(n) la pila arriva ad avere n+1n+1 record di FattRic contemporaneamente (da n fino a 0). La versione col for ne ha sempre uno solo. Questo è il “per n=3n = 3 usano entrambe le stesse risorse (memoria)?” della slide 83: no, la ricorsiva ne usa 4 contemporaneamente, l’iterativa 1.

Esempio 2, una pila che sale e scende più volte (slide 88-90). Il prof disegna main che chiama P1, P1 chiama P2’, P2’ chiama P3, P3 chiama P2” (una seconda attivazione di P2: ricorsione indiretta P2 → P3 → P2).

evento                         pila (fondo → cima)
main → P1 → P2' → P3 → P2''    main  P1  P2'  P3  P2''          slide 88
P2'' finisce, poi P3           main  P1  P2'                    slide 89
P2' chiama P4                  main  P1  P2'  P4                slide 90
P4, P2', P1 finiscono          main

Il record di P4 finisce nello stesso posto dove prima c’erano P3 e P2”: la memoria della pila si riusa. Sotto la pila, in fondo, ci sono le variabili globali, che restano lì per tutto il programma.

2.2Stampe prima e dopo la chiamata ricorsiva

È il tracing che esce di più. La regola viene dalla pila: un’istruzione prima della chiamata ricorsiva si esegue durante l’andata, quindi in ordine di chiamata; un’istruzione dopo si esegue durante il ritorno, quindi in ordine inverso.

#include <stdio.h>

void prima(int n)
{
    if (n == 0)
        return;
    printf("%d ", n);
    prima(n - 1);
}

void dopo(int n)
{
    if (n == 0)
        return;
    dopo(n - 1);
    printf("%d ", n);
}

void entrambe(int n)
{
    if (n == 0) {
        printf("| ");
        return;
    }
    printf("%d ", n);
    entrambe(n - 1);
    printf("%d ", n);
}

int main(void)
{
    prima(3);
    printf("\n");
    dopo(3);
    printf("\n");
    entrambe(3);
    printf("\n");
    return 0;
}

Output (verificato):

3 2 1 
1 2 3 
3 2 1 | 1 2 3 

Tracing di entrambe(3), una riga per istruzione eseguita. Il rientro mostra la profondità.

istruzionen del record in cimastampa
entrambe(3): 3 == 0 falso3
printf prima della chiamata33
. entrambe(2): 2 == 0 falso2
. printf prima22
. . entrambe(1): falso1
. . printf prima11
… entrambe(0): caso base0|
. . printf dopo, entrambe(1) finisce11
. printf dopo, entrambe(2) finisce22
printf dopo, entrambe(3) finisce33

La seconda stampa di ogni record usa il suo n: quando entrambe(1) riprende dopo il ritorno di entrambe(0), il suo n vale ancora 1, perché ogni attivazione ha la sua cella.

Esempio 2, le cifre di un numero. n % 10 è l’ultima cifra, n / 10 toglie l’ultima cifra (come in Ciclo while ed esempi).

#include <stdio.h>

void cifre_inverse(int n)
{
    printf("%d", n % 10);
    if (n >= 10)
        cifre_inverse(n / 10);
}

void cifre(int n)
{
    if (n >= 10)
        cifre(n / 10);
    printf("%d", n % 10);
}

int main(void)
{
    cifre_inverse(4271);
    printf("\n");
    cifre(4271);
    printf("\n");
    return 0;
}
chiamatann % 10n >= 10
142711vero
24277vero
3422vero
444falso: caso base

cifre_inverse stampa la cifra prima di scendere: in ordine di chiamata, 1 7 2 4. cifre stampa dopo: in ordine di ritorno, cioè dalla chiamata 4 alla 1, 4 2 7 1. Output (verificato): 1724, poi 4271. Qui il caso base non ha un return esplicito: è il ramo in cui l’if è falso e non si chiama più niente.

Esempio 3, due chiamate ricorsive con la stampa in mezzo (lo schema di Hanoi):

#include <stdio.h>

void righello(int n)
{
    if (n == 0)
        return;
    righello(n - 1);
    printf("%d ", n);
    righello(n - 1);
}

int main(void)
{
    righello(3);
    printf("\n");
    return 0;
}

Con due chiamate per record la pila non basta più a vedere tutto in una colonna: si disegna l’albero delle chiamate, con ogni chiamata come nodo e le sue chiamate come figli, da sinistra a destra nell’ordine in cui avvengono.

                       r(3)
            ┌───────────┼────────────┐
          r(2)       stampa 3       r(2)
       ┌────┼────┐              ┌────┼────┐
     r(1) st.2  r(1)          r(1) st.2  r(1)
    ┌─┼─┐      ┌─┼─┐         ┌─┼─┐      ┌─┼─┐
  r0 1 r0    r0 1 r0       r0 1 r0    r0 1 r0

La stampa si legge visitando l’albero da sinistra a destra: 1 2 1 3 1 2 1 (verificato). È la sequenza dei dischi mossi da Hanoi con 3 dischi (sotto, Esempi svolti).

2.3Contare le chiamate

Si scrive una ricorrenza: le chiamate di f(n)f(n) sono 1 (la chiamata stessa) più le chiamate fatte dai figli. Il caso base conta 1.

funzionericorrenza delle chiamatevaloriformula
FattRic(n)C(0)=1C(0) = 1, C(n)=1+C(n−1)C(n) = 1 + C(n-1)C(3)=4C(3) = 4n+1n + 1
righello(n), HanoiC(0)=1C(0) = 1, C(n)=1+2C(n−1)C(n) = 1 + 2C(n-1)C(3)=15C(3) = 152n+1−12^{n+1} - 1
Fibo(n)C(0)=C(1)=1C(0) = C(1) = 1, C(n)=1+C(n−1)+C(n−2)C(n) = 1 + C(n-1) + C(n-2)C(5)=15C(5) = 15, C(6)=25C(6) = 252F(n+1)−12F(n+1) - 1
CountWays(n)C(n)=1C(n) = 1 se n≤0n \le 0, C(n)=1+C(n−1)+C(n−2)+C(n−3)C(n) = 1 + C(n-1) + C(n-2) + C(n-3)C(3)=13C(3) = 13, C(10)=979C(10) = 979esponenziale

Esempio 1, FattRic(3): chiamate con nn = 3, 2, 1, 0, quindi 4. Lineare: ogni chiamata ne fa al massimo una.

Esempio 2, Fibo(5): C(2)=1+1+1=3C(2) = 1 + 1 + 1 = 3, C(3)=1+3+1=5C(3) = 1 + 3 + 1 = 5, C(4)=1+5+3=9C(4) = 1 + 5 + 3 = 9, C(5)=1+9+5=15C(5) = 1 + 9 + 5 = 15. Controllo con la formula: F(6)=8F(6) = 8, 2⋅8−1=152 \cdot 8 - 1 = 15. Contate anche con un contatore globale nel programma: 15 (verificato).

Esempio 3, il conteggio della scala. Nella nota sul ciclo while ci sono già le chiamate della versione ricorsiva di ChatGPT, con casi base fino a n=2n = 2: 289 per n=10n = 10 (Ciclo while ed esempi › La scala a passi da 1, 2 o 3). La versione del prof (slide 110) ha come unico caso base n≤0n \le 0, quindi scende di due livelli in più: per n=10n = 10 fa 979 chiamate (contate con uno script). Le due successioni sono le stesse spostate di 2: Cprof(n)=CGPT(n+2)C_{prof}(n) = C_{GPT}(n+2), e infatti Cprof(8)=289C_{prof}(8) = 289.

Una regola pratica per i casi semplici: con una chiamata ricorsiva per record le chiamate sono tante quanti i livelli (lineare); con due o più chiamate che scendono di poco (n−1n-1, n−2n-2) le chiamate crescono esponenzialmente.

2.4Ricorsione contro iterazione

Ogni funzione ricorsiva vista nel deck ha anche una versione con un ciclo. Il prof le confronta sul fattoriale (slide 73-75, slide 83):

domanda della slideFatt (con il for)FattRic
moltiplicazioni per n=1n = 10 (il for parte da i = 2 e non entra)1 (1 * FattRic(0))
moltiplicazioni per n=3n = 32 (i = 2, 3)3 (n = 3, 2, 1)
confronti per n=3n = 33 (i <= n con i = 2, 3, 4)4 (n == 0 con n = 3, 2, 1, 0)
memoria per n=3n = 3un record (n, ris, i)4 record di FattRic insieme

Contati con due contatori dentro le funzioni (verificato). La differenza è piccola sul fattoriale, ma le chiamate costano: ogni chiamata crea un record, copia i parametri, salva il punto di ritorno.

Quando la ricorsione è peggio di molto:

Quando conviene: quando il problema è ricorsivo per natura (Hanoi, gli alberi della seconda parte del corso), la ricorsiva è corta e si scrive copiando la definizione, mentre l’iterativa richiede di gestire a mano quello che la pila fa da sola.

Memoization (slide 105). “Riduciamo il tempo di esecuzione memoizzando (annotando) i risultati di istanze già eseguite. Quando eseguiremo una funzione per un determinato valore, andremo prima a cercare nell’array contenente i valori della funzione eseguita in precedenza.” Si tiene un array inizializzato a 0 (0 = “non ancora calcolato”); prima di calcolare f(n)f(n) si guarda se la casella n è già piena, e dopo averlo calcolato lo si scrive lì. Ogni valore si calcola una volta sola: Fibonacci passa da esponenziale a lineare.

2.5Ricorsione su array e stringhe

La dimensione lungo cui muoversi è la lunghezza: si risolve il problema su un array di nn elementi usando lo stesso problema su n−1n-1 elementi, e il caso base è l’array vuoto (o di un elemento). Con le stringhe la fine si riconosce dal '\0' (Stringhe), quindi non serve passare la lunghezza.

Tre modi di “accorciare”:

ultimi n-1 elementi esclusi    f(a, n)  usa a[n-1]   e   f(a, n-1)      sommatoria, massimo
indice che avanza              f(s, i)  usa s[i]     e   f(s, i+1)      lunghezza, stampa al contrario
due indici che si stringono    f(a,i,j) usa a[i],a[j] e  f(a, i+1, j-1) inversione, palindroma
#include <stdio.h>

int lunghezza(const char s[])
{
    if (s[0] == '\0')
        return 0;
    return 1 + lunghezza(s + 1);
}

void stampa_al_contrario(const char s[], int i)
{
    if (s[i] == '\0')
        return;
    stampa_al_contrario(s, i + 1);
    putchar(s[i]);
}

int palindroma(const char s[], int i, int j)
{
    if (i >= j)
        return 1;
    if (s[i] != s[j])
        return 0;
    return palindroma(s, i + 1, j - 1);
}

void inverti(int a[], int i, int j)
{
    int t;

    if (i >= j)
        return;
    t = a[i];
    a[i] = a[j];
    a[j] = t;
    inverti(a, i + 1, j - 1);
}

int massimo(const int a[], int n)
{
    int m;

    if (n == 1)
        return a[0];
    m = massimo(a, n - 1);
    return a[n - 1] > m ? a[n - 1] : m;
}

int main(void)
{
    int v[4] = {2, 7, 5, 4};

    printf("%d\n", lunghezza("ciao"));
    stampa_al_contrario("ciao", 0);
    putchar('\n');
    printf("%d %d\n", palindroma("radar", 0, 4), palindroma("rotore", 0, 5));
    inverti(v, 0, 3);
    printf("%d %d %d %d\n", v[0], v[1], v[2], v[3]);
    printf("%d\n", massimo(v, 4));
    return 0;
}

Output (verificato):

4
oaic
1 0
4 5 7 2
7

Gli array si passano per indirizzo (Funzioni): tutte le chiamate di inverti lavorano sullo stesso array, ed è per questo che gli scambi fatti in profondità si vedono nel main.

3Metodo

Scrivere una funzione ricorsiva.

  1. Trova la dimensione che scende: un numero (nn), una lunghezza, una distanza fra due indici.
  2. Scrivi il caso base: l’istanza più piccola, risolta senza chiamate. Controlla che ogni valore iniziale ci arrivi (con n - 2 da un numero dispari si salta lo 0: serve n <= 0).
  3. Scrivi il caso induttivo con i tre passi della slide 57: istanza più piccola, fiducia nel risultato, composizione.
  4. Prova a mano sul caso base e su quello subito sopra.

Tracciare “cosa stampa”.

  1. Se c’è una sola chiamata ricorsiva per record: scrivi la colonna delle chiamate con i valori dei parametri fino al caso base (andata), poi risali (ritorno). Le stampe prima della chiamata escono scendendo, quelle dopo risalendo.
  2. Se ce ne sono due o più: disegna l’albero delle chiamate, con le stampe come foglie nel punto in cui avvengono, e leggilo da sinistra a destra.
  3. Ogni record ha i suoi parametri e le sue variabili locali: dopo il ritorno di una chiamata il valore di n è quello di prima. Fanno eccezione le variabili globali, static e quelle raggiunte tramite puntatore, che sono una sola cella condivisa da tutti i record.
  4. Per i valori restituiti scrivi l’espressione in sospeso (3 * ?) e completala al ritorno.

Contare chiamate e operazioni. Scrivi la ricorrenza C(n)=1+∑C(figli)C(n) = 1 + \sum C(\text{figli}), calcola i primi valori dal basso, e controlla sull’albero disegnato.

4Esempi svolti a lezione

4.1Le Torri di Hanoi

(slide 16-36) Tre pioli A, B, C; i dischi stanno su A, dal più grande in basso al più piccolo in cima. L’obiettivo del gioco è mettere tutti i dischi sul piolo C, sempre in ordine, seguendo tre regole (slide 19-20):

  1. si può spostare un solo disco alla volta;
  2. si può spostare solo un disco che non ha altri dischi sopra;
  3. non si può mai mettere un disco più grande su uno più piccolo.

Le slide 21-36 mostrano la soluzione con 4 dischi, mossa per mossa: 15 mosse (mossa 1 da A a B, mossa 2 da A a C, mossa 3 da B a C, …).

Formulazione induttiva (slide 39-45). “Come si descrive induttivamente la soluzione del problema con nn dischi?”

Il passo 1 è legale perché il disco grande, rimasto sotto in A, non dà fastidio: tutti i dischi spostati sono più piccoli. Nel passo 1 il piolo C fa da appoggio, nel passo 3 lo fa A.

Il commento del prof (slide 46): il caso base è semplice da riconoscere e risolvere; la ricorsione riguarda due sottoproblemi con n−1n-1 dischi, semplici da estrarre; le soluzioni parziali si compongono: le mosse del primo sottoproblema, una mossa singola, le mosse del secondo.

Il codice (slide 47-53). Nelle slide i commenti dicono “Muovi n-1 dischi da da_piolo a piolo_appoggio”, “Muovi il disco rimasto da da_piolo a a_piolo”, “Muovi n-1 dischi da piolo_appoggio to a a_piolo”. Il main della slide 53 chiama hanoi('A', 'C', 'B', n): A è il piolo di partenza, C quello di arrivo, B l’appoggio. Qui con int main(void) e il controllo di scanf:

#include <stdio.h>

void hanoi(char da_piolo, char a_piolo, char piolo_appoggio, int dischi)
{
    if (dischi == 1) {
        printf("Muovi disco 1 da %c a %c\n", da_piolo, a_piolo);
        return;
    }
    hanoi(da_piolo, piolo_appoggio, a_piolo, dischi - 1);
    printf("Muovi %d da %c a %c\n", dischi, da_piolo, a_piolo);
    hanoi(piolo_appoggio, a_piolo, da_piolo, dischi - 1);
}

int main(void)
{
    int n;

    printf("Inserisci il numero di dischi: ");
    if (scanf("%d", &n) != 1 || n < 1) {
        return 1;
    }
    printf("\nSequenza di passi:\n");
    hanoi('A', 'C', 'B', n);
    return 0;
}

Output con input 3 (verificato):

Inserisci il numero di dischi: 
Sequenza di passi:
Muovi disco 1 da A a C
Muovi 2 da A a B
Muovi disco 1 da C a B
Muovi 3 da A a C
Muovi disco 1 da B a A
Muovi 2 da B a C
Muovi disco 1 da A a C

L’albero delle chiamate, con h(n, da, a, appoggio). I figli di ogni nodo sono: prima chiamata, mossa, seconda chiamata.

h(3,A,C,B)
├── h(2,A,B,C)
│   ├── h(1,A,C,B)          mossa 1: disco 1 A → C
│   ├── disco 2 A → B       mossa 2
│   └── h(1,C,B,A)          mossa 3: disco 1 C → B
├── disco 3 A → C           mossa 4
└── h(2,B,C,A)
    ├── h(1,B,A,C)          mossa 5: disco 1 B → A
    ├── disco 2 B → C       mossa 6
    └── h(1,A,C,B)          mossa 7: disco 1 A → C

Come si costruiscono i parametri dei figli: in h(2,A,B,C) la prima chiamata è hanoi(da_piolo, piolo_appoggio, a_piolo, 1), cioè h(1, A, C, B); la seconda è hanoi(piolo_appoggio, a_piolo, da_piolo, 1), cioè h(1, C, B, A). I numeri dei dischi mossi, letti in ordine, sono 1 2 1 3 1 2 1: lo stesso righello(3) di sopra.

Quante mosse (slide 54-55). Sia M(n)M(n) il numero di mosse con nn dischi.

M(1) = 1
M(2) = 2·1 + 1 = 3
M(3) = 2·3 + 1 = 7
M(4) = 2·7 + 1 = 15        le 15 mosse delle slide 22-36

Per induzione M(n)=2n−1M(n) = 2^n - 1: vale per n=1n = 1 (2−1=12 - 1 = 1), e se M(n−1)=2n−1−1M(n-1) = 2^{n-1} - 1 allora M(n)=2(2n−1−1)+1=2n−1M(n) = 2(2^{n-1} - 1) + 1 = 2^n - 1. Con il programma: input 4 stampa 15 righe “Muovi” (verificato). Il prof aggiunge che questa è la soluzione più breve, e il grafico della slide 55 mostra y=2n−1y = 2^n - 1: crescita esponenziale, ogni disco in più raddoppia le mosse.

4.2Sommatoria su array

(slide 63-67) La sommatoria s(n)=∑i=1nais(n) = \sum_{i=1}^{n} a_i. La soluzione non ricorsiva usa un’istruzione iterativa (un for). La formulazione ricorsiva:

s(n)=∑i=1nai=an+s(n−1)s(n) = \sum_{i=1}^{n} a_i = a_n + s(n-1)

con caso base s(0)=0s(0) = 0 (la somma di nessun numero). L’esercizio della slide 66: calcolarla in modo ricorsivo, con i coefficienti in un array, in una funzione Sommatoria chiamata dal main. La soluzione della slide 67:

#include <stdio.h>

int Sommatoria(int arr[], int n)
{
    if (n <= 0)
        return 0;
    return arr[n - 1] + Sommatoria(arr, n - 1);
}

int main(void)
{
    int arr[5] = {1, 2, 3, 4, 5};

    printf("Sommatoria = %d\n", Sommatoria(arr, 5));
    return 0;
}

ana_n della formula è arr[n - 1], perché l’array parte da 0. Il caso base è n <= 0 e non n == 0: protegge anche da un n negativo passato per errore.

chiamatanin sospesoritorna
Sommatoria(arr, 5)55 + ?5 + 10 = 15
Sommatoria(arr, 4)44 + ?4 + 6 = 10
Sommatoria(arr, 3)33 + ?3 + 3 = 6
Sommatoria(arr, 2)22 + ?2 + 1 = 3
Sommatoria(arr, 1)11 + ?1 + 0 = 1
Sommatoria(arr, 0)0caso base0

Output: Sommatoria = 15 (verificato). Le somme si fanno al ritorno, dall’ultima riga alla prima: 1, poi 3, 6, 10, 15.

La nuvoletta della slide 67 chiede di sostituire l’inizializzazione con una sequenza di lunghezza arbitraria, definita da un parametro letto in ingresso. Senza VLA, con un massimo fisso:

#include <stdio.h>

#define MAX 100

int Sommatoria(int arr[], int n)
{
    if (n <= 0)
        return 0;
    return arr[n - 1] + Sommatoria(arr, n - 1);
}

int main(void)
{
    int arr[MAX];
    int n;

    printf("Quanti numeri? ");
    if (scanf("%d", &n) != 1 || n < 0 || n > MAX) {
        return 1;
    }
    for (int i = 0; i < n; i++) {
        if (scanf("%d", &arr[i]) != 1) {
            return 1;
        }
    }
    printf("Sommatoria = %d\n", Sommatoria(arr, n));
    return 0;
}

Con input 4 10 -3 7 1 stampa Quanti numeri? Sommatoria = 15 (verificato: 10 - 3 + 7 + 1 = 15).

4.3Fattoriale

(slide 68-75) La soluzione non ricorsiva (slide 69) moltiplica in un for da 2 a nn. La ricorsiva (slide 70) copia la definizione 0!=10! = 1, n!=n⋅(n−1)!n! = n \cdot (n-1)!:

#include <stdio.h>

int Fatt(int n)
{
    int ris;
    ris = 1;
    for (int i = 2; i <= n; i++)
        ris = ris * i;
    return ris;
}

int FattRic(int n)
{
    if (n == 0)
        return 1;
    else
        return n * FattRic(n - 1);
}

int main(void)
{
    for (int n = 0; n <= 5; n++)
        printf("%d! = %d %d\n", n, Fatt(n), FattRic(n));
    printf("13! = %d\n", FattRic(13));
    return 0;
}

Output (verificato):

0! = 1 1
1! = 1 1
2! = 2 2
3! = 6 6
4! = 24 24
5! = 120 120
13! = 1932053504

L’ultima riga è sbagliata: 13!=6 227 020 80013! = 6\,227\,020\,800 non sta in un int a 32 bit (massimo 2 147 483 6472\,147\,483\,647), e il risultato stampato è quello che resta dopo l’overflow. Per il C l’overflow di un int con segno è comportamento indefinito; con gcc qui si vede 13!13! modulo 2322^{32}. Il fattoriale in int è giusto solo fino a 12!=479 001 60012! = 479\,001\,600.

Il programma completo della slide 71 ha una differenza: il caso base è if(n==1) return 1;, e il main stampa solo if(n>0).

#include <stdio.h>

int FattRic(int n)
{
    if (n == 1) return 1;
    else return n * FattRic(n - 1);
}

int main(void)
{
    int n;

    printf("Inserisci n: \n");
    if (scanf("%d", &n) != 1) {
        return 1;
    }
    if (n > 0) printf("%d!= %d\n", n, FattRic(n));
    return 0;
}

Con input 5 stampa 5!= 120; con input 0 non stampa il risultato (verificato). Il controllo nel main serve: con il caso base n <mark> 1, FattRic(0) chiamerebbe FattRic(-1), FattRic(-2), … senza mai arrivare a 1, fino a esaurire lo stack. Con il caso base n </mark> 0 della slide 70 invece anche 0!=10! = 1 funziona. Nella slide manca anche il \n dopo il risultato; qui è aggiunto.

Le domande delle slide 73-75 e 83 (moltiplicazioni, confronti, memoria) sono risolte sopra, in Ricorsione contro iterazione. Lo stack della slide 82 è nella figura de La pila chiamata per chiamata.

4.4Lista inversa

(slide 72) La lista inversa L−1L^{-1} di L={a1,…,an}L = \{a_1, \dots, a_n\}:

L’esempio della slide, un passo per riga:

{2,7,5,4}^-1 = {4, {2,7,5}^-1}        tolgo l'ultimo (4) e lo metto davanti
             = {4,5, {2,7}^-1}        stessa regola su {2,7,5}
             = {4,5,7, {2}^-1}        stessa regola su {2,7}
             = {4,5,7,2}              caso base: un elemento solo

La slide non ha codice. Tradotta in C come stampa: si stampa l’ultimo elemento, poi la lista inversa dei primi n−1n-1.

#include <stdio.h>

void stampa_inversa(const int a[], int n)
{
    if (n == 1) {
        printf("%d\n", a[0]);
        return;
    }
    printf("%d,", a[n - 1]);
    stampa_inversa(a, n - 1);
}

int main(void)
{
    int L[4] = {2, 7, 5, 4};

    stampa_inversa(L, 4);
    return 0;
}

Output: 4,5,7,2 (verificato). Le chiamate sono con nn = 4, 3, 2, 1 e stampano a[3], a[2], a[1], poi a[0] nel caso base. La versione che inverte l’array in memoria è inverti, in Ricorsione su array e stringhe.

4.5MCD ricorsivo

(slide 76-79) L’esercizio parte dalla soluzione non ricorsiva con le sottrazioni (Euclide, come in Ciclo while ed esempi):

int mcd(int x, int y){
   while (x!=y)
     if (x>y) x-=y;
     else y -=x;
   return x;
}

e chiede la ricorsiva. Soluzione 1 (slide 77), le sottrazioni: il ciclo diventa una chiamata con i nuovi valori, e la condizione di uscita x == y diventa il caso base.

int mcdRicorsiva(int x,int y){
  if(x>y)
    return mcdRicorsiva(x-y,y);
      else if(x<y)
        return mcdRicorsiva(y-x,x);
            else return x;
}

Soluzione 2 (slide 79), con il resto: MCD(x,0)=xMCD(x, 0) = x, e MCD(x,y)=MCD(y,x%y)MCD(x, y) = MCD(y, x \% y).

int mcdRicorsiva(int x,int y){
   return y==0 ? x :
          mcdRicorsiva(y,x%y);
}

Nella soluzione della slide 78 le due versioni stanno nello stesso file, con la 2 commentata, e il main legge a e b e stampa MCD(%d,%d)=%d. Qui le due versioni con una printf a ogni chiamata, per vedere i parametri:

#include <stdio.h>

int mcd1(int x, int y)
{
    printf("mcd1(%d,%d)\n", x, y);
    if (x > y)
        return mcd1(x - y, y);
    else if (x < y)
        return mcd1(y - x, x);
    else
        return x;
}

int mcd2(int x, int y)
{
    printf("mcd2(%d,%d)\n", x, y);
    return y == 0 ? x : mcd2(y, x % y);
}

int main(void)
{
    printf("= %d\n", mcd1(12, 18));
    printf("= %d\n", mcd2(12, 18));
    printf("= %d\n", mcd2(18, 12));
    return 0;
}

Output (verificato):

mcd1(12,18)
mcd1(6,12)
mcd1(6,6)
= 6
mcd2(12,18)
mcd2(18,12)
mcd2(12,6)
mcd2(6,0)
= 6
mcd2(18,12)
mcd2(12,6)
mcd2(6,0)
= 6
chiamataxyregolaprossima
mcd11218x<yx < y: (y-x, x)(6, 12)
mcd1612x<yx < y: (y-x, x)(6, 6)
mcd166x=yx = y: caso baseritorna 6
mcd2121812 % 18 = 12(18, 12)
mcd2181218 % 12 = 6(12, 6)
mcd212612 % 6 = 0(6, 0)
mcd260y=0y = 0: caso baseritorna 6

Se x<yx < y la soluzione 2 spende una chiamata per scambiarli: 12 % 18 vale 12, e la chiamata dopo è mcd2(18, 12). Dopo, le due righe di output coincidono con quelle di mcd2(18, 12).

In entrambe le versioni la chiamata ricorsiva è l’ultima cosa che la funzione fa (il suo risultato si restituisce così com’è, senza calcoli in sospeso). Al ritorno non c’è niente da fare: il 6 risale invariato.

4.6Passaggio per indirizzo

(slide 84-85) “Qual è il risultato dell’esecuzione di questa funzione?”

#include <stdio.h>

void incrementa(int *n, int m)
{
    if (m != 0) {
        *n = *n + 1;
        incrementa(n, m - 1);
    }
}

int main(void)
{
    int x = 2;
    int y = 3;

    incrementa(&x, y);
    printf("x=%d y=%d\n", x, y);
    return 0;
}

Somma m a *n, un’unità per chiamata. Nella slide 85 il prof parte da x=2x = 2 e y=3y = 3:

attivazionem (copia propria)n*n dopo *n = *n + 1
prima3&xx = 3
seconda2&xx = 4
terza1&xx = 5
quarta0&xm != 0 falso, niente

Output: x=5 y=3 (verificato). Nel disegno della slide il riquadro di x nell’area dati della funzione chiamante ha i valori 2, 3, 4, 5 cancellati uno dopo l’altro, e da ogni record parte una freccia verso quello stesso riquadro. Il punto: m è passato per valore, quindi ogni attivazione ha la sua copia (3, 2, 1, 0) e y nel main resta 3. n contiene un indirizzo, lo stesso in tutte le attivazioni: tutte modificano la stessa x.

4.7Fibonacci

(slide 92-104) “Riconoscete questa successione?” 0, 1, 1, 2, 3, 5, 8, 13, … Sono i numeri di Fibonacci:

L’esempio della slide 94, un passo per riga:

f2 = f1 + f0 = 1 + 0 = 1
f3 = f2 + f1 = 1 + 1 = 2
f4 = f3 + f2 = 2 + 1 = 3

Qui i casi base sono due: il caso induttivo usa i due valori precedenti, quindi servono f0f_0 e f1f_1 per partire. La soluzione delle slide 96-97, con int main(void) e il controllo di scanf (la slide dichiara anche un int ris; che non usa):

#include <stdio.h>

int Fibo(int n)
{
    if (!n)
        return 0;
    else if (n == 1)
        return 1;
    else
        return Fibo(n - 1) + Fibo(n - 2);
}

int main(void)
{
    int n;

    printf("Inserisci n: \n");
    if (scanf("%d", &n) != 1) {
        return 1;
    }
    for (int i = 0; i <= n; i++)
        printf("Fibonacci(%d)=%d\n", i, Fibo(i));
    return 0;
}

Output con input 6 (verificato):

Inserisci n: 
Fibonacci(0)=0
Fibonacci(1)=1
Fibonacci(2)=1
Fibonacci(3)=2
Fibonacci(4)=3
Fibonacci(5)=5
Fibonacci(6)=8

if (!n) vuol dire if (n == 0): !n vale 1 solo quando n è 0 (Istruzioni condizionali).

Tempo di esecuzione (slide 98-100). “Il tempo di esecuzione di un algoritmo è funzione del numero di istruzioni (confronti, operazioni aritmetiche, …) necessarie per portarlo a termine.” Per F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2) cresce esponenzialmente: la slide 99 mostra il grafico dei secondi in funzione di nn, piatto fino a 40 e poi verticale, e dice che TFibonacci(n)T_{Fibonacci}(n) si comporta come ana^n.

Albero di esecuzione (slide 100-104). Il prof disegna gli alberi per nn = 3, 4, 5, 6 e colora in verde i termini che vengono ricalcolati. La figura qui è quella di F(5)F(5) con tutte le chiamate che il codice fa davvero, numerate nell’ordine in cui avvengono:

Gli alberi delle slide si fermano a F(2)F(2) e F(1)F(1), come se F(2)F(2) fosse un caso base. Con il codice della slide 96 invece F(2)F(2) chiama F(1)F(1) e F(0)F(0): il conteggio vero delle chiamate per F(5)F(5) è 15, non i 9 nodi del disegno. La slide 100, poi, disegna i figli di F(3)F(3) come F(1)F(1) e F(2)F(2), in ordine scambiato rispetto al codice, che chiama prima Fibo(n - 1).

“Quanti sono i nodi dell’albero per F(n)F(n)?” (slide 104). Contando tutte le chiamate: C(n)=1+C(n−1)+C(n−2)C(n) = 1 + C(n-1) + C(n-2) con C(0)=C(1)=1C(0) = C(1) = 1, quindi C(n)=2F(n+1)−1C(n) = 2F(n+1) - 1:

nn234561030
F(n)F(n)1235855832 040
chiamate35915251772 692 537

Controllo su n=6n = 6: F(7)=13F(7) = 13, 2⋅13−1=252 \cdot 13 - 1 = 25 (contate con uno script). Le chiamate crescono come i numeri di Fibonacci, cioè di un fattore circa 1,62 per ogni nn in più: per questo il grafico della slide 99 esplode.

Overflow: Fibo restituisce un int. F(46)=1 836 311 903F(46) = 1\,836\,311\,903 ci sta, F(47)=2 971 215 073F(47) = 2\,971\,215\,073 no; con la versione memoizzata qui sotto l’input 47 stampa Fibonacci(47)=-1323752223 (verificato).

Memoization (slide 105-106). Nel codice della slide 106 il commento dice che la memoization abbassa la complessità di Fibo fino a renderla lineare. Sol[n] vale 0 finché F(n)F(n) non è stato calcolato; poi contiene il valore, e le chiamate successive lo restituiscono subito.

#include <stdio.h>

int Fibo(int n, int Sol[])
{
    if (!n)
        return 0;
    else if (n == 1)
        return 1;
    else if (Sol[n])
        return Sol[n];
    else
        return Sol[n] = Fibo(n - 1, Sol) + Fibo(n - 2, Sol);
}

int main(void)
{
    int n;
    int FiboS[100];

    for (n = 0; n < 100; n++)
        FiboS[n] = 0;
    printf("Inserisci n: \n");
    if (scanf("%d", &n) != 1 || n < 0 || n > 99) {
        return 1;
    }
    printf("Fibonacci(%d)=%d\n", n, Fibo(n, FiboS));
    return 0;
}

Output con input 46: Fibonacci(46)=1836311903 (verificato). Due correzioni rispetto alla slide: il ciclo di azzeramento della slide va fino a n<99 e lascia FiboS[99] non inizializzato (qui n < 100), e manca il controllo che n stia fra 0 e 99 (con n più grande si scrive fuori dall’array).

return Sol[n] = ... assegna e restituisce in un colpo: l’assegnazione è un’espressione e vale il valore assegnato (Il Linguaggio C). Il guadagno: nell’albero di F(5)F(5) il sottoalbero di destra F(3)F(3) (chiamate 11-15) diventa una sola chiamata che trova Sol[3] già pieno. In generale ogni F(k)F(k) si calcola una volta, e le chiamate sono 2n−12n - 1: 9 per n=5n = 5 invece di 15, 91 per n=46n = 46 invece di quasi 6 miliardi (contate con uno script).

4.8La scala con passi da 1, 2 o 3, ricorsiva

(slide 107-116) “Un bambino sale le scale con passi che coprono 1, 2 o 3 gradini alla volta. Formulare un algoritmo ricorsivo che, data la lunghezza della scala N, calcoli il numero di modi possibili di salire le scale.” È il problema risolto con il ciclo in Ciclo while ed esempi › La scala a passi da 1, 2 o 3.

Soluzione (slide 109): l’approccio è top-down. All’ultimo passo il bambino può aver fatto un passo singolo dalla posizione n−1n-1, doppio da n−2n-2, triplo da n−3n-3. Il numero totale di modi è la somma dei modi di raggiungere n−1n-1, n−2n-2 e n−3n-3. Nella nota sul while si ragiona sul primo passo, qui sull’ultimo: la ricorrenza che esce è la stessa.

int CountWays(int n ){
if (n<0) return 0;
    else if (n == 0) return 1;
    else
          return CountWays(n-1) +
                 CountWays(n-2) +
                 CountWays(n-3);
}

I due casi base hanno un significato:

Non servono casi base per 1 e 2: CountWays(1) = CountWays(0) + CountWays(-1) + CountWays(-2) = 1 + 0 + 0 = 1.

Rundown per N=3N = 3 (slide 111-114), un passo per riga, abbreviando CountWays in CW:

CW(3) = CW(2) + CW(1) + CW(0)                              definizione con n = 3
      = [CW(1) + CW(0) + CW(-1)] + [CW(0) + CW(-1) + CW(-2)] + 1
                                                           espando CW(2) e CW(1); CW(0) = 1
      = [1 + 1 + 0] + [1 + 0 + 0] + 1                      CW(1) = 1 (sopra), CW(0) = 1, negativi 0
      = 4

Nella slide 114 il prof scrive CW(1) = 1 dentro la prima parentesi senza espanderlo. Il valore è giusto, ma il programma la chiamata CW(1) la fa, con le sue tre chiamate figlie. In tutto CW(3)CW(3) fa 13 chiamate:

CW(3)
├── CW(2)
│   ├── CW(1)
│   │   ├── CW(0) → 1
│   │   ├── CW(-1) → 0
│   │   └── CW(-2) → 0          CW(1) = 1
│   ├── CW(0) → 1
│   └── CW(-1) → 0              CW(2) = 2
├── CW(1)
│   ├── CW(0) → 1
│   ├── CW(-1) → 0
│   └── CW(-2) → 0              CW(1) = 1
└── CW(0) → 1                   CW(3) = 2 + 1 + 1 = 4

Il programma completo della slide 115 legge la lunghezza in un unsigned int e stampa “Il numero di modi di salire la scala è: %d”. I valori per nn da 0 a 10, stampati da un ciclo: 1 1 2 4 7 13 24 44 81 149 274 (verificato).

Le domande delle slide 115-116. “Per quali N (lunghezza della scala) è corretta l’implementazione della funzione? 1, 10, 37, 100?” e “Confrontate il numero di operazioni del problema per la soluzione iterativa e ricorsiva. Ci sono problemi di overflow? Per quali delle soluzioni?”

4.9I cammini del robot

(slide 117-122) “Un robot si trova nell’angolo in alto a sinistra di una griglia m×nm \times n. Può muoversi solo verso destra o verso il basso. Quanti percorsi distinti portano all’angolo in basso a destra?” Nella slide 117 il prof disegna a mano il robot, le frecce DESTRA e GIÙ, un percorso tratteggiato e l’ARRIVO in basso a destra.

Il ragionamento è quello della scala: all’arrivo si giunge o dalla cella sopra o da quella a sinistra, quindi i cammini sono la somma dei cammini verso quelle due celle. Se mm o nn vale 0 si è sul bordo, e c’è un solo cammino (sempre dritto). La soluzione della slide 118:

int Cammini(int m, int n){
    if (m == 0||n == 0) //per m=0 o n=0
        return 1 ;      //un solo cammino
    return Cammini(m - 1, n) +
           Cammini(m, n - 1);
}

Qui mm e nn sono quanti passi mancano verso il basso e verso destra, non il numero di celle. Esempio con m=n=2m = n = 2, un passo per riga:

C(2,2) = C(1,2) + C(2,1)
C(1,2) = C(0,2) + C(1,1) = 1 + C(1,1)
C(1,1) = C(0,1) + C(1,0) = 1 + 1 = 2
C(1,2) = 1 + 2 = 3          e per simmetria C(2,1) = 3
C(2,2) = 3 + 3 = 6

Controllo: con 2 passi giù (G) e 2 a destra (D) le sequenze sono DDGG, DGDG, DGGD, GDDG, GDGD, GGDD, cioè 6.

“Questo algoritmo, sebbene corretto, può causare problemi o errori durante l’esecuzione. Quale meccanismo ci può aiutare ad evitare questi problemi? La memoization.” Il problema è lo stesso di Fibonacci: C(1,1) si calcola sia dentro C(1,2) sia dentro C(2,1). Per m=n=9m = n = 9 la versione senza memo fa 97 239 chiamate (contate con uno script), per un risultato di 48 620.

Con memoization (slide 119-122). La matrice memo parte tutta a 0; memo[m][n] diverso da 0 vuol dire “già calcolato”.

#include <stdio.h>

int Cammini(int m, int n, int cols, int memo[][cols])
{
    if (m == 0 || n == 0)
        return 1;
    if (memo[m][n])
        return memo[m][n];
    memo[m][n] = Cammini(m - 1, n, cols, memo) + Cammini(m, n - 1, cols, memo);
    return memo[m][n];
}

int main(void)
{
    int i;
    int j;
    int Paths[10][10];

    for (i = 0; i < 10; i++)
        for (j = 0; j < 10; j++)
            Paths[i][j] = 0;
    printf("Numero di Cammini del Robot=%d\n", Cammini(9, 9, 10, Paths));
    printf("2x2: %d\n", Cammini(2, 2, 10, Paths));
    return 0;
}

Output (verificato):

Numero di Cammini del Robot=48620
2x2: 6

La seconda riga è aggiunta qui per controllare l’esempio a mano. La seconda chiamata trova Paths[2][2] già pieno dalla prima e restituisce subito 6. Il parametro int memo[][cols] passa una matrice di cui si conosce il numero di colonne solo a tempo di esecuzione (Matrici e array multidimensionali): cols deve venire prima di memo nella lista dei parametri. Il risultato si controlla con il calcolo combinatorio: 18 passi di cui 9 verso il basso, (189)=48 620\binom{18}{9} = 48\,620.

5Esercizi tipo esame

In una pagina a parte, dal più facile al livello del 30: Ricorsione (esercizi).

6Errori tipici

7Domande