Definizione ricorsiva

Una successione di numeri è definita ricorsivamente quando ciascun suo termine si ottiene applicando un algoritmo (clausola di ricorsione o regola ricorsiva) che permette di calcolarlo a partire dal termine o dai termini che lo precedono, fissato il primo elemento della successione tramite una clausola base. Ad esempio, il fattoriale di un numero naturale nè denotato con il simbolo n! e si definisce mediante l’espressionen! = n(n-1)! con 0! = 1; invece, la successione di Fibonacci, formata dai numeri 1, 1, 2, 3, 5, 8, 13, 21, 34, … è definita dalla seguente regola ricorsiva: a_n = a_{n – 1}+ a_{n – 2}, (n= 2, 3, 4, …), con a₀= 1, a₁ = 1.