Définition récursive - Recursive definition

Quatre étapes dans la construction d'un flocon de neige Koch . Comme pour beaucoup d'autres fractales , les étapes sont obtenues via une définition récursive.

En mathématiques et en informatique , une définition récursive , ou définition inductive , est utilisée pour définir les éléments d'un ensemble en termes d'autres éléments de l'ensemble ( Aczel 1977: 740ff). Voici quelques exemples d'objets récursive définissables comprennent factorielles , nombres naturels , les nombres de Fibonacci , et l' ensemble de Cantor ternaire .

Une définition récursive d'une fonction définit les valeurs de la fonction pour certaines entrées en termes de valeurs de la même fonction pour d'autres entrées (généralement plus petites). Par exemple, la fonction factorielle n ! est défini par les règles

0! = 1.

( n + 1)! = ( n + 1) · n !.

Cette définition est valable pour chaque entier naturel n , car la récursivité atteint finalement le cas de base de 0. La définition peut aussi être considérée comme donnant une procédure pour calculer la valeur de la fonction  n !, En partant de n  = 0 et en continuant en avant avec n  = 1, n  = 2, n  = 3 etc.

Le théorème de récursivité stipule qu'une telle définition définit en effet une fonction qui est unique. La preuve utilise l'induction mathématique .

Une définition inductive d'un ensemble décrit les éléments d'un ensemble en termes d'autres éléments de l'ensemble. Par exemple, une définition de l'ensemble N d' entiers naturels est:

1. 1 est en N .
2. Si un élément n est N alors n  + 1 est en N .
3. N est l'intersection de tous les ensembles satisfaisant (1) et (2).

Il existe de nombreux ensembles qui satisfont (1) et (2) - par exemple, l'ensemble {1, 1.649, 2, 2.649, 3, 3.649, ...} satisfait la définition. Cependant, la condition (3) spécifie l'ensemble des nombres naturels en supprimant les ensembles avec des membres étrangers. Notez que cette définition suppose que N est contenu dans un ensemble plus grand (tel que l'ensemble des nombres réels) - dans lequel l'opération + est définie.

Les propriétés des fonctions et ensembles définis récursivement peuvent souvent être prouvées par un principe d'induction qui suit la définition récursive. Par exemple, la définition des nombres naturels présentée ici implique directement le principe de l'induction mathématique pour les nombres naturels: si une propriété tient du entier naturel 0 (ou 1), et que la propriété vaut n +1 chaque fois qu'elle vaut n , alors la propriété est valable pour tous les nombres naturels (Aczel 1977: 742).

Forme des définitions récursives

La plupart des définitions récursives ont deux fondements: un cas de base (base) et une clause inductive.

La différence entre une définition circulaire et une définition récursive est qu'une définition récursive doit toujours avoir des cas de base , des cas qui satisfont la définition sans être définis en termes de définition elle-même, et que toutes les autres instances des clauses inductives doivent être "plus petites" dans un certain sens (c'est-à-dire plus proche de ces cas de base qui terminent la récursivité) - une règle également connue sous le nom de "se reproduire uniquement avec un cas plus simple".

En revanche, une définition circulaire peut ne pas avoir de cas de base, et peut même définir la valeur d'une fonction en termes de cette valeur elle-même - plutôt qu'en fonction d'autres valeurs de la fonction. Une telle situation conduirait à une régression infinie .

