Fonction Récursive


Fonction Récursive

Fonction récursive

Wiktprintable without text.svg

Voir « récursif » sur le Wiktionnaire.

En informatique et en mathématiques, le terme fonction récursive désigne une classe de fonctions calculables, autrement dit de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique. 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. 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 que cela englobe.

Sommaire

Logique informatique et paradigmes de programmation

Du point de vue de la programmation, une fonction récursive est une fonction, au sens informatique de ce terme, qui peut s'appeler elle-même au cours de son exécution ; on parle également de définition récursive ou d'appel récursif de fonction.

Article détaillé : algorithme récursif.

Logique mathématique (Calculabilité)

Fonction récursive

En théorie de la calculabilité, une fonction récursive est une fonction à un ou plusieurs arguments entiers, qui peut se calculer en tout point par une procédure mécanique[1]. Il est plus cohérent de définir les fonctions partielles récursives, qui sont aussi des fonctions partiellement récursives, avant les fonctions récursives. Formellement, une fonction récursive est alors une fonction partielle récursive définie en tout point. On trouve de plus en plus souvent le terme de fonction calculable pour désigner une fonction récursive, qui est le terme historique. Mais ce dernier est encore très utilisé. Il y a plusieurs définitions équivalentes de fonctions calculables, l'une d'elles étant que ce sont les fonctions calculées par une machine de Turing (ces fonctions sont a priori partielles) dont le calcul termine pour toute entrée.

Historiquement on a d'abord introduit dans les années 1920 la classe des fonctions récursives primitives, dont on s'est rapidement rendu compte qu'elle ne capturait pas toutes les fonctions calculables (en un sens encore intuitif). Le schéma de définition par récurrence utilisé pour définir ces fonctions est bien récursif au premier sens du terme : une fonction est définie en fonction d'elle-même.

Jacques Herbrand décrivit, dans une lettre adressée à Kurt Gödel en 1931, un modèle de calcul, des systèmes d'équations avec un mécanisme d'évaluation symbolique « par valeur », comme on dirait maintenant. Ce modèle fut précisé par Gödel lors d'exposés à Princeton en 1934. Les fonctions ainsi calculées furent appelées fonctions récursives générales. Les systèmes d'équations de Herbrand-Gödel utilisent de façon libre des appels récursifs de fonction au premier sens de ce terme. L'équivalence démontrée, par Stephen Cole Kleene, de cette définition avec celle des fonctions λ-calculables et des fonctions calculables par machine de Turing fournit des arguments pour la thèse de Church-Turing, qui énonce que ces modèles capturent effectivement la notion intuitive de fonction calculable.

On utilise parfois plus spécifiquement le terme de fonctions récursives pour les fonctions récursives au sens de Kleene, ou fonction μ-récursives, l'une des définitions possibles de fonctions calculables, introduite par Kleene en 1936 qui laisse le calcul implicite. Cette définition généralise celle des fonctions récursives primitives.

Enfin les théorèmes de point fixe de Kleene, qui permettent entre autres de justifier l'utilisation des définitions récursives de fonctions (au sens premier de ce terme), sont également appelés théorèmes de la récursion.

Ensemble récursif

De façon cohérente avec la définition précédente, un ensemble récursif est un ensemble d'entiers naturels ou de n-uplets d'entiers naturels dont la fonction caractéristique est récursive. Cela signifie que l'on peut décider mécaniquement de l'appartenance ou non à cet ensemble. On dira également ensemble décidable, le problème de décision de l'appartenance ou non d'un entier, ou n-uplet d'entiers, à cet ensemble étant décidable. Un ensemble récursivement énumérable est un ensemble qui est l'ensemble de définition, ou de façon équivalente (à l'ensemble vide près), l'ensemble image, d'une fonction récursive partielle. L'équivalence se démontre en faisant intervenir le calcul de la fonction.

Via des codages à la Gödel, on peut généraliser ces notions aux langages formels. On parle par exemple de langage récursif ou décidable. En logique mathématique, une théorie récursive, ou théorie décidable est une théorie dont l'ensemble des théorèmes est récursif. Une théorie récursivement axiomatisable est une théorie pour laquelle on peut trouver un ensemble d'axiomes récursif, ou de façon équivalente, dont l'ensemble des théorèmes est récursivement énumérable.

Notes et références

  1. Depuis l'avènement de l'informatique, on dirait un programme.

Voir aussi

  • Portail de la programmation informatique Portail de la programmation informatique
  • Portail de la logique Portail de la logique
Ce document provient de « Fonction r%C3%A9cursive ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Fonction Récursive de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Fonction recursive — Fonction récursive Voir « récursif » sur le Wiktionnaire …   Wikipédia en Français

  • Fonction récursive — ● Fonction récursive fonction ayant certaines propriétés (de calculabilité notamment) définies, étudiées avec précision dans le cadre de la théorie de la récursivité …   Encyclopédie Universelle

  • Fonction récursive — Sur les autres projets Wikimedia : « Fonction récursive », sur le Wiktionnaire (dictionnaire universel) En informatique et en mathématiques, le terme fonction récursive désigne une classe de fonctions calculables, autrement dit de… …   Wikipédia en Français

  • Fonction Récursive Primitive — Une fonction récursive primitive est une fonction définie principalement à l aide de fonctions primitives de récursion et de composition. Ces fonctions constituent un sous ensemble des fonctions récursives. Elles ont été initialement analysées… …   Wikipédia en Français

  • Fonction recursive primitive — Fonction récursive primitive Une fonction récursive primitive est une fonction définie principalement à l aide de fonctions primitives de récursion et de composition. Ces fonctions constituent un sous ensemble des fonctions récursives. Elles ont… …   Wikipédia en Français

  • Fonction récursive primitive — Une fonction récursive primitive est une fonction définie principalement à l aide de fonctions primitives de récursion et de composition. Ces fonctions constituent un sous ensemble des fonctions récursives. Elles ont été initialement analysées… …   Wikipédia en Français

  • Fonction Imbriquée — Une fonction imbriquée ou fonction interne est une fonction encapsulée dans une autre. Elle ne peut être appelée que par la fonction englobante ou par des fonctions imbriquées directement ou non dans la même fonction englobante. En d autres… …   Wikipédia en Français

  • Fonction imbriquee — Fonction imbriquée Une fonction imbriquée ou fonction interne est une fonction encapsulée dans une autre. Elle ne peut être appelée que par la fonction englobante ou par des fonctions imbriquées directement ou non dans la même fonction englobante …   Wikipédia en Français

  • Fonction Calculable — Une fonction calculable (ou fonction récursive) est une fonction semi calculable (ou fonction partielle récursive) qui est aussi totale, c est à dire définie pour toute entrée (en tout point). Ce sont les fonctions calculées par une machine de… …   Wikipédia en Français

  • Fonction De Sudan — En Calculabilité, la fonction de Sudan est un exemple de fonction récursive mais non primitive récursive. Ceci est aussi le cas de la bien plus connue Fonction d Ackermann. Elle fut conçue en 1927 par le mathématicien roumain Gabriel Sudan élève… …   Wikipédia en Français


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.