Fonction récursive
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

En informatique et en mathématiques, le terme fonction récursive désigne deux concepts liés, mais distincts. Plus généralement les termes " récursif ", " récursivement ", " récursion ", " récursivité ", peuvent faire référence suivant le contexte (Le contexte d'un évènement inclut les circonstances et conditions qui l'entourent; le contexte d'un mot, d'une phrase ou d'un texte inclut les mots qui l'entourent. Le concept de contexte issu traditionnellement de l'analyse...) à l'une ou l'autre des deux notions.

Logique (La logique (du grec logikê, dérivé de logos (λόγος), terme inventé par Xénocrate signifiant à la fois raison, langage, et raisonnement) est dans une première...) informatique (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le traitement automatique de l'information par des machines telles que...) et paradigmes de programmation (La programmation dans le domaine informatique est l'ensemble des activités qui permettent l'écriture des programmes informatiques. C'est une étape importante de la conception de logiciel (voire de matériel,...)

Du point (Graphie) de vue (La vue est le sens qui permet d'observer et d'analyser l'environnement par la réception et l'interprétation des rayonnements lumineux.) de la programmation, une fonction récursive (En informatique et en mathématiques, le terme fonction récursive désigne deux concepts liés, mais distincts. Plus généralement les termes « récursif », « récursivement », « récursion »,...) est une fonction, au sens (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine....) informatique de ce terme, qui peut s'appeler elle-même au cours de son exécution. On parle également de définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.) récursive, d'appel récursif de fonction, etc. voir l'article détaillé algorithme récursif.

Logique mathématique (La logique mathématique est née à la fin du XIXe siècle de la logique au sens philosophique du terme. Ses débuts furent marqués par la rencontre entre deux idées nouvelles :) (Calculabilité)

Fonction récursive

En théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée ou une connaissance spéculative, souvent basée sur l’observation...) de la calculabilité (La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est une branche de la logique mathématique et de l'informatique théorique. Alors que la notion intuitive de fonction...) (on dit aussi récursivité !), une fonction récursive est une fonction à un ou plusieurs arguments entiers, qui peut se calculer en tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) point par une procédure mécanique (Dans le langage courant, la mécanique est le domaine des machines, moteurs, véhicules, organes (engrenages, poulies, courroies, vilebrequins, arbres de...), par un programme peut-on dire depuis l'avènement de l'informatique. 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 (Les fonctions partielles récursives correspondent aux fonctions calculées par une machine de Turing. Selon la thèse de Church la classe des fonctions...) définie en tout point. On trouve de plus en plus souvent le terme de 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...) 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 (Le rendu est un processus informatique calculant l'image 2D (équivalent d'une photographie) d'une scène créée dans un logiciel de modélisation 3D comportant à la fois des objets et des sources de...) 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 (Stephen Cole Kleene (né le 5 janvier 1909 à Hartford, mort le 25 janvier 1994) est un mathématicien et logicien états-unien.), de cette définition avec celle des fonctions λ-calculables et des fonctions calculables par machine de Turing fournit des arguments pour la thèse (Une thèse (du nom grec thesis, se traduisant par « action de poser ») est l'affirmation ou la prise de position d'un locuteur, à l'égard du sujet ou du thème qu'il évoque.) 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 (En mathématiques, pour une application f d’un ensemble E dans lui-même, un élément x de E est un point fixe de f si f(x) = x.) de Kleene, qui permettent entre autre 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 (En théorie de la calculabilité, un ensemble récursif ou ensemble décidable est un ensemble d'entiers (ou d'éléments facilement codables dans les entiers) dont la fonction caractéristique est une fonction récursive au sens de la...)

De façon cohérente avec la définition précédente, un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise...) récursif est un ensemble d'entiers naturels ou de n-uplets d'entiers naturels dont la fonction caractéristique (On rencontre des fonctions caractéristiques dans plusieurs domaines :) 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 (En logique mathématique, le terme décidabilité recouvre deux concepts liés : la décidabilité logique et la décidabilité algorithmique.), le problème de décision (En logique mathématique, on appelle problème de la décision le fait de déterminer de façon mécanique, par un algorithme, si un énoncé est un théorème...) de l'appartenance ou non d'un entier, ou n-uplet (En mathématiques, si n est un entier naturel non nul alors un n-uplet est une collection de n objets tel qu'il soit possible de dire exactement celui qui est le premier élément, le second élément, ..., le nème. Les...) d'entiers, à cet ensemble étant décidable. Un ensemble récursivement énumérable (Intuitivement un ensemble est récursivement énumérable s'il existe un procédé mécanique (en gros qui peut être réalisé par un ordinateur) qui liste ses éléments. On dirait aussi qu'il existe un «programme» qui peut...) est un ensemble qui est l'ensemble de définition (En mathématiques, l' ensemble de définition D f  d'une fonction  f  dont l' ensemble de départ est noté  E  et l' ensemble d'arrivée  F , est l'ensemble des antécédents de f, c'est-à-dire...), ou de façon équivalente (à l'ensemble vide (En mathématiques, l'ensemble vide est l'ensemble ne contenant aucun élément.) 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 (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les...), 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.

Page générée en 0.156 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique