Funzione ricorsiva: differenze tra le versioni

Le funzioni ricorsive sono un sovrainsieme delle [[funzione ricorsiva primitiva|funzioni ricorsive primitive]], ed infatti la loro definizione induttiva (come vedremo nel seguito) è costruita a partire da quella di queste ultime. Esistono quindi funzioni ricorsive che non sono anche ricorsive primitive, e l'esempio più noto è quello della [[funzione di Ackermann]]. Altre classi di funzioni [[turing equivalenza|equivalenti a quella delle funzioni ricorsive]] sono le [[funzioni lambda-ricorsive|funzioni λ-ricorsive]] e le funzioni che possono essere calcolate da un [[algoritmo di Markov]].

 

Le funzioni ricorsive sono definite sulla base delle [[Funzione ricorsiva primitiva|funzioni ricorsive primitive]].

 

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.

 

* [[Numero di Fibonacci]]

* [[Funzione 91 di McCarthy]]