Que les définitions récursives soient valides - ce qui signifie qu'une définition récursive identifie une fonction unique - est un théorème de la théorie des ensembles connu sous le nom de théorème de récursivité , dont la preuve n'est pas triviale. Lorsque le domaine de la fonction est les nombres naturels, les conditions suffisantes pour que la définition soit valide sont que la valeur de f (0) (c'est-à-dire le cas de base) soit donnée, et que pour n > 0 , un algorithme soit donné pour déterminer f ( n ) en termes de n , f (0), f (1),…, f ( n - 1) (ie, clause inductive).

Plus généralement, des définitions récursives de fonctions peuvent être faites chaque fois que le domaine est un ensemble bien ordonné , en utilisant le principe de la récursivité transfinie . Les critères formels de ce qui constitue une définition récursive valide sont plus complexes pour le cas général. Un aperçu de la preuve générale et les critères se trouve dans James Munkres de Topology . Cependant, un cas spécifique (le domaine est limité aux entiers positifs au lieu de tout ensemble bien ordonné) de la définition récursive générale sera donné ci-dessous.

Principe de définition récursive

Laissez - A un ensemble et laisser un ₀ un élément de A . Si ρ est une fonction qui affecte à chaque fonction f mappant une section non vide des entiers positifs dans A , un élément de A , alors il existe une fonction unique telle que ${\ displaystyle h: \ mathbb {Z} _ {+} \ à A}$

${\ displaystyle h (1) = a_ {0}}$

${\ displaystyle h (i) = \ rho (h | _ {\ {1,2, \ ldots, i-1 \}}) {\ text {pour}} i> 1.}$

Exemples de définitions récursives

Fonctions élémentaires

L'addition est définie de manière récursive en comptant comme

${\ displaystyle 0 + a = a,}$

${\ Displaystyle (1 + n) + a = 1 + (n + a).}$

La multiplication est définie de manière récursive comme

${\ displaystyle 0a = 0,}$

${\ Displaystyle (1 + n) a = a + na.}$

L'exponentiation est définie de manière récursive comme

${\ displaystyle a ^ {0} = 1,}$

${\ displaystyle a ^ {1 + n} = aa ^ {n}.}$

Les coefficients binomiaux peuvent être définis de manière récursive comme

${\ displaystyle {\ binom {a} {0}} = 1,}$

${\ displaystyle {\ binom {1 + a} {1 + n}} = {\ frac {(1 + a) {\ binom {a} {n}}} {1 + n}}.}$

nombres premiers

L'ensemble des nombres premiers peut être défini comme l'ensemble unique d'entiers positifs satisfaisant

• 1 n'est pas un nombre premier,
• tout autre entier positif est un nombre premier si et seulement s'il n'est pas divisible par un nombre premier plus petit que lui-même.

La primalité de l'entier 1 est le cas de base; vérifier la primalité de tout entier plus grand X par cette définition nécessite de connaître la primalité de chaque entier entre 1 et X , ce qui est bien défini par cette définition. Ce dernier point peut être prouvé par récurrence sur X , pour laquelle il est essentiel que la seconde clause dise «si et seulement si»; s'il avait dit simplement "si", la primauté de, par exemple, 4 ne serait pas claire, et la poursuite de l'application de la deuxième clause serait impossible.

Nombres pairs non négatifs

Les nombres pairs peuvent être définis comme consistant en

• 0 est dans l'ensemble E des évens non négatifs (clause de base),
• Pour tout élément x de l'ensemble E , x  + 2 est dans E (clause inductive),
• Rien n'est dans E à moins qu'il ne soit obtenu à partir des clauses de base et inductives (clause extrémale).

Formules bien formées

C'est principalement dans la logique ou la programmation informatique que se trouvent les définitions récursives. Par exemple, une formule bien formée (wff) peut être définie comme:

1. un symbole qui représente une proposition - comme p signifie «Connor est un avocat».
2. Le symbole de négation, suivi d'un wff - comme Np signifie "Ce n'est pas vrai que Connor est un avocat."
3. L'un des quatre connecteurs binaires ( C , A , K ou E ) suivi de deux wff. Le symbole K signifie «les deux sont vrais», donc Kpq peut signifier «Connor est un avocat, et Mary aime la musique».

L'intérêt d'une telle définition récursive est qu'elle peut être utilisée pour déterminer si une chaîne particulière de symboles est "bien formée".

• Kpq est bien formé, car c'est K suivi des wff atomiques p et q .
• NKpq est bien formé, car c'est N suivi de Kpq , qui est à son tour un wff.
• KNpNq est K suivi de Np et Nq ; et Np est un wff, etc.

Voir également

• Induction mathematique
• Types de données récursifs
• Récursion
• Induction structurelle

Remarques

Les références

• Halmos, Paul (1960). Théorie des ensembles naïve . van Nostrand . OCLC   802530334 .
• Aczel, Peter (1977). "Une introduction aux définitions inductives". Dans Barwise, J. (éd.). Manuel de logique mathématique . Études de logique et fondements des mathématiques. 90 . Hollande du Nord . 739–782. doi : 10.1016 / S0049-237X (08) 71120-0 . ISBN   0-444-86388-5 .
• Hein, James L. (2010). Structures discrètes, logique et calculabilité . Jones et Bartlett . ISBN   978-0-7637-7206-2 . OCLC   636352297 .