Esercizio 5Fibonacci ricorsivo, chiamate e complessità

(a) Albero delle chiamate

Ogni nodo è una chiamata, il valore tra parentesi è ciò che restituisce (vedi Algoritmi ricorsiviAlgoritmi ricorsivi come induzione eseguita; albero della ricorsione e record di attivazione nello stack; esempi ReverseArray, LinearSum, Power in tempo logaritmico, Fibonacci ricorsivo (esponenziale) e con memoizzazione; analisi della complessità con l'albero della ricorsione e correttezza per induzione.Algoritmi ricorsivi →):

f(5) = 5
├─ f(4) = 3
│   ├─ f(3) = 2
│   │   ├─ f(2) = 1
│   │   │   ├─ f(1) = 1
│   │   │   └─ f(0) = 0
│   │   └─ f(1) = 1
│   └─ f(2) = 1
│       ├─ f(1) = 1
│       └─ f(0) = 0
└─ f(3) = 2
    ├─ f(2) = 1
    │   ├─ f(1) = 1
    │   └─ f(0) = 0
    └─ f(1) = 1

Ordine di esecuzione (la chiamata sinistra si risolve per intero prima della destra): $f(5) \to f(4) \to f(3) \to f(2) \to f(1) = 1$, poi $f(0) = 0$ e $f(2) = 1 + 0 = 1$; poi $f(1) = 1$ e $f(3) = 1 + 1 = 2$; poi $f(2)$ destra di $f(4)$: $f(1) = 1$, $f(0) = 0$, $f(2) = 1$, quindi $f(4) = 2 + 1 = 3$; poi $f(3)$ destra di $f(5)$ (che ripete tutto il lavoro svolto per $f(3)$ a sinistra): $f(3) = 2$ e infine $f(5) = 3 + 2 = 5$. Nello stack, al momento più profondo, ci sono $5$ record: $f(5), f(4), f(3), f(2), f(1)$, cioè profondità $n$.

(b) Numero di chiamate

Contando i nodi dell'albero: $f(5)$: $1$; $f(4)$: $1$; $f(3)$: $2$; $f(2)$: $3$; $f(1)$: $5$; $f(0)$: $3$. Totale $1 + 1 + 2 + 3 + 5 + 3 = \mathbf{15}$ chiamate (compresa la prima), cioè $14$ chiamate ricorsive oltre alla chiamata iniziale. (Dipende dalla lettura del testo: "chiamate effettuate" va dichiarato; qui $15$ nodi dell'albero, verificato eseguendo il codice.)

Contare le chiamate in generale: $C(0) = C(1) = 1$ e $C(n) = 1 + C(n-1) + C(n-2)$, cioè $1, 1, 3, 5, 9, 15, 25, 41, 67, \dots$. Si dimostra per induzione che $C(n) = 2F(n+1) - 1$.

(c) Complessità al caso pessimo

Il costo di ogni nodo (escluse le chiamate figlie) è $\Theta(1)$, quindi il tempo è proporzionale al numero di nodi: $T(n) \in \Theta(C(n)) = \Theta(F(n+1))$.

• Limite inferiore: $C(n) > 2\,C(n-2)$ (perché $C(n-1) \ge C(n-2)$), quindi $C(n) \ge 2^{\lfloor n/2 \rfloor}$: esponenziale.
• Limite superiore: $C(n) \le 2\,C(n-1) + 1$ dà $C(n) \le 2^{n+1}$.
• Valore esatto: $C(n) = 2F(n+1) - 1 \in \Theta(\Phi^n)$ con $\Phi = \frac{1 + \sqrt5}{2} \approx 1{,}618$ (formula chiusa, vedi Dimostrazioni, induzione e invariantiTecniche di dimostrazione (esempio, controesempio, assurdo), induzione con casi base multipli, invarianti di ciclo (inizializzazione, conservazione, uso alla fine), schema generale per provare la correttezza; esempi svolti su arrayMax, sequenza di bit e numeri di Fibonacci.Dimostrazioni, induzione e invarianti →).

Quindi $T(n) \in \Theta(\Phi^n)$, in particolare $2^{n/2} \lesssim T(n) \lesssim 2^n$: esponenziale, inefficiente anche per $n \approx 50$.

(d) Come migliorarlo

Lo spreco sono i sottoproblemi ripetuti: $f(3)$ è calcolato 2 volte, $f(2)$ 3 volte, $f(1)$ 5 volte. Rimedi:

1. Memoizzazione: una tabella $M[0..n]$; prima di calcolare $f(k)$ si controlla $M[k]$, altrimenti si calcola e si salva. Ogni $f(k)$ è calcolato una volta: $\Theta(n)$ tempo e spazio. Per $f(5)$ le chiamate scendono da $15$ a $9$.
2. Iterativo (dal basso): a <- 0; b <- 1; for i <- 2 to n: (a, b) <- (b, a+b); return b (con $n \ge 1$): $\Theta(n)$ tempo, $\Theta(1)$ spazio.
3. Potenza veloce: con la formula $F(n) = \frac{1}{\sqrt5}(\Phi^n - \hat\Phi^n)$ e l'algoritmo Power (o con potenze di matrici $2 \times 2$ a interi, che evitano gli errori di arrotondamento): $O(\log n)$ operazioni (vedi Algoritmi ricorsiviAlgoritmi ricorsivi come induzione eseguita; albero della ricorsione e record di attivazione nello stack; esempi ReverseArray, LinearSum, Power in tempo logaritmico, Fibonacci ricorsivo (esponenziale) e con memoizzazione; analisi della complessità con l'albero della ricorsione e correttezza per induzione.Algoritmi ricorsivi →).

Errori comuni

• Dire che l'albero ha $n$ nodi (è il numero di livelli): ha $\Theta(\Phi^n)$ nodi.
• Contare male il numero di chiamate: per $f(5)$ sono $15$ nodi (non $5$, non $8$).
• Concludere $\Theta(n)$ perché "ci sono $n$ livelli": a ogni livello il lavoro raddoppia circa.
• Proporre di "usare un ciclo" senza spiegare che il guadagno viene dal non ripetere sottoproblemi.