Funzione ricorsiva: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
FrescoBot (discussione | contributi)
m Bot: niente spazio dopo l'apostrofo
FrescoBot (discussione | contributi)
m Bot: niente spazi dopo l'apostrofo e modifiche minori
Riga 10:
Le '''funzioni ricorsive''' sono definite sulla base delle [[Funzione ricorsiva primitiva|funzioni ricorsive primitive]].
 
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'all’'''operatore μ''', detto anche operatore di minimizzazione.
 
L'operatore μ è così definito:
Riga 19:
\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.
 
Si ricorda comunque che l'operatore di minimizzazione opera su '''funzioni totali'''. Si può dimostrare che se si ammette l'applicazione dell' operatore di minimizzazione su funzioni parziali, allora le funzioni ricorsive non sarebbero chiuse rispetto alla minimizzazione.
 
== Esempi di funzioni ricorsive ==