Algoritmi ricorsivi

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$.

È l'induzione trasformata in programma: 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 →).

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). 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$, quindi $\lfloor n/2 \rfloor + 1$ chiamate di costo costante: $\Theta(n)$.

Potenze 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.

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 l'esponente è $\le n/2^i$: l'albero è un cammino di $O(\log n)$ nodi, ciascuno $\Theta(1)$. $t_{Power}(n) \in O(\log n)$. Contando le chiamate: $n = 1000$ ne richiede $11$ ($\lfloor \log_2 n \rfloor + 2$), contro le $999$ moltiplicazioni dell'approccio ingenuo. 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 →), 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)

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). 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).

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: se $n+1$ è pari, per ipotesi $y = x^{(n+1)/2}$ e $y\cdot y = x^{n+1}$; se è dispari, $y = x^{n/2}$ e $x \cdot y \cdot y = x^{1 + n}$ ✓.

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)$.