Récursivité

I/ Diviser pour régner

1) Tri par fusion

(Von Neumann, Goldstine 1947)

Le tri par fusion est un des algorithmes de tri les plus rapides connus. Il est particulièrement rapide si la taille de la liste à trier est une puissance de 2. Il se fait par ces deux étapes :

• (diviser) on divise la liste en deux parties (de même longueur len(L)//2 dans le cas présent) ;
• on trie (récursivement) chaque moitié ;
• (régner) on réunit les solutions des deux sous-problèmes en une solution au problème de départ.

2) Fusion

Pour fusionner deux listes M et N (supposées déjà triées), on construit une liste L en plaçant dans l'ordre les éléments extraits de M et N :

def fusion(M: list,N: list) -> list:
    assert M==sorted(M) and N==sorted(N)
    L = []
    while len(M) and len(N):
        print(L,M,N)
        if M[0]<N[0]:
            L.append(M.pop(0))
        else:
            L.append(N.pop(0))
    if len(M)==0:
        L += N
    else:
        L += M
    return L

Le nombre de comparaisons, enfilements et défilements est la longueur (supposée commune) des deux listes à fusionner. La longueur de ces listes (au cours de la fusion) est un variant et le fait que L est et reste triée au cours de la fusion, est un invariant : la fusion est correcte, se termine et est de coût linéaire.

3) Tri

L'algorithme de tri par fusion se code alors ainsi :

def tri1(L: list) -> list:
    M = [L[i] for i in range(len(L)//2)]
    N = [L[i] for i in range(len(L)//2,len(L))]
    M.sort()
    N.sort()
    return fusion(M,N)

Mais l'efficacité de ce tri vient de l'utilisation de la récursivité.

4) Version récursive

def tri2(L: list) -> list:
    if len(L)<=1:
        return L
    else:
        M = [L[i] for i in range(len(L)//2)]
        N = [L[i] for i in range(len(L)//2,len(L))]
        M = tri2(M)
        N = tri2(N)
        return fusion(M,N)

5) Propriétés

a) Terminaison

En prenant comme variant la longueur des moitiés de liste, on prouve la terminaison de l'algorithme : cette longueur est divisée par 2 à chaque appel récursif.

b) Correction

L'invariant « la liste fusionnée est triée » permet de prouver que le tri par fusion est correct. C'est un invariant parce que

• Une liste constituée d'une seule carte est triée.
• Si les deux listes à fusionner sont triées, la liste fusionnée l'est également.

Par contagion, le tri par fusion est bien un tri.

c) Complexité

Pour une liste de longueur 16, on effectue

• 2 appels de fonction sur des listes de longueur 8,
• 4 appels de fonction sur des listes de longueur 4,
• 8 appels de fonction sur des listes de longueur 2,
• et 16 appels de fonction sur des listes de longueur 1.

2+4+8+16=30 est plus petit que le double de 16 : le nombre d'appels de fonction est linéaire par rapport à la taille de la liste à trier.

• Pour fusionner 16 listes de longueur 1 (pour obtenir 8 listes de longueur 2), on effectue 8×1=8 comparaisons.
• Pour fusionner 8 listes de longueur 2 (pour obtenir 4 listes de longueur 4), on effectue 4×2=8 comparaisons.
• Pour fusionner 4 listes de longueur 4 (pour obtenir 2 listes de longueur 8), on effectue 2×4=8 comparaisons.
• Pour fusionner 2 listes de longueur 8 (pour obtenir 1 liste de longueur 2), on effectue 8 comparaisons.

Le nombre de comparaisons est donc 8×4=32. C'est la moitié de 16×4=16×log₂(16) : le coût de l'algorithme de tri par fusion est n×log(n).

Un théorème dit qu'il n'existe aucun algorithme de tri qui soit plus rapide (de coût inférieur) que le tri par fusion.

II/ Programmation dynamique

1) Rendu de monnaie

Influencés par une civilisation extraterrestre, les Atlantes n'effectuaient leurs achats qu'avec 3 sortes de pièces d'or :

• la pièce d'un drachme atlante : ①
• la pièce de 3 drachmes atlantes : ③
• et la pièce de 4 drachmes atlantes : ④

Comment faire l'appoint sur un certain nombre de drachmes atlantes, en utilisant le moins de pièces d'or possibles ?

2) Algorithme glouton

On rappelle ce qui a été vu en 1ère à ce sujet : l'algorithme glouton consiste, en Atlantide, à donner

• d'abord le plus de pièces de 4 drachmes atlantes possible,
• ensuite le plus de pièces de 3 drachmes atlantes possible,
• puis au besoin finir par des pièces d'un drachme atlante.

Le nombre de pièces de chaque sorte est un attribut de la tirelire de chaque Atlante :

class Tirelire():
    def __init__(self,un=0,trois=0,quatre=0):
        self.un = un
        self.trois = trois
        self.quatre = quatre
    def __repr__(self):
        aff = '('+str(self.un)+'① , '+str(self.trois)+'③ ,'+str(self.quatre)+'④ )'
        return aff

L'algorithme glouton peut être récursif :

def rendu(centimes):
    if centimes>=4:
        bourse = rendu(centimes-4)
        bourse.quatre += 1
        return bourse
    elif centimes>=3:
        bourse = rendu(centimes-3)
        bourse.trois += 1
        return bourse
    elif centimes>=1:
        bourse = rendu(centimes-1)
        bourse.un += 1
        return bourse
    else:
        return Tirelire()

Pour vérifier l'effet on se propose d'enrichir l'affichage de la tirelire, afin de vérifier la somme de monnaie et aussi de voir le nombre total de pièces :

class Tirelire():
    def __init__(self,un=0,trois=0,quatre=0):
        self.un = un
        self.trois = trois
        self.quatre = quatre
    def pièces(self):
        return self.un+self.trois+self.quatre
    def total(self):
        return self.un+3*self.trois+4*self.quatre
    def __repr__(self):
        aff = '('+str(self.un)+'① , '+str(self.trois)+'③ ,'+str(self.quatre)+'④ )'
        aff += ' total '+str(self.total())+' cents en '+str(self.pièces())+' pièces'
        return aff

En faisant

for n in range(6,15):
    print(rendu(n))

On constate que l'algorithme fait l'appoint :

(2① , 0③ ,1④ ) total 6 cents en 3 pièces
(0① , 1③ ,1④ ) total 7 cents en 2 pièces
(0① , 0③ ,2④ ) total 8 cents en 2 pièces
(1① , 0③ ,2④ ) total 9 cents en 3 pièces
(2① , 0③ ,2④ ) total 10 cents en 4 pièces
(0① , 1③ ,2④ ) total 11 cents en 3 pièces
(0① , 0③ ,3④ ) total 12 cents en 3 pièces
(1① , 0③ ,3④ ) total 13 cents en 4 pièces
(2① , 0③ ,3④ ) total 14 cents en 5 pièces

Mais il ne le fait pas de façon optimale :

• Il rend 6 cents en 3 pièces ④①① alors qu'on pouvait le faire en seulement deux pièces.
• Il rend 14 drachmes atlantes (ou cents) en 5 pièces ④④④①① alors qu'on pouvait le faire en seulement 4 pièces.

3) Algorithme optimal

