Esercizio 5Fibonacci ricorsivo, chiamate e complessità

(a) Albero delle chiamate

Ogni nodo è una chiamata, il valore a destra del segno uguale è 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 → e RicorsioneFunzioni che chiamano se stesse: caso base e passo ricorsivo, stack delle chiamate, esempi su numeri, stringhe e liste, ricorsione multipla e suo costo, divide et impera, confronto con l'iterazione.Ricorsione →):

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$ (lo spazio è quindi $\Theta(n)$ anche se il tempo è esponenziale: i record vengono tolti e riusati; il funzionamento dello stack è in Stack e chiamata di funzioni in ARMChiamata con BL e ritorno con BX LR; convenzione di chiamata AAPCS (argomenti in r0-r3, risultato in r0, registri da preservare r4-r11); stack discendente pieno con PUSH e POP; record di attivazione; funzioni foglia e non foglia; esempio ricorsivo del fattoriale con evoluzione dello stack.Stack e chiamata di funzioni in ARM →).

Stack delle chiamate nei primi passi (cima a destra; ogni record ha il suo parametro n e, dopo la prima chiamata figlia, il valore parziale ricevuto):

(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$: base $C(0)=1=2F(1)-1$, $C(1)=1=2F(2)-1$; passo $C(n+1)=1+C(n)+C(n-1)=1+(2F(n+1)-1)+(2F(n)-1)=2(F(n+1)+F(n))-1=2F(n+2)-1$ (Principio di induzionePer dimostrare una proprietà per ogni n basta il passo base e il passo induttivo da n a n+1.Principio di induzione →, 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 →).

(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. Per induzione a passo $2$: base $C(0)=C(1)=1=2^0$; se $C(n-2)\ge2^{\lfloor (n-2)/2\rfloor}=2^{\lfloor n/2\rfloor-1}$, allora $C(n)\ge2\,C(n-2)\ge2^{\lfloor n/2\rfloor}$. Controllo: $C(6)=25\ge2^3=8$.
• Limite superiore: $C(n) \le 2\,C(n-1) + 1$ dà $C(n) \le 2^{n+1}$: aggiungendo $1$ a entrambi i membri, $C(n)+1\le2\,(C(n-1)+1)$, quindi $C(n)+1\le2^n\,(C(0)+1)=2^{n+1}$. Controllo: $C(5)=15\le2^6-1=63$.
• 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$: la discesa $f(5),f(4),f(3),f(2),f(1),f(0)$ fa $6$ chiamate e riempie $M[2]=1$, $M[3]=2$, $M[4]=3$, $M[5]=5$; le altre $3$ (la seconda figlia di $f(3)$, di $f(4)$ e di $f(5)$) trovano subito il valore in $M$ o sono un caso base.
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.