Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Définition par récurrence
Résumé
vignette|4 étapes de la construction d'un flocon de Koch. Comme beaucoup d'autres fractales, cette courbe est définie par récurrence.
En mathématiques, on parle de définition par récurrence pour une suite, c'est-à-dire une fonction définie sur les entiers positifs et à valeurs dans un ensemble donné. Une fonction est définie par récurrence quand, pour définir la valeur de la fonction en un entier donné, on utilise les valeurs de cette même fonction pour des entiers strictement inférieurs. À la différence d'une définition usuelle, qui peut être vue comme une simple abréviation, une définition par récurrence utilise le nom de l'objet défini (la fonction en l'occurrence) dans la définition même.
Le principe de définition par récurrence assure l'existence et l'unicité de la fonction ainsi définie. Il est distinct de celui du raisonnement par récurrence, dont il n'est pas conséquence sans les autres axiomes de Peano. Richard Dedekind l'identifie et en donne une démonstration en 1888 dans son ouvrage Was sind und was sollen die Zahlen ? (« Que sont et à quoi servent les nombres ? »), qui utilise une axiomatisation des entiers dans un cadre ensembliste.
Les définitions par récurrence se généralisent aux ordinaux et ensembles bien ordonnés, et plus généralement aux relations bien fondées. On parle également de définition par induction (sur les entiers positifs, sur tel bon ordre, sur les ordinaux). Elle se généralise aussi aux objets structurés (par exemple les arbres binaires ou les termes), on parle alors de récurrence structurelle ou d'induction structurelle et elle est particulièrement utilisée en informatique pour définir des fonctions (par exemple la taille).
L'ensemble des entiers naturels (on dira simplement entiers) est noté N. Étant donnés un ensemble E, un élément a de E et une fonction h de N × E dans E,
la fonction f de N dans E définie par récurrence à partir de a et h
est l'unique fonction qui vérifie :
f(0) = a et pour tout entier naturel n, f(n + 1) = h(n, f(n)).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Personnes associées (4)
Concepts associés (10)
Logique
La logique — du grec , qui est un terme dérivé de signifiant à la fois « raison », « langage » et « raisonnement » — est, dans une première approche, l'étude de l'inférence, c'est-à-dire des règles formelles que doit respecter toute argumentation correcte. Le terme aurait été utilisé pour la première fois par Xénocrate. La logique antique se décompose d'abord en dialectique et rhétorique. Elle est depuis l'Antiquité l'une des grandes disciplines de la philosophie, avec l'éthique (philosophie morale) et la physique (science de la nature).
Récursivité
La récursivité est une démarche qui fait référence à l'objet même de la démarche à un moment du processus. En d'autres termes, c'est une démarche dont la description mène à la répétition d'une même règle.
Formule logique
En logique on dit d’une suite finie de lettres qu’elle est une formule, ou parfois formule bien formée, d'un langage logique donné lorsqu’elle peut être construite en appliquant une combinaison des règles de la grammaire formelle associée, on parle de la syntaxe du langage. Informellement les formules sont les assemblages de lettres auxquels il est possible de donner une signification en termes de valeur de vérité (Vrai, ou Faux). Les formules logiques sont l'équivalent des phrases du langage naturel.