Funzione ricorsiva: differenze tra le versioni

 

Le '''funzioni ricorsive''' sono la più piccola classe di funzioni contenente le funzioni ricorsive primitive chiusa rispetto agli operatori di composizione, di ricorsione primitiva e all' '''operatore μ''', detto anche operatore di minimizzazione.

 

L'operatore μ è così definito:

\mu\,y.(f(y, x_1, \ldots, x_n)=0)\ &\stackrel{\mathrm{def}}{=} \ \ il\ pi\grave{u}\ piccolo\ y\ tale\ che\ f(y, x_1, \ldots, x_n)=0\ \ (se\ esiste)

\end{align}</math>

 

Le funzioni ricorsive primitive sono quindi un sottoinsieme delle funzioni ricorsive. Si noti che mentre le funzioni ricorsive primitive sono sempre totali (NB: non tutte le funzioni totali sono ricorsive primitive), le funzioni ricorsive possono essere parziali, ovvero possono non essere definite per alcuni valori di input: infatti, l'operatore minimizzazione non restituisce alcun valore nel caso in cui la funzione a cui è applicato non si annulla per nessun valore dell' argomento.