Relazioni di ricorrenza

Definizione ricorsiva di una sequenza = relazione di ricorrenza

Data una sequenza $a_0,a_1,..,a_n$, una relazione di ricorrenza esprime $a_n$ in termini di uno o più termini precedenti della sequenza, cioè di $a_0,a_1,..,a_{n-1}$ per tutti gli interi non negativi $n \geq 0$

Data una relazione di ricorrenza, unitamente alle condizioni iniziali, l’obiettivo è di risolvere la relazione di ricorrenza cioè trovare una formula chiusa per l’$n$-esimo termine della sequenza (formula esplicita in $n$ che non dipende più dai termini precedenti)

Esempio: data la relazione di ricorrenza e la sua condizione iniziale:

• $a_n = a_{n-1}r$ (relazione di ricorrenza)
• $a_0 = b$ (condizione iniziale)

La sua soluzione è $a_n = br^n$

D’ora in avanti useremo $T(n)$ per indicare l’$n$-esimo termine $a_n$ della sequenza

Algoritmi ricorsivi

In informatica, l’interesse per le soluzioni delle relazioni di ricorrenza risiede nel fatto che esse nascono dall’analisi di algoritmi ricorsivi

Esempio: calcolo del fattoriale

procedure fattoriale(n)
	if n = 1 then
		return 1
	else 
		return n*fattoriale(n-1)

La complessità asintotica di un algoritmo ricorsivo si esprime attraverso una relazione di ricorrenza:

• $T(n)= T(n-1)+b$
• $T(1)=a$

$a =$ costo per effettuare return $1$, $b=$ costo per effettuare il prodotto n*fattoriale(n-1)

Metodi di risoluzione