Algoritmi ricorsivi

Definizione (algoritmo ricorsivo). Un algoritmo ricorsivo invoca se stesso su istanze sempre più piccole. La soluzione di un'istanza di taglia $n$ si ottiene:

• direttamente per i casi base $n = n_0, \dots, n_0 + k$;
• altrimenti usando le soluzioni di una o più istanze di taglia $< n$.

Esempio. LinearSum(A, n) ha il caso base $n=1$ e per $n>1$ usa LinearSum(A, n-1): su $A=[3,1,4]$ con $n=3$ restituisce $3+1+4=8$.

È l'induzione trasformata in programma: il caso base della ricorsione è il caso base dell'induzione, e la chiamata su un'istanza più piccola corrisponde all'ipotesi induttiva. Per questo la correttezza si prova per induzione (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 → e 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 →). La ricorsione come tecnica di programmazione è introdotta in 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 → (Fondamenti di Informatica).

Traccia di LinearSum(A, 3) con $A=[3,1,4]$: la chiamata con $n=3$ aspetta LinearSum(A,2), che aspetta LinearSum(A,1) $=A[0]=3$; risalendo, LinearSum(A,2) $=3+A[1]=3+1=4$ e LinearSum(A,3) $=4+A[2]=4+4=8$. Il risultato si costruisce al ritorno dalle chiamate.

Esempi

Algoritmo ReverseArray(A, i, j)           Algoritmo LinearSum(A, n)
Input: array A, indici i, j >= 0          Input: array A, intero n >= 1
Output: A[i..j] ribaltato in loco         Output: somma dei primi n elementi
if i < j then                             if n = 1 then return A[0]
    swap(A[i], A[j])                      else return LinearSum(A, n-1) + A[n-1]
    ReverseArray(A, i+1, j-1)
return

Albero della ricorsione e stack

L'esecuzione su una data istanza è descritta dall'albero della ricorsione: ogni nodo è una chiamata, la radice è la prima, i figli di un nodo sono le chiamate fatte direttamente da esso, le foglie sono i casi base.

