Definizioni ricorsive

Ci sono casi in cui oggetto (funzioni, insiemi, algoritmi, ..) può essere definito in termini di se stesso, ma di più piccole dimensioni

Esempio: consideriamo la sequenza aritmetica (progressione aritmetica)

• $a, a+d, a+2d, a+3d, .., a+nd,..$
• $b_n = a+nd$ (n-esimo termine della sequenza) con $n \in \mathbb N$

Definizione ricorsiva della sequenza:

• $b_n = a+nd = a +(n-1)d +d = b_{n-1}+d$ per $n \geq 1$
• $b_0 = a$

Esempio: consideriamo la sequenza geometrica (progressione geometrica)

• $a, ar, ar^2, ar^3,..,ar^n,..$
• $b_n = ar^n$ (n-esimo termine della sequenza) con $n \in \mathbb N$

Definizione ricorsiva della sequenza:

• $b_n = ar^n = ar^{n-1}r=b_{n-1}r$ per $n \geq 1$
• $b_0 = a$

Definire funzioni ricorsive

Per definire una funzione ricorsiva sull’insieme degli interi non negativi

• passo base: specificare il valore della funzione in $0$
• passo ricorsivo: dare una regola per determinare il valore della funzione in $n$ in termini del valore della funzione in interi $n-1$