Definizione ricorsiva
# Definizione ricorsiva

In matematica una definizione ricorsiva di un insieme A si ha quando per definire A vengono elencati degli elementi di A e delle regole per costruire nuovi elementi di A a partire da elementi di A.

Ad esempio l'insieme P dei numeri pari può essere definito ricorsivamente dicendo:

* 2 appartiene a P
* se un numero n appartiene a P allora anche n+2 appartiene a P

Una definizione ricorsiva di una funzione f definita sui numeri naturali si ha quando f viene definita dando esplicitamente il valore che assume su 0 e dando una regola per calcolare il valore della funzione su n a partire dal valore che assume su n-1.

Anche in ambiente informatico l'uso della definizione ricorsiva è piuttosto comune, soprattutto sotto forma di acronimo ricorsivo: un esempio molto noto è

    GNU = GNU's Not Unix

dove si può notare come il nome è la parte in un certo senso meno importante della definizione stessa.

Infine, l'induzione matematica può portare a una specie di definizione ricorsiva, dove però c'è un caso speciale al quale tutti gli altri prima o poi devono giungere e che quindi fa terminare la ricorsione. Ad esempio, per calcolare il fattoriale di un numero positivo n, si può dire

    il fattoriale di 1 è 1;
    il fattoriale di n è n volte il fattoriale di (n-1), se n è maggiore di 1.
