ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Notions sur les fonctions récursives     » fonctions calculables , ensemble récursivement énumérables

Les termes récursif, récursion, récursivité ont la même racine latine que récurrence : currere = courir, et par là : recurrere = courir en arrière qui a donné également recourir, recours = action de faire appel (en justice).

• Le terme récurrence apparaît avec Poincaré dans La Science et L'hypothèse au tout début du 20è siècle. On parle dès lors de formule de récurrence, et de raisonnement par récurrence pour signifier le raisonnement par induction de Pascal.
  

• La récursivité n'apparaît dans le Larousse qu'en 1968 avec les progrès de l'informatique et des algorithmes récursifs : la notion actuelle de fonction (ou de procédure) récursive rencontrée en programmation se rattache à celle définie par Skolem (1923) puis Gödel (1926) sans en avoir exactement le même sens.

I - Les fonctions récursives en informatique :      

Une fonction ou procédure (ensemble de règles logiques) X est définie récursivement si sa définition est de la forme X = Φ(A, B, ..., X) où A, B, ... désignent des règles ou fonctions connues et Φ une fonction ou procédure combinant A, B, ... et X. C'est dire que X fait appel à elle-même pour se définir.

à cette relation générale, il faut associer une condition d'arrêt, s'apparentant généralement à une condition initiale. En cas d'oubli, la procédure pourrait boucler indéfiniment ou provoquer un dépassement de capacité...

• La fonction factorielle de n est définie récursivement dans N par :

function factorielle(n)
{
if (n<=1) return 1 else return n*factorielle(n-1)
}

L'instruction y = factorielle(4) retourne 1 × 2 × 3 × 4 dans la variable y. L'algorithme empile en mémoire les calculs intermédiaires 4*factorielle(3) | 4*3*factorielle(2) | 4*3*2*factorielle(1) | 4*3*2*1. La condition if (n<=1) return 1 est la condition d'arrêt effectivement calculable conduisant à y = 24. Ce petit algorithme renvoie 1 si n = 0 (convention 0! = 1! = 1).

Le propre d'une procédure récursive bien pensée est qu'elle généralement d'une admirable concision et n'utilise qu'un minimum de concepts extérieurs à sa définition.

 ➔  Il s'agit de bien distinguer récursion , récurrence et itération

♦  Définir une suite (u_n) par u_o = 1, u_n = 3u_n-1, c'est écrire une relation récurrente. Pour calculer u_n en fonction de n, il faut "courir en arrière" : reculer jusqu'à u_o (valeur initiale), en décrémentant n.

 u_n = 3u_n-1 = 3 × 3u_n-2 = 3 × 3 × 3u_n-3 = 3 × 3 × 3 × 3u_n-4 = ... =  3ⁿu_o

Mais u_n n'est autre qu'une fonction de n : u_n = f(n). En écrivant :

n∈N*, f(0) = 1, f(n) = 3f(n-1)

On définit une fonction récursive dans l'ensemble des entiers naturels, dont f(0) = 1 est la condition d'arrêt. On est donc en présence d'une procédure récursive de type récurrent conduisant à la fonction exponentielle de base 3 restreinte à N.  La fonction factorielle décrite précédemment est également récursive de type récurrent.

»  factorielle n , suite de Fibonacci , fonction d'Ackermann , Nombres de Fibonacci ,  Nombres de Lucas

♦  Le calcul du PGCD selon la méthode d'Euclide est une méthode récursive non récurrente :

