La ricorsione

Giuseppe Peano

Il termine ricorsione è usato in matematica ogni volta che si definisce qualcosa facendo riferimento (cioè “ricorrendo”) alla definizione stessa.

Il primo matematico che ha utilizzato il concetto di ricorsività è stato Giuseppe Peano nel suo quinto assioma usato per la definizione di numeri naturali:

  • 1 è un numero naturale: caso base
  • se N è un numero naturale allora anche succ(N) è un numero naturale: caso induttivo.

Cioè ogni numero naturale può essere ottenuto ripetendo un numero finito di volte l’applicazione della definizione precedente.

Il fattoriale di un numero è il tipico caso di ricorsione.

0!=1

n!=n\cdot (n-1)!

ossia il fattoriale di un generico numero n può essere ottenuto dal fattoriale del numero che precede il numero in questione,  così via finchè si giunge al numero 0, di cui è noto il valore del fattoriale.

Per esempio:

4!=4\cdot 3!=4\cdot 3\cdot 2!=4\cdot 3\cdot 2!=4\cdot 3\cdot 2\cdot 1!=4\cdot 3\cdot 2\cdot 1\cdot 0!

Funzione ricorsiva

Una funzione matematica è definita ricorsivamente quando nella sua definizione compare un riferimento a se stessa. In informatica una funzione di dice ricorsiva quando al suo interno è presente una chiamata a se stessa.

Lo schema di una funzione ricorsiva è così costituito:

  • condizione di terminazione
  • passo ricorsivo.
Questa voce è stata pubblicata in Senza categoria. Contrassegna il permalink.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *