La première axiomatisation de l'arithmétique est dûe à Giuseppe Peano en 1888. Elle est basée sur une fonction successeur parfois notée S et qui est l'addition de 1 :
def S(n): assert n==int(n) and n>=0 return n+1
Parmi les axiomes de Peano il y a celui disant qu'un
seul entier naturel n'est le successeur d'aucun autre.
Peano le notait 1 mais aujourd'hui on considère que
c'est 0. On a alors 1==S(0)
.
Peano utilise également la fonction prédécesseur
notée P
et telle que pour tout entier non nul n
on
a P(n)==n-1
:
def P(n): assert n==int(n) and n>0 return n-1
Peano définit l'addition add
de cette manière :
def add(a,b): if b==0: return a else: return S(add(a,P(b)))
La définition de la multiplication par Peano est, elle aussi, récursive :
def mul(a,b): if b==0: return 0 else: return add(mul(a,P(b)),a)
La définition de la puissance par Peano ressemble à
def pot(a,b): if b==0: return 1 else: return mul(pot(a,P(b)),a)
Elle est donc elle aussi, récursive.
La définition d'une liste d'entiers selon McCarthy (fin des années 1950) est récursive : une liste d'entiers est formée de :
car
de la liste)cdr
de la liste,
ou suite)Par exemple, la liste [0,1,2,3,5,8]
a
pour car
l'entier 0
et pour cdr
la liste [1,2,3,5,8]
.
La définition est récursive parce que la suite de la liste est elle-même une liste d'entiers :
class Liste(): def __init__(self,entier,suite=None): self.entier = entier self.suite = suite def car(self): return self.entier def cdr(self): return self.suite
Avoir une définition récursive, permet de facilement obtenir des algorithmes récursifs.
Pour accrocher un train à la fin d'un autre train,
def accrocher(self,liste): if self.cdr() is None: self.suite = liste else: self.cdr().accrocher(liste)
De même, la longueur d'une liste d'entiers, ses extrema, sa somme et le mapping d'une fonction à la liste sont programmables récursivement.
Même l'affichage d'une liste peut se programmer récursivement :
car
de la liste,cdr
(qui est une liste) :def __repr__(self): if self is None: return '' else: gauche = str(self.entier) milieu = '→' droite = str(self.suite).replace('None','⊥') return gauche + milieu + droite
Par exemple, avec
L = Liste(0) for n in [1,2,3,5,8]: L.accrocher(Liste(n))
on dessine 0→1→2→3→5→8→⊥
qui correspond
à l'affichage façon McCarthy.
Un arbre binaire aussi peut être défini récursivement (c'est même la meilleure façon de le définir). Pour définir un arbre binaire d'entiers on peut faire
class Arbre(): def __init__(self,entier,père=None,mère=None): self.entier = entier self.père = père self.mère = mère def get_int(self): return self.entier def get_gauche(self): return self.père def get_droite(self): return self.mère def greffe_gauche(self,arbre): self.père = arbre def greffe_droite(self,arbre): self.mère = arbre def __repr__(self): if self is None: return '' else: gauche = str(self.père).replace('None',"`") milieu = '↖'+str(self.entier)+'↗' droite = str(self.mère).replace('None',"'") return gauche+milieu+droite
qui, avec
a = Arbre(1) a.greffe_gauche(Arbre(2)) a.greffe_droite(Arbre(3))
donne l'affichage `↖2↗'↖1↗`↖3↗'
évoquant
l'arbre binaire avec la racine 1 en bas :
`↖2↗ ↖3↗' ↖1↗
L'affichage (ici, par parcours infixe) est récursif, mais surtout parce que la définition elle-même est récursive.
Un arbre binaire d'entiers, c'est
père
),
qui est lui -même un arbre d'entiers,mère
),
qui est lui -même un arbre d'entiers.Cette définition est elle-même récursive puisque les deux enfants d'un arbre binaire sont eux-mêmes des arbres binaires (sauf s'ils sont vides). Le vocabulaire utilisé ici vient de la généalogie.
Pour avoir l'arbre généalogique d'une personne,
En généalogie, il est traditionnel de donner à la racine le numéro 1, et
Par exemple la grand-mère maternelle d'un ancêtre
de numéro n
, a pour numéro
2(2n+1)+1 = 4n+3
.
On en déduit les définitions récursives suivantes :
Ces notions sont donc aisément traitées par des langages favorisant les définitions récursives comme Prolog ou Haskell...