Définitions récursives

I/ Arithmétique

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

1) Addition

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)))

2) Multiplication

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)

3) Puissances

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.

II/ Listes d'entiers

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 :

• un entier (le car de la liste)
• une liste d'entiers (le 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].

1) Définition

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.

2) Concaténation

Pour accrocher un train à la fin d'un autre train,

• Si le premier train se réduit à la locomotive, on accroche le second train directement à la locomotive.
• Sinon on accroche le second train au bout du premier.

    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.

3) Représentation

Même l'affichage d'une liste peut se programmer récursivement :

• On affiche le car de la liste,
• puis on affiche son 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.

III/ Arbres binaires

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.

1) Arbre binaire

Un arbre binaire d'entiers, c'est

• un entier
• un enfant gauche (ici appelé père), qui est lui -même un arbre d'entiers,
• un enfant droit (ici appelé 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.

2) Arbre généalogique

Pour avoir l'arbre généalogique d'une personne,

• On prend pour racine de l'arbre, la personne,
• on greffe en haut à gauche, l'arbre généalogique du père,
• on greffe en haut à droite, l'arbre généalogique de la mère.

En généalogie, il est traditionnel de donner à la racine le numéro 1, et

• le numéro du père est le double du numéro de la personne.
• le numéro de la mère est le double augmenté de 1, du numéro de la personne.

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.

3) Ancêtres et descendants

On en déduit les définitions récursives suivantes :

a) Ancêtres

• Toute personne est son propre ancêtre.
• Les ancêtres des parents d'une personne, sont également des ancêtres de la personne.

b) Descendants

• Toute personne est son propre descendant.
• Les descendants des enfants sont également des descendants des parents.

Ces notions sont donc aisément traitées par des langages favorisant les définitions récursives comme Prolog ou Haskell...