A runtime, la memoria si divide in stack (variabili locali e riferimenti: ogni chiamata aggiunge un record di attivazione e lo toglie quando finisce, con politica LIFO, e si accede solo all'ultimo inserito) e heap (oggetti, o strutture allocate con malloc). La divisione è spiegata in Gestione della memoria in CSegmenti di memoria di un processo (codice, dati statici, stack, heap); durata delle variabili; allocazione dinamica con malloc, calloc, realloc e free; errori classici: memory leak, dangling pointer, double free, buffer overflow; strumenti di controllo.Gestione della memoria in C →; come il processore costruisce e distrugge i record di attivazione è 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 →. In LinearSum(A, 5) la chiamata LinearSum(A, 3) crea il suo record sopra quelli di n=5 e n=4; una ricorsione di profondità $d$ occupa $\Theta(d)$ di stack.

Complessità con l'albero della ricorsione

A ogni nodo si attribuisce il costo delle operazioni della sua chiamata escluse le chiamate ricorsive; il costo totale è la somma sui nodi. Per un limite superiore si stima per ogni istanza di taglia $n$, per un limite inferiore si esibisce un'istanza (o una stima valida per tutte).

• LinearSum: $n$ nodi (una chiamata per ogni $n, n-1, \dots, 1$), ciascuno $\Theta(1)$: $\Theta(n)$.
• ReverseArray, con taglia $n = j - i + 1$: ogni chiamata riduce la taglia di $2$ (si passa da $(i,j)$ a $(i+1,j-1)$), quindi $\lfloor n/2 \rfloor + 1$ chiamate di costo costante: $\Theta(n)$. Traccia su $A=[1,2,3,4,5]$, $n=5$: (0,4) scambia $A[0],A[4]$ e dà $[5,2,3,4,1]$; (1,3) dà $[5,4,3,2,1]$; (2,2) ha $i<j$ falso e termina. Sono $3=\lfloor5/2\rfloor+1$ chiamate. Per $n=4$ ((0,3), (1,2), (2,1)) sono ancora $3=\lfloor4/2\rfloor+1$: l'ultima chiamata ha taglia $0$ o $1$ ed è il caso base.

Potenze in tempo logaritmico

Formula (potenza in tempo logaritmico). $x^n = 1$ se $n = 0$; $x \cdot (x^{(n-1)/2})^2$ se $n$ dispari; $(x^{n/2})^2$ se $n$ pari e positivo.

Esempio. Power(2, 10) calcola $2^{10}=(2^5)^2$ con $5$ chiamate ($n=10,5,2,1,0$) e restituisce $1024$.

Algoritmo Power(x, n)
Input: x reale, n >= 0 intero
Output: x^n
if n = 0 then return 1
if n è dispari then
    y <- Power(x, (n-1)/2)
    return x * y * y
else
    y <- Power(x, n/2)
    return y * y

Alla $i$-esima chiamata (la prima è la $0$-esima) l'esponente vale $\lfloor n/2^i \rfloor$: se $n$ è pari si passa a $n/2$, se è dispari a $(n-1)/2=\lfloor n/2\rfloor$, in entrambi i casi la parte intera della metà. La ricorsione si ferma quando l'esponente è $0$, cioè quando $2^i > n$ (stesso ragionamento della ricerca binaria, vedi Problemi computazionali e algoritmiProblema computazionale come insieme di coppie (istanza, soluzione); algoritmo e modello di calcolo RAM; pseudocodice; taglia di un'istanza; ADT e struttura dati concreta; esempio svolto con ricerca lineare e binaria in un array ordinato.Problemi computazionali e algoritmi → e Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →), per $i=\lfloor \log_2 n \rfloor + 1$. L'albero è un cammino di $\lfloor\log_2 n\rfloor+2$ nodi, ciascuno $\Theta(1)$. $t_{Power}(n) \in O(\log n)$. Contando le chiamate: $n = 1000$ ne richiede $11$ ($\lfloor \log_2 1000 \rfloor + 2 = 9 + 2$), contro le $999$ moltiplicazioni dell'approccio ingenuo.

Traccia di Power(2, 10): le chiamate scendono con esponenti $10 \to 5 \to 2 \to 1 \to 0$ e i valori risalgono così: Power(2,0) $=1$; Power(2,1) ($n$ dispari, $y=1$) $=2\cdot1\cdot1=2$; Power(2,2) ($n$ pari, $y=2$) $=2\cdot2=4$; Power(2,5) ($n$ dispari, $y=\text{Power}(2,2)=4$) $=2\cdot4\cdot4=32$; Power(2,10) ($y=32$) $=32\cdot32=1024$. Si calcola y una volta sola e si riusa: chiamare Power due volte riporterebbe a $\Theta(n)$.

Con la formula $F(n) = \frac{1}{\sqrt5}(\Phi^n - \hat\Phi^n)$ (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 →; $\Phi\approx1{,}618$ è la sezione aurea), PowerFib(n) $= (Power(\Phi,n) - Power(\hat\Phi,n))/\sqrt5$ costa $O(\log n)$ operazioni aritmetiche su reali (in pratica, con numeri a precisione finita, per $n$ grandi serve aritmetica esatta).

Fibonacci ricorsivo e memoizzazione

fib(n): se n <= 1 restituisci n; altrimenti restituisci fib(n-1) + fib(n-2)

Formula (numero di chiamate di fib). Il numero di chiamate $C(n)$ soddisfa $C(0) = C(1) = 1$ e $C(n) = 1 + C(n-1) + C(n-2)$, cioè $C(n) = 2F(n+1) - 1$: $1, 1, 3, 5, 9, 15, 25, 41, \dots$ ($n = 0, 1, 2, 3, 4, 5, 6, 7$; per $\mathrm{fib}(5)$ sono $15$ chiamate, verificato eseguendo il codice). Cresce come $\Phi^n$: esponenziale. Lo spreco è nei sottoproblemi ripetuti ($\mathrm{fib}(3)$ è ricalcolato più volte).

Perché $C(n)=2F(n+1)-1$. Per induzione (due casi base, perché si usano due valori precedenti, 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 →). Base: $C(0)=1=2F(1)-1$ e $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$. Poiché $F(n)\approx\Phi^n/\sqrt5$ (il secondo termine $|\hat\Phi|^n/\sqrt5$ tende a $0$), $C(n)\approx\frac{2}{\sqrt5}\Phi^{n+1}$: ogni incremento di $n$ moltiplica le chiamate per $\Phi\approx1{,}618$. Chiamate di $\mathrm{fib}(4)$, $C(4)=9$:

Somma $1+1+2+3+2=9$; il sottoproblema $\mathrm{fib}(2)$ è calcolato due volte e $\mathrm{fib}(1)$ tre. Il grafico confronta le chiamate senza memoizzazione (curva $\frac{2}{\sqrt5}\Phi^{n+1}-1$, che coincide con $C(n)$ ai valori interi con errore inferiore a $0{,}5$) con quelle con memoizzazione, $2n-1$:

{"tipo":"funzione","titolo":"Chiamate di fib(n): senza memoizzazione crescono come 2Φ^(n+1)/√5 − 1 (C(5) = 15, C(10) = 177), con memoizzazione sono 2n − 1 (9 per n = 5, 19 per n = 10)","curve":[{"espressione":"2*((1+sqrt(5))/2)^(x+1)/sqrt(5)-1","etichetta":"senza memoizzazione: C(n)"},{"espressione":"2*x-1","etichetta":"con memoizzazione: 2n−1"}],"x":[1,12],"y":[0,500],"punti":[{"x":5,"y":15,"etichetta":"15"},{"x":10,"y":177,"etichetta":"177"}],"assi":{"x":"n","y":"chiamate"}}
``` Con la **memoizzazione** (si salva ogni risultato in una tabella e lo si riusa) per $\mathrm{fib}(5)$ le chiamate scendono a $9$ e in generale a $\Theta(n)$ (ciascun $\mathrm{fib}(k)$ è calcolato una volta sola). Per $\mathrm{fib}(5)$: la discesa $\mathrm{fib}(5),\mathrm{fib}(4),\mathrm{fib}(3),\mathrm{fib}(2),\mathrm{fib}(1),\mathrm{fib}(0)$ fa $6$ chiamate e riempie la tabella; poi $\mathrm{fib}(3)$ chiama $\mathrm{fib}(1)$ (caso base, una chiamata), $\mathrm{fib}(4)$ chiama $\mathrm{fib}(2)$ (già in tabella) e $\mathrm{fib}(5)$ chiama $\mathrm{fib}(3)$ (già in tabella): $6+3=9$. In generale $n+1$ chiamate di discesa più $n-2$ chiamate che trovano già il risultato, circa $2n$. La memoizzazione usa $\Theta(n)$ di memoria per la tabella: è lo scambio tempo contro spazio.

*Esempio.* $C(5)=2F(6)-1=2\cdot8-1=15$ chiamate per `fib(5)`.

## Correttezza per induzione

Sia $n$ la taglia. Si dimostra la correttezza per i casi base $n \in [n_0, n_0 + k]$; poi, assumendo che l'algoritmo risolva correttamente tutte le istanze di taglia $m \in [n_0, n]$, si dimostra che risolve quelle di taglia $n + 1$.

**LinearSum.** Base $n = 1$: restituisce $A[0]$ ✓. Passo: per ipotesi `LinearSum(A, n)` $= \sum_{i=0}^{n-1} A[i]$, quindi `LinearSum(A, n+1)` $= \sum_{i=0}^{n-1} A[i] + A[n] = \sum_{i=0}^{n} A[i]$ ✓.

**Power.** Base $n = 0$: $x^0 = 1$ ✓. Passo: si assume che `Power` sia corretta per **tutti** gli esponenti da $0$ a $n$ (ipotesi forte: serve perché la chiamata ricorsiva è su circa la metà dell'esponente, non su $n$). Se $n+1$ è pari, la chiamata è su $(n+1)/2 \le n$ (vero per $n\ge1$), quindi per ipotesi $y = x^{(n+1)/2}$ e $y\cdot y = x^{n+1}$. Se $n+1$ è dispari, la chiamata è su $n/2 \le n$, quindi $y = x^{n/2}$ e $x \cdot y \cdot y = x \cdot x^{n} = x^{n+1}$ ✓ (si usa $x^a x^b = x^{a+b}$, vedi <a class="wiki glossa" href="/analisi-1/appunti/funzioni-potenza/" aria-describedby="sp-10">Funzioni potenza<span class="spiega" role="tooltip"><span class="spiega-testo" id="sp-10">Le potenze x^alfa al variare dell&#39;esponente: domini, grafici, radici n-esime e proprietà delle potenze con base positiva.<span class="spiega-vai">Funzioni potenza →</span></span><span class="graffa" aria-hidden="true"><i class="g-l"></i><i class="g-linea"></i><i class="g-punta"></i><i class="g-linea"></i><i class="g-r"></i></span></span><!--/spiega--></a>).

## Errori comuni

- Dimenticare un caso base, o una chiamata che non riduce la taglia (non termina): in `ReverseArray` serve $i < j$.
- Contare il costo di un nodo **includendo** le chiamate figlie (le conta due volte).
- Ricalcolare più volte la stessa sottoistanza (`Power` con due chiamate, `fib` senza memoizzazione).
- Dimenticare che la ricorsione consuma stack: profondità $d$ ⇒ spazio $\Theta(d)$.