recursive function

Pour calculer la factorielle de 4, on peut remplacer le problème par le même calcul sur 3, puis sur 2, sur 1 et enfin sur 0. À 0, une valeur connue arrête la descente. Les réponses remontent ensuite dans l'ordre inverse pour donner 24. Une fonction récursive fonctionne ainsi : elle se rappelle elle-même avec une donnée plus simple et possède un cas de base qui met fin aux appels.

En informatique, une fonction récursive est une fonction dont l'exécution fait appel à elle-même, directement ou par l'intermédiaire d'autres fonctions. Sa définition comporte un cas de base, traité directement, et un cas récursif. Pour que le calcul s'achève, une mesure ou une condition de progression doit conduire chaque chaîne d'appels à un cas de base.

En théorie de la calculabilité, l'expression a un autre sens. Les fonctions mu-récursives partielles sont construites sur les entiers naturels à partir de la fonction zéro, de la fonction successeur et des projections, par composition, récursion primitive et minimisation non bornée. Lorsque le résultat de cette construction est défini pour toute entrée, la fonction obtenue est totale. Les fonctions mu-récursives partielles correspondent aux fonctions partielles calculables par une machine de Turing, conformément à la thèse de Church-Turing.

Les fonctions récursives primitives n'emploient pas la minimisation. Elles forment une sous-classe stricte des fonctions récursives. Le sens informatique décrit donc une manière d'organiser des appels, tandis que le sens mathématique classe les fonctions calculables.

Une définition récursive informatique réunit quatre éléments. Le domaine précise les arguments admis. Le cas de base fournit une réponse sans nouvel appel. Le cas récursif exprime la réponse au moyen de la même fonction. Enfin, une progression vers la base rend les arguments plus simples à chaque appel. Le cas récursif dépend du résultat des appels plus simples ; la terminaison dépend, elle, de leur arrivée effective au cas de base. Ces données décrivent le schéma d'une définition récursive. Pour dérouler la factorielle sur les entiers naturels, il faut en outre préciser sa valeur de base F(0) = 1 et sa règle F(n) = n × F(n − 1) pour n > 0. Elles définissent le mécanisme, indépendamment du langage de programmation ou de la manière dont les appels sont stockés en mémoire.

On veut calculer la factorielle de 4. Les données sont l'entier naturel 4, le cas de base « la factorielle de 0 vaut 1 » et la règle qui multiplie l'entier courant par la factorielle de l'entier précédent.

En notant F la fonction factorielle et n l'entier naturel donné, la définition est : $F(0)=1\text{et}F(n)=nF(n-1)\text{ pour }n>0F(0)=1\backslash quad\backslash text\{et\}\backslash quad\; F(n)=n\backslash ,F(n-1)\backslash text\{\; pour\; \}n>0$.

1. Remplacer F(4) par 4 × F(3).
2. Remplacer successivement F(3), F(2) et F(1), jusqu'à obtenir 4 × 3 × 2 × 1 × F(0).
3. Appliquer le cas de base F(0) = 1.
4. Multiplier en remontant : 1 pour F(0), puis 1 pour F(1), puis 2, puis 6, puis 24.

Le résultat exact est F(4) = 24. Le contrôle direct consiste à refaire le produit 4 × 3 × 2 × 1, qui vaut également 24. Le schéma des appels rend visible la descente vers F(0) et la remontée des résultats.

Pour programmer la factorielle, la récursion suit directement sa définition : un appel traite 0, l'autre ramène n à n − 1. Une boucle est préférable lorsque la profondeur des appels devient un coût observable et que le calcul se parcourt simplement de 1 à n.

Pour décrire un calcul composé de sous-problèmes de même forme, la récursion fait correspondre chaque étape à un nouvel appel. Une formulation itérative est préférable si aucun sous-problème emboîté n'apparaît et qu'un simple compteur suffit.

En calculabilité, on ne cherche pas la forme la plus commode d'un programme. On établit qu'une fonction appartient à une classe construite avec des fonctions de base et des schémas autorisés. Le point d'attention est alors la construction mathématique, pas la syntaxe du code.

Fonction récursive au sens informatique et fonction mu-récursive. La première se reconnaît à un appel direct de la fonction par elle-même, ou à un appel indirect entre plusieurs fonctions. La seconde appartient à une classe mathématique définie par des fonctions de base et trois schémas de construction. Un programme factoriel auto-appelant illustre le premier sens ; son appartenance à une classe de calculabilité relève du second.

Fonction récursive et fonction récursive primitive. Une fonction récursive primitive admet une construction sans minimisation non bornée. Celle-ci élargit les schémas de construction disponibles, mais son emploi dans une construction donnée ne suffit pas à prouver qu'une fonction n'est pas récursive primitive : il faut montrer qu'elle n'admet aucune représentation récursive primitive.

Récursion et simple répétition. Une boucle répète des instructions sans que la fonction se rappelle nécessairement elle-même. Dans le calcul de F(4), la présence des appels F(3), F(2), F(1) et F(0) caractérise la version récursive ; un compteur multipliant successivement 1 à 4 caractérise une version itérative.

Un cas de base ne garantit pas à lui seul l'arrêt. Si l'argument ne progresse pas vers ce cas, les appels continuent. Remplacer F(n) par n × F(n + 1), même avec F(0) = 1, éloigne tout entier positif de 0 ; il faut employer une règle qui diminue n.

La minimisation peut ne trouver aucune valeur. Une recherche non bornée ne s'arrête pas lorsqu'aucun entier naturel ne satisfait le critère. Elle définit alors une fonction partielle sur cet argument. Pour parler d'une fonction de ℕⁿ dans ℕ, il faut vérifier qu'un résultat existe pour toute entrée du domaine.

La définition mathématique ne promet pas une exécution efficace. Être calculable indique qu'un processus mécanique fini produit le résultat pour les entrées où la fonction est définie. Cela ne fixe ni le nombre d'étapes ni la mémoire nécessaire ; ces coûts doivent être étudiés séparément.

L'algorithme replace la récursion parmi les procédés finis servant à transformer des données en résultat.

La machine de Turing donne un autre modèle du calcul et éclaire l'équivalence évoquée par la thèse de Church-Turing.

L'article Une fonction qui dépasse les bornes prolonge la réflexion sur les fonctions, les bornes et la calculabilité.