Fonction récursive
En informatique, le terme fonction récursive désigne deux concepts liés, mais distincts.
Programmation informatique
Du point de vue programmation, une fonction récursive est une fonction qui peut s'appeler elle-même au cours de son exécution. Des fonctions mutuellement récursives sont des fonctions qui peuvent s'appeler mutuellement les unes les autres au cours de leur exécution.
Un exemple canonique (bien que peu intéressant en pratique) de définition récursive de fonction est la factorielle : on définit fact(n) = si n > 0, alors n*fact(n-1), sinon 1. Remarquer l'usage d'un appel à fact à l'intérieur de sa propre définition.
Les fonctions récursives sont très utiles pour travailler sur des structures récursives comme les arbres. Ce concept est directement relié aux fonctions récursives de la théorie de la calculabilité.
Logique mathématique (Calculabilité)
En logique mathématique, il s'agit d'un synonyme de fonction calculable.