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:
- scatole cinesi: “sono stati fatti investimenti nella ditta XYZ che è controllata da xyz che è controllata da abc che è controllata da cba…”. Si scrive
XYZ = ControllataDa(ControllataDa(ControllataDa(cba)))(slide 5); - albero genealogico: se B è il padre di C e A è il padre di B, allora
A = PADRE(B) = PADRE(PADRE(C))(slide 6); - immagini: ricorsione in natura (alberi veri, in cui ogni ramo si divide in rami più piccoli fatti allo stesso modo), un albero frattale generato al computer, il fiocco di neve di Von Koch (un triangolo in cui ogni lato si sostituisce con quattro lati lunghi un terzo, con una punta in mezzo, e si ripete su ciascuno), l’H-tree (slide 7-15).
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 . 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:
- caso base: “la classe di istanze sufficientemente piccole (quindi sufficientemente semplici) da poter essere risolte in maniera diretta (senza ricorsione)”;
- caso induttivo: “la classe delle istanze restanti che, pur non essendo direttamente risolvibili, si prestano ad essere risolte tramite un determinato algoritmo”.
Prima di tutto bisogna trovare “la dimensione lungo la quale muoversi” (slide 56): il numero di dischi in Hanoi, 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).
- Dall’istanza di dimensione si ricavano una o più istanze dello stesso problema di dimensione più piccola (, , …, 1).
- Si suppone di saper già risolvere quelle istanze più piccole.
- 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 ” implica “giusto per ”, allora è giusto per ogni . 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 : il valore del parametro attuale 3 viene copiato nel parametro formale n, inizia l’esecuzione, arriva la nuova chiamata , 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.
| passo | evento | pila (fondo → cima) | cosa resta in sospeso |
|---|---|---|---|
| 1 | main chiama FattRic(3) | main, n=3 | |
| 2 | 3 == 0 falso, serve FattRic(2) | main, n=3, n=2 | 3 * ? |
| 3 | 2 == 0 falso, serve FattRic(1) | main, n=3, n=2, n=1 | 3 * ?, 2 * ? |
| 4 | 1 == 0 falso, serve FattRic(0) | main, n=3, n=2, n=1, n=0 | 3 * ?, 2 * ?, 1 * ? |
| 5 | 0 == 0 vero: caso base, ritorna 1 | main, n=3, n=2, n=1 | 3 * ?, 2 * ?, 1 * 1 |
| 6 | n=1 calcola 1 * 1, ritorna 1 | main, n=3, n=2 | 3 * ?, 2 * 1 |
| 7 | n=2 calcola 2 * 1, ritorna 2 | main, n=3 | 3 * 2 |
| 8 | n=3 calcola 3 * 2, ritorna 6 | main |
Due fasi da tenere separate:
- andata (passi 1-4): si scende fino al caso base, e ogni chiamata lascia una moltiplicazione in sospeso, perché non conosce ancora il fattore di destra;
- ritorno (passi 5-8): i record si chiudono dall’alto, e le moltiplicazioni in sospeso si fanno in ordine inverso rispetto a come erano state lasciate.
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 record di FattRic contemporaneamente (da n fino a 0). La versione col for ne ha sempre uno solo. Questo è il “per 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à.
| istruzione | n del record in cima | stampa |
|---|---|---|
entrambe(3): 3 == 0 falso | 3 | |
printf prima della chiamata | 3 | 3 |
. entrambe(2): 2 == 0 falso | 2 | |
. printf prima | 2 | 2 |
. . entrambe(1): falso | 1 | |
. . printf prima | 1 | 1 |
… entrambe(0): caso base | 0 | | |
. . printf dopo, entrambe(1) finisce | 1 | 1 |
. printf dopo, entrambe(2) finisce | 2 | 2 |
printf dopo, entrambe(3) finisce | 3 | 3 |
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;
}
| chiamata | n | n % 10 | n >= 10 |
|---|---|---|---|
| 1 | 4271 | 1 | vero |
| 2 | 427 | 7 | vero |
| 3 | 42 | 2 | vero |
| 4 | 4 | 4 | falso: 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 sono 1 (la chiamata stessa) più le chiamate fatte dai figli. Il caso base conta 1.
| funzione | ricorrenza delle chiamate | valori | formula |
|---|---|---|---|
FattRic(n) | , | ||
righello(n), Hanoi | , | ||
Fibo(n) | , | , | |
CountWays(n) | se , | , | esponenziale |
Esempio 1, FattRic(3): chiamate con = 3, 2, 1, 0, quindi 4. Lineare: ogni chiamata ne fa al massimo una.
Esempio 2, Fibo(5): , , , . Controllo con la formula: , . 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 : 289 per (Ciclo while ed esempi › La scala a passi da 1, 2 o 3). La versione del prof (slide 110) ha come unico caso base , quindi scende di due livelli in più: per fa 979 chiamate (contate con uno script). Le due successioni sono le stesse spostate di 2: , e infatti .
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 (, ) 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 slide | Fatt (con il for) | FattRic |
|---|---|---|
| moltiplicazioni per | 0 (il for parte da i = 2 e non entra) | 1 (1 * FattRic(0)) |
| moltiplicazioni per | 2 (i = 2, 3) | 3 (n = 3, 2, 1) |
| confronti per | 3 (i <= n con i = 2, 3, 4) | 4 (n == 0 con n = 3, 2, 1, 0) |
| memoria per | un 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:
- più chiamate sugli stessi sottoproblemi: Fibonacci e la scala ricalcolano gli stessi valori un numero esponenziale di volte (sotto, Esempi svolti);
- pila troppo profonda: ogni livello occupa memoria nello stack, e con migliaia di livelli lo stack finisce (crash, “stack overflow”). Il “Ricapitolando” della slide 91 lo dice: “attenzione all’impatto delle chiamate ricorsive sui requisiti di occupazione memoria dello stack ed i tempi di esecuzione”.
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 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 elementi usando lo stesso problema su 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
lunghezza("ciao"):s + 1è la stringa senza il primo carattere (aritmetica dei puntatori, Puntatori). Le chiamate vedono"ciao","iao","ao","o",""; si torna con 0, 1, 2, 3, 4.stampa_al_contrario: laputcharè dopo la chiamata, quindi le lettere escono al ritorno, dall’ultima alla prima.palindroma("radar", 0, 4): confrontar/r(0, 4),a/a(1, 3), poii = j = 2e si ferma con 1. Per"rotore"giàr/esono diversi: 0.inverti(v, 0, 3): scambiav[0]ev[3]({4, 7, 5, 2}), poiv[1]ev[2]({4, 5, 7, 2}), poii = 2 > j = 1e si ferma.massimo(v, 4)sull’array già invertito {4, 5, 7, 2}:massimo(v, 1)= 4, poi max(5, 4) = 5, max(7, 5) = 7, max(2, 7) = 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.
- Trova la dimensione che scende: un numero (), una lunghezza, una distanza fra due indici.
- Scrivi il caso base: l’istanza più piccola, risolta senza chiamate. Controlla che ogni valore iniziale ci arrivi (con
n - 2da un numero dispari si salta lo 0: serven <= 0). - Scrivi il caso induttivo con i tre passi della slide 57: istanza più piccola, fiducia nel risultato, composizione.
- Prova a mano sul caso base e su quello subito sopra.
Tracciare “cosa stampa”.
- 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.
- 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.
- 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,statice quelle raggiunte tramite puntatore, che sono una sola cella condivisa da tutti i record. - Per i valori restituiti scrivi l’espressione in sospeso (
3 * ?) e completala al ritorno.
Contare chiamate e operazioni. Scrivi la ricorrenza , 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):
- si può spostare un solo disco alla volta;
- si può spostare solo un disco che non ha altri dischi sopra;
- 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 dischi?”
- Caso base: se ho un solo disco da spostare da A a C, lo so spostare.
- Caso induttivo (suppongo di saper risolvere problemi con dischi):
- metto gli dischi più piccoli da A in B;
- metto un disco (il più grande) da A in C;
- metto gli dischi più piccoli da B in C.
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 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 il numero di mosse con dischi.
- (caso base, una mossa).
- (due sottoproblemi e la mossa del disco grande).
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 : vale per (), e se allora . 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 : crescita esponenziale, ogni disco in più raddoppia le mosse.
4.2Sommatoria su array
(slide 63-67) La sommatoria . La soluzione non ricorsiva usa un’istruzione iterativa (un for). La formulazione ricorsiva:
con caso base (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;
}
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.
| chiamata | n | in sospeso | ritorna |
|---|---|---|---|
Sommatoria(arr, 5) | 5 | 5 + ? | 5 + 10 = 15 |
Sommatoria(arr, 4) | 4 | 4 + ? | 4 + 6 = 10 |
Sommatoria(arr, 3) | 3 | 3 + ? | 3 + 3 = 6 |
Sommatoria(arr, 2) | 2 | 2 + ? | 2 + 1 = 3 |
Sommatoria(arr, 1) | 1 | 1 + ? | 1 + 0 = 1 |
Sommatoria(arr, 0) | 0 | caso base | 0 |
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 . La ricorsiva (slide 70) copia la definizione , :
#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: non sta in un int a 32 bit (massimo ), 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 modulo . Il fattoriale in int è giusto solo fino a .
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 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 di :
- se , ;
- altrimenti , dove è la lista ottenuta da cancellando l’ultimo elemento .
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 .
#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 = 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: , e .
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
| chiamata | x | y | regola | prossima |
|---|---|---|---|---|
mcd1 | 12 | 18 | : (y-x, x) | (6, 12) |
mcd1 | 6 | 12 | : (y-x, x) | (6, 6) |
mcd1 | 6 | 6 | : caso base | ritorna 6 |
mcd2 | 12 | 18 | 12 % 18 = 12 | (18, 12) |
mcd2 | 18 | 12 | 18 % 12 = 6 | (12, 6) |
mcd2 | 12 | 6 | 12 % 6 = 0 | (6, 0) |
mcd2 | 6 | 0 | : caso base | ritorna 6 |
Se 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 e :
| attivazione | m (copia propria) | n | *n dopo *n = *n + 1 |
|---|---|---|---|
| prima | 3 | &x | x = 3 |
| seconda | 2 | &x | x = 4 |
| terza | 1 | &x | x = 5 |
| quarta | 0 | &x | m != 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:
- ;
- ;
- per , .
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 e 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 cresce esponenzialmente: la slide 99 mostra il grafico dei secondi in funzione di , piatto fino a 40 e poi verticale, e dice che si comporta come .
Albero di esecuzione (slide 100-104). Il prof disegna gli alberi per = 3, 4, 5, 6 e colora in verde i termini che vengono ricalcolati. La figura qui è quella di con tutte le chiamate che il codice fa davvero, numerate nell’ordine in cui avvengono:
Gli alberi delle slide si fermano a e , come se fosse un caso base. Con il codice della slide 96 invece chiama e : il conteggio vero delle chiamate per è 15, non i 9 nodi del disegno. La slide 100, poi, disegna i figli di come e , in ordine scambiato rispetto al codice, che chiama prima Fibo(n - 1).
“Quanti sono i nodi dell’albero per ?” (slide 104). Contando tutte le chiamate: con , quindi :
| 2 | 3 | 4 | 5 | 6 | 10 | 30 | |
|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 5 | 8 | 55 | 832 040 | |
| chiamate | 3 | 5 | 9 | 15 | 25 | 177 | 2 692 537 |
Controllo su : , (contate con uno script). Le chiamate crescono come i numeri di Fibonacci, cioè di un fattore circa 1,62 per ogni in più: per questo il grafico della slide 99 esplode.
Overflow: Fibo restituisce un int. ci sta, 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é 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 il sottoalbero di destra (chiamate 11-15) diventa una sola chiamata che trova Sol[3] già pieno. In generale ogni si calcola una volta, e le chiamate sono : 9 per invece di 15, 91 per 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 , doppio da , triplo da . Il numero totale di modi è la somma dei modi di raggiungere , e . 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:
n < 0: si è saltato oltre la cima, quella sequenza di passi non vale, 0 modi;n == 0: si è esattamente in cima, la sequenza vale, 1 modo (quello di non fare più niente).
Non servono casi base per 1 e 2: CountWays(1) = CountWays(0) + CountWays(-1) + CountWays(-2) = 1 + 0 + 0 = 1.
Rundown per (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 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 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?”
- Operazioni: la versione con il ciclo fa un giro per gradino, cioè circa somme. La ricorsiva fa chiamate con : 13 per , 979 per , 192 299 281 per , circa per (contate con uno script).
- Overflow: sta in un
int, supera .CountWaysrestituisceint, quindi da il risultato è sbagliato in entrambe le soluzioni, se usanoint. Conunsigned intsi arriva fino a (il limite è ), conlong longmolto più in là. - Quindi: e vanno bene; con il valore va in overflow e in più la ricorsiva impiega decine di secondi; con la ricorsiva non finisce in nessun tempo ragionevole e il valore non sta in nessun tipo intero del C.
4.9I cammini del robot
(slide 117-122) “Un robot si trova nell’angolo in alto a sinistra di una griglia . 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 o 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 e sono quanti passi mancano verso il basso e verso destra, non il numero di celle. Esempio con , 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 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, .
5Esercizi tipo esame
In una pagina a parte, dal più facile al livello del 30: Ricorsione (esercizi).
6Errori tipici
- Manca il caso base, o non si raggiunge: la funzione si richiama all’infinito, lo stack si riempie e il programma si ferma con un crash. Il caso tipico è un passo che salta il caso base, come
f(n - 2)partendo da un dispari con il caso basen <mark> 0, oFattRic(0)con il caso basen </mark> 1. - Il passo non si avvicina al caso base:
f(n)che chiamaf(n), of(n + 1)con caso basen == 0. - Dimenticare il
returndavanti alla chiamata ricorsiva in una funzione che restituisce un valore (mcd(y, x % y);invece direturn mcd(y, x % y);): il valore calcolato si butta via e la funzione restituisce un valore indefinito. gcc con-Wallavvisa (control reaches end of non-void function). - Confondere l’ordine delle stampe: quello che sta prima della chiamata esce scendendo, quello che sta dopo esce risalendo, in ordine inverso.
- Credere che le variabili locali siano condivise fra le chiamate: ognuna ha il suo record. Condivise lo sono solo le globali, le
statice quelle raggiunte con un puntatore (comexinincrementa). - Fermarsi a nell’albero di Fibonacci: con i casi base 0 e 1, fa altre due chiamate, e il conto delle chiamate cambia.
- Usare la ricorsione multipla senza memoization su valori grandi (Fibonacci, scala, cammini): tempo esponenziale.
- Overflow: fattoriale e Fibonacci escono presto dall’
int(dopo e ). - Array di memo non azzerato (o azzerato solo in parte, come
FiboS[99]nella slide 106): una casella con un valore a caso viene presa per un risultato già calcolato.
7Domande
-
Come definisce il prof il caso base e il caso induttivo di una formulazione induttiva?
-
Quali sono i tre passi per risolvere il caso induttivo (slide 57)?
-
Che differenza c’è fra ricorsione diretta e indiretta?
-
Perché per eseguire una funzione ricorsiva non basta una cella per ogni parametro? Cos’è un record di attivazione?
-
Perché la memoria delle chiamate si gestisce a pila? Cosa succede alla pila quando una funzione termina?
-
Qual è la formulazione induttiva delle Torri di Hanoi? Quante mosse servono con dischi e perché?
-
In che ordine escono le stampe che stanno prima della chiamata ricorsiva, e quelle che stanno dopo?
-
Cosa stampa
entrambe(3), conprintf("%d ", n)sia prima sia dopo la chiamataentrambe(n - 1)e caso basen == 0? -
Quante chiamate fa
FattRic(n)? Quante moltiplicazioni e confronti fannoFatteFattRicper ? -
Quanto vale
xdopoincrementa(&x, 3)conx = 2, e perchémnon cambia nel chiamante? -
Perché la
Fiboricorsiva impiega un tempo esponenziale? Quante chiamate fa per ? -
Cos’è la memoization e come cambia il tempo di Fibonacci?
-
Quali sono i casi base di
CountWayse cosa significano? Quanto valeCountWays(3)e quante chiamate fa? -
Da quale la scala ricorsiva va in overflow con
int, e perché con è inutilizzabile anche senza overflow? -
Come si scrive il MCD ricorsivo con il resto, e qual è il suo caso base?
-
Cosa succede se il caso base non viene mai raggiunto?