Dans cette variante, on cherche à ajouter le moins de pièces possible. Pour cela on regarde d'abord les cas les plus simples :

• Pour un montant inférieur à 3, on ne peut payer qu'en pièces de ① cent, on a donc la solution au problème.
• Pour un montant de 3 cents, on peut payer en une seule pièce de ③ et il est évident que cette solution est optimale.
• Pour un montant d'au moins 4, on regarde la meilleure solution parmi
  • 1 cent de moins
  • 3 cents de moins
  • 4 cents de moins
  que le montant à rendre, on choisit cette meilleure solution puis on lui ajoute une pièce de ① , de ③ ou de ④ selon la meilleure solution choisie.

def rendu(cents):
    if cents<3:
        return Tirelire(cents,0,0)
    elif cents==3:
        return Tirelire(0,1,0)
    else:
        t1 = rendu(cents-1)
        t3 = rendu(cents-3)
        t4 = rendu(cents-4)
        if t4.pièces()<t3.pièces():
            t4.quatre += 1
            return t4
        elif t3.pièces()<t1.pièces():
            t3.trois += 1
            return t3
        else:
            t1.un += 1
            return t1

On obtient bien un résultat optimal :

(0① , 2③ ,0④ ) total 6 cents en 2 pièces
(0① , 1③ ,1④ ) total 7 cents en 2 pièces
(0① , 0③ ,2④ ) total 8 cents en 2 pièces
(1① , 0③ ,2④ ) total 9 cents en 3 pièces
(0① , 2③ ,1④ ) total 10 cents en 3 pièces
(0① , 1③ ,2④ ) total 11 cents en 3 pièces
(0① , 0③ ,3④ ) total 12 cents en 3 pièces
(1① , 0③ ,3④ ) total 13 cents en 4 pièces
(0① , 2③ ,2④ ) total 14 cents en 4 pièces

Cet algorithme résout le problème, mais il prend beaucoup de temps pour cela. Pour le voir, on dessine l'arbre des appels de fonction (pour l'argument 8):

Les feuilles de l'arbre sont les appels de fonction non récursifs. On compte que la fonction rendu est appelée

• 4 fois avec l'argument 0,
• 6 fois avec l'argument 1
• 3 fois avec l'argument 2,
• 6 fois avec l'argument 3,
• 4 fois avec l'argument 4,
• 2 fois avec l'argument 5,
• une seule fois pour chacun des arguments 6, 7 et 8.

Cela fait 28 appels avec seulement 9 valeurs différentes de l'argument passé à la fonction. La programmation dynamique (Richard Bellman, 1954) consiste à minimiser le nombre d'appels de fonction, en remplaçant l'arbre par un graphe orienté :

4) Mémoïsation

Pour ce faire, on remplace les appels à la fonction (sauf le premier) par une lecture en mémoire.

def rendu(cents):
    vu = []
    for k in range(cents+1):
        if k<3:
            vu += [(k,0,0)]
        elif k<4:
            vu += [(0,1,0)]
        else:
            t1 = vu[k-1]
            t3 = vu[k-3]
            t4 = vu[k-4]
            if sum(t4)<sum(t3):
                vu.append((t4[0],t4[1],t4[2]+1))
            elif sum(t3)<sum(t1):
                vu.append((t3[0],t3[1]+1,t3[2]))
            else:
                vu.append((t1[0]+1,t1[1],t1[2]))
    return Tirelire(*vu[-1])

Cet algorithme (qui n'est pas récursif) est de coût linéaire à la fois en temps et en place mémoire, alors que l'autre version est de coût logarithmique en place mémoire mais exponentiel en temps.

5) Programmation dynamique

La programmation dynamique permet de créer des algorithmes efficaces pour résoudre un problème tel que :

• Le problème se ramène à des sous-problèmes plus petits.
• Les sous-problèmes apparaissent un grand nombre de fois.
• Il existe une structure de données permettant de stocker les solutions des sous-problèmes.

Elle consiste à résoudre (et stocker) les sous-problèmes puis aller vers le problème général, soit récursivement, soit itérativement.