fonction μ-récursive

En informatique et en mathématiques, le terme fonction récursive ou fonction calculable désigne la classe de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique fini. En fait, cela fait référence à deux concepts liés, mais distincts. En théorie de la calculabilité, la classe des fonctions récursives est une classe plus générale que celle des fonctions récursives primitives, mais plus restreinte que celle des fonctions semi-calculables (ou partielles récursives). En informatique, les fonctions récursives sont des fonctions dont le calcul nécessite d'invoquer la fonction elle-même, c'est-à-dire que dans ce deuxième cas, on insiste plutôt sur la façon dont le calcul est mis en œuvre que sur la classe de fonctions.