Primitief recursieve functie
In de theoretische informatica vormen de primitief recursieve functies een klasse van totale, berekenbare functies. De klasse is gedefinieerd als de kleinste klasse van functies die de basisfuncties (constante functies, opvolgerfunctie en projectie) bevat, en afgesloten is onder compositie en primitieve recursie. Alle primitief recursieve functies zijn totaal en berekenbaar, maar er bestaan totale en berekenbare functies die niet primitief recursief zijn, zoals de Ackermannfunctie. Als we de klasse van primitief recursieve functies ook onder minimalisering afsluiten, ontstaat de klasse van μ-recursieve functies, die wel precies met de berekenbare functies overeenkomt.

Definitie 
Een primitief recursieve functie is een functie die aan een of meer natuurlijke getallen (0,1,2,3,...) als functiewaarde een natuurlijk getal toevoegt, en die behoort tot de als volgt inductief gedefinieerde klasse: 
 de constante functie 0, dat wil zeggen de functie die elke  op 0 afbeeldt, is een primitief recursieve functie;
 de opvolgerfunctie , gedefinieerd als , is een primitief recursieve functie;
 voor elke  is de projectie , gedefinieerd door , een primitief recursieve functie;
 de compositie van primitief recursieve functies is primitief recursief;
 als  en  primitief recursieve functies zijn, is ook de functie  die gedefinieerd wordt door

 primitief recursief. (Deze laatste eis heet primitieve recursie.)

De laatste eis, de primitieve recursie, kan worden gezien als een definitie van  in twee gevallen: het basisgeval, als het eerste argument gelijk aan 0 is, wordt gegeven door de functie , terwijl het recursieve geval, als het eerste argument groter dan 0 is, wordt gegeven door de functie .

Voorbeelden 
Voorbeelden van primitief recursieve functies zijn:

 Optellen
 
 Vermenigvuldigen
 
 Machtsverheffen
 , waarbij  en

Functies die niet primitief recursief zijn 
De primitief recursieve functies vormen een onderklasse van de berekenbare functies; dat wil zeggen dat niet-berekenbare functies, zoals de busy beaver-functie, ook niet primitief recursief zijn. Aangezien het eerste argument van recursief gedefinieerde functies in de recursieve aanroep altijd wordt verlaagd, zijn primitief recursieve functies altijd totale functies. Dat wil zeggen dat berekenbare functies die niet overal gedefinieerd zijn niet primitief recursief kunnen zijn. Ten derde zijn er ook totale, berekenbare functies die niet primitief recursief zijn. Het bekendste voorbeeld van zo'n functie is de Ackermannfunctie.

Literatuur  
 Uwe Schöning, Theoretische Informatik – kurz gefasst, 5. Auflage, Spektrum, 2009
 Elaine Rich, Automata, Computability and Complexity, Pearson, 2008

Theoretische informatica