1. PGCD(a,0) = a  (condition d'arrêt);

2. PGCD(a , b) = PGCD(b , r)   avec r = a - b × Ent(a/b), reste de la division de a par b.        

On réitère la formule récursive 2 tant que la condition d'arrêt r = 0 n'a pas lieu. Le pgcd est le dernier reste non nul : par exemple, d(24,18) = d(18,6) = d(6,0) = 6.

On remarque que dans les deux méthodes, le cas "général" s'obtient en revenant au cas initial par un processus bien défini au bout d'un nombre fini d'itérations.

♦  On parlera d'un algorithme itératif (du latin iterare = répéter) lorsqu'un résultat souhaité est obtenu en répétant (en réitérant) un même processus p_n pour des valeurs croissantes de n. En termes de programmation, on parle de boucle (for ... do ..., while ...).

II - Les procédures récursives en informatique :      

Le traitement récursif des chaînes de caractères est très efficace et très instructif de la puissance de la récursion par la simplicité de mise en œuvre. On pourra consulter quelques exemples donnés dans ChronoMath :

 » Inversion d'une chaîne , Tri d'une liste , Formule de Wallis (tableur) , Autres cas sur la page Ackermann

III - Les fonctions récursives en logique mathématique :      

C'est tout particulièrement à Gödel et Herbrand en 1930-31, puis Turing et Post, mais aussi Rózsa Péter et Kalmár en Hongrie, que l'on doit la mise en place du concept mathématique nouveau de fonction récursive dans leurs travaux relatifs aux fondements des mathématiques gravement ébranlés par les contradictions apparues dans la logique classique du tiers-exclu d'Aristote suite à l'apparition de la théorie des ensembles de Cantor.

Kronecker, qui affirmait « Dieu a créé les nombres entiers, le reste est l'œuvre de l'homme » avait prédit que la recherche mathématique devait s'appuyer exclusivement sur les propriétés des nombres entiers. Reconstruire les mathématiques à partir de N, ensemble des entiers naturels, source de toute la mathématique, nécessite donc une définition sans faille exempte de toute intuition susceptible de mettre à mal le futur édifice.

Les nombres réels, base de l'analyse, sont construits à partir des rationnels, quotients d'entiers, et les géométries reposent sur leurs métriques définies par des propriétés numériques, ce qui nous ramène encore aux entiers. Ce principe de construction se rencontre par exemple dans la mise en place de la fonction exponentielle :

Construction de la fonction exponentielle : »

 ➔  La validité et la puissance du concept de fonction et d'énoncés récursifs défini par Gödel en 1931 (et, indépendamment, par Jacques Herbrand, 1908-1931) réside dans sa totale indépendance de toute théorie mathématique existante, aspect évidemment fondamental lorsque l'objectif est de fonder une logique nouvelle suite aux failles des systèmes de pensée précédents. La seule connaissance admise et utilisée fut l'ensemble des entiers naturels que von Neumann s'amusera à définir récursivement...

Ambiguïté d'un vocabulaire pléthorique... :    

Dans les années 1930, un des objectifs était d'étudier la consistance des théories mathématiques et de la décidabilité de propositions énoncées en leur sein :

Dans une théorie T, une proposition p est décidable si l'on peut prouver, au moyen des axiomes de T, soit p soit non p.

Prouver p c'est établir au moyen de la logique de T (définie par ses axiomes et son langage) que non p est contradictoire en ce sens qu'elle impliquerait la la négation d'un axiome ou d'un énoncé (formule, proposition) déjà établi.

La validité de p consiste alors à exhiber une méthode effective de preuve, c'est à dire un algorithme aboutissant à p par l'usage d'un nombre fini « d'opérations » fondamentales. Les langages informatiques ayant emprunté les terme récursif (adjectif), récursivité (substantif associé) récursion (action récursive au sein d'un programme récursif) on préfère, en logique mathématique, parler aujourd'hui de fonction calculable (concept initié par Gödel) ou, plus précisément, de fonction effectivement calculable, pour signifier qu'il existe une méthode permettant de la calculer en un nombre fini d'opérations fondamentales. C'est le cas, par exemple,  de la définition du PGCD défini par Euclide.

Kleene qualifia de primitives (on dit aussi fondamentales) les premières fonctions récursives introduites par Skolem (1923). Augmentées des fonctions obtenues par son opération de minimum, dites μ-récursives (» ci-après), on parla de fonctions récursives partielles.

Après les travaux de Gödel et Herbrand et les résultats décisifs de Turing (1936) apportés par sa fameuse « machine à penser », on parla, avec Gödel, de fonctions récursives générales (Princeton, 1934) pour exprimer des définitions récursives composées de fonctions récursives primitives au sens de Kleene.

En 1936-37, Church et Kleene prouvent, au moyen de leurs fonctions λ-définissables et  μ-récursives (respectivement) clôturent le chapitre en prouvant que :

Les fonctions calculables sont les fonctions récursives générales lesquelles coïncident 
avec les fonctions calculables au sens de (la machine de) Turing.

En logique, les fonctions calculables sont désormais les fonctions récursives générales, ou récursives (tout court) : fonctions construites et obtenues au moyen d'un nombre fini d'étapes en utilisant les fonctions récursives primitives décrites ci-dessous. Après six années de recherches, il apparaissait donc que la calculabilité au sens de la pensée logique, sans rapport à l'informatique, inexistante à l'époque, coïncide avec la calculabilité "mécanique" ! C'est là un résultat à la fois remarquable et bouleversant auquel ne s'attendait certes pas Gödel dans un contexte philosophique du mécanisme de la pensée, ni Hilbert qui énonçait, au tout début du 20 siècle, ses célèbres 23 problèmes pour le (les ?) siècle(s) à venir.

Au fait, existe-t-il des fonctions non calculables ? Oui, mais elles sont "rares" pour ne pas dire tirées par les cheveux... On pourra consulter la réf.9 et l'exemple dit du castor affairé, (busy biver problem) qui empile les 1 (plutôt que les branchages...), une fonction qui boucle indéfiniment sur une machine de Turing. 

On suppose ici que l'ensemble N des entiers naturels est construit ou accepté dans son sens intuitif. Selon Kleene, les fonctions de N^p dans N, p ≥ 1, établies comme effectivement calculables depuis les premiers travaux de Skolem et Gödel sur le sujet, dites récursives primitives (appellation due à Skolem) sont les suivantes :

1. La fonction successeur (incrémentation) Incr : x → x⁺ qui à tout entier naturel x associe l'entier immédiatement supérieur. C'est donc x + 1, mais tant que l'addition n'est pas définie, cette déduction est illicite...
2. Les fonctions constantes F_c(x _l, ..., x_p) = c (entier) dont la fonction nulle.
3. Les fonctions projections P_i(x _l, ..., x_p) = x_i.
   Pour deux variables : P₂(x₁,x₂) = x₂, pour une variable : P₁(x₁) = x₁, c'est l'application identique.
4. Les fonctions obtenues par récurrence simple sur une des variables entières, par exemple x₁ : on suppose g récursive primitive, alors f définie par l'algorithme ci-dessous l'est aussi :
       a/ initialisation : f(0, x ₂, ..., x_p) = k, k donné dans N      » Raisonnement par induction
       b/ hérédité (ou induction) : f(n+1, x ₂, ..., x_p) = g(f(n, x₂, ..., x_p), x₂, ..., x_p)
5. Les fonctions obtenues par composition (on dit aussi par superposition) : si f et g sont récursives primitives, alors la fonction composée h définie par h(x _l, ..., x_p) = f(x _l, ...,g(x _l, ...,  x_p),...,  x_p) l'est aussi.
6. Les fonctions obtenues par l'opération de minimum (dû à Kleene) : si R(x _l, ...,  x_p) entre éléments de N, on désigne par (µx)R(x _l, ...,  x_p), mu comme minimum, le plus petit entier naturel x réalisant R(x _l, ...,  x_p), ce qui permet de construire de nouvelles fonctions.

La nature récursive de ces fonctions (au sens usuel de fonction se définissant en faisant appel à elle-même) n'apparaît peut-être pas clairement. Étudions les à travers des exemples plus concrets, les fonctions récursives élémentaires :

La fonction prédécesseur Decr (décrémentation, antécedent) :     

Si x est un entier naturel, son antécédent est 0 s'il est nul, sinon, c'est x - 1. Or, (x + 1) - 1 = x. On peut donc la définir très simplement au moyen de la fonction successeur par :

Decr0) = N(x)  (i.e. = 0, initialisation)
Decr(Incr(x)) = P₁(x)  (= x, récurrence simple).

• Ce qui peut s'écrire Dec(0) = 0 et Dec(n+1) = n. Il vient ainsi Decr(1) = Decr(0 + 1) = 0, Decr(2) = Decr(1 + 1) = 1, et ainsi de suite. L'algorithme correspondant procède par itération (boucle).

La fonction addition Add :     

Additionner y à x, c'est incrémenter x en décrémentant y jusqu'à obtenir 0. On peut la définir par récurrence :

Add(x,0) = P₁(x)  (i.e. = x, condition d'arrêt)
Add(x,y) = Incr(Add(x,Decr(y))

• Par exemple : Add(2,3) = Incr(Add(2,2)) = Add(2,2) + 1 = [Incr(Add(2,1)) + 1] + 1
                                       = [[Add(2,0) + 1] + 1] + 1
                                       = [[2 + 1] + 1] + 1 = [3 + 1] + 1 = 4 + 1 = 5.

Et on pose plus simplement : Add(x,y) = x + y.

La fonction soustraction Sous :     

La soustraction dans N définie par : S(x,y) = x - y si x ≥ y et 0 sinon, peut être définie par :

        Sous(x, 0) = x et Sous(x,y) = Decr(Sous(x,Decr(y))

• Par exemple : Sous(5,3) = Decr(Sous(5,2)) =  Decr(Decr(Sous(5,1)))
                                       = Decr(Decr(Decr(Sous(5,0)))) = Decr(Decr(Decr(5)))
                                       = Decr(Decr(4)) = Decr(3) = 2

La fonction multiplication M :    

M(x,y) = xy. Elle sera définie par :

M(x,0) = N(x)  (= 0, fonction nulle : condition d'arrêt)
M(x,y) = A(M(x,D(y)),P₁(x,y)) , c'est à dire x(y - 1) + x : appel récursif 

On définira alors facilement la fonction puissance entière.

En simplifiant : une partie X de N, et plus généralement de N^p, est dite récursive ou décidable pour signifier qu'il existe un algorithme permettant d'affirmer en un nombre fini d'étapes qu'un élément x de X appartient ou non à cet ensemble. Cela revient à dire que sa fonction caractéristique (égale à 1 dans X, 0 sinon) est calculable.

X est dit récursivement énumérable ou semi-décidable (définition due à Kleene), s'il existe une fonction récursive (autrement dit calculable) dont l'image est cet ensemble. Plus intuitivement : s'il existe un algorithme capable d'établir la liste de tous les éléments de X.

• Toute partie décidable est récursivement énumérable. Tout ensemble diophantien est récursivement énumérable. Inversement tout ensemble récursivement énumérable est diophantien : difficile résultat (étroitement lié au 10ème problème de Hilbert) étudié et prouvé de 1950 à 1970.

• Si X est semi-décidable ainsi que son complémentaire, alors X est décidable.

• N ainsi que toutes ses parties finies sont décidables.

• L'ensemble des nombres premiers est décidable.
• E = {(x,y,z)∈N³, x² + y² = z²} est décidable.
• F = {x∈2N, ∃ (p,q)∈N², p et q premiers, x = p + q} est décidable    »  Goldbach
• G = {(x,y,z,t)∈N⁴, x^t + y^t = z^t} est décidable.

• H = {t∈N, ∃ (x,y,z)∈N³, x^t + y^t = z^t}. H est l'image de G par la projection (x,y,z,t) → t, et p est manifestement calculable. Donc H est récursivement énumérable (semi-décidable). Avant la preuve de Wiles concernant l'ex conjecture de Fermat, H n'était pas décidable car aucune procédure n'était capable de prouver en un nombre fini d'étapes qu'un entier t donné appartient ou non à H.

Cette nouvelle vision permet d'exhiber sans ambiguïté, dans un contexte constructiviste, des objets mathématiques en un nombre fini d'étapes et conduisent au concept d'ensembles et de théories axiomatisables et décidables. Ces idées novatrices permettront de résoudre négativement le 10ème problème de Hilbert.

» Turing , Rózsa Péter , Ackermann , Church , Kleene

 ➔   Pour en savoir plus :

1. An early history of recursive functions ans computability, from Gödel to Turing, par Rod Adams, Docent Press - 2011
2. Techniques récursives en programmation, D.W. Barron, Éd. Dunod, Paris - 1970
3. Les bases de la programmation, Jacques Arsac, Éd. Dunod, Paris - 1982
4. Les Algorithmes par Patrice Hernert, Que sais-je n° 2928, Éd. P.U.F., Paris - 1995
5. par Douglas Hofstadter, Ed. InterEditions - Paris 1985
6. Logique mathématique, tome2 : Fonctions récursives, th. de Gödel, th.des ensembles, th. des modèles
   par René Cori, Daniel Lascar. Éd. Dunod, Paris, 2003.
7. Fonctions récursives, ensembles récursivement énumérables, effectivité par Andrzej Grzegorczyk
   Collection logique mathématique Série A, Paris Gauthier-Villars, 1961.
8. Itération et récursivité par Jacques Arsac : http://hal.archives-ouvertes.fr/docs/00/35/91/90/PDF/d14p081.pdf
9. La théorie des fonctions récursives et ses applications, par D. Lacombe (Bulletin de la SMF,1960)
   http://archive.numdam.org/article/BSMF_1960__88__393_0.pdf
10. Histoire d'algorithmes : Du caillou à la puce, par une équipe d'enseignants (IREM, IUFM, CNRS).
    Éd. Belin - Collection Regards sur la science - 1993
11. a) Machines de Turing, Calculabilité et décidabilité, cours d'Alain Lecomte, univ. Paris VIII :
    http://lecomte.al.free.fr/ressources/LIC_MIASS/coursTuring.pdf
    b) Fonctions récursives et Machines de Turing , cours et exercices de Nhan Le Tanh (Univ. Nice) :
    http://www.i3s.unice.fr/~nlt/cours/licence/it/s5_itdut_poly.pdf
12. Algorithmique et Calculabilité (Université de Liège) : http://www.discmath.ulg.ac.be/cours/main_calcul.pdf
13. Ensembles récursivement énumérables et 10è problème de Hilbert :  http://www.mathkang.org/cite/confC01.html
14. Ensembles récursivement énumérables et théorème de Gödel : cours de Jean Betrema : http://www.labri.fr/perso/betrema/MC/MC4.html
15. Théorie de la démonstration : Wikipédia, Portail de la logique : http://fr.wikipedia.org/wiki/Th%C3A9orie_de_la_dC3%A9monstration
16. ABRÉGÉ D'HISTOIRE DES MATHÉMATIQUES, 1700-1900, Jean Dieudonné, Ch.11, §5, par Marcel Guillaume. Ed. Hermann, Paris, 1978-1992.
17. La machine de Turing, théorie des nombres calculables, fonctions récursives, suivie d'une application au problème de la décision, Les machines peuvent-elles penser ? par Alan Turing (traduit de l'anglais).
18. Un livre superbe, à lire dans le calme... : Gödel, Escher, Bach, les Brins d'une Guirlande Eternelle