Skip to content

2 4 2 mecanismes

Mécanismes

Prenons un simple code récursif (fonction foo) dont le cas de base est celui où le paramètre n vaut 0 et qui sinon fait un appel récursif à une instance foo(n-1).

  def foo(n):

    if n == 0:
       # traitement cas de base
    else 
       ...
       foo(n-1)
       ...

La fonction foo réalise généralement un certain traitement pour le cas de base, et peut effectuer un traitement avant (que nous appelons ici pré-traitement, pour exprimer que le travail se fait avant l'appel récursif même si ce n'est pas un terme consacré), ou après (que nous appelons ici post-traitement, pour exprimer que le travail se fait avant l'appel récursif même si ce n'est pas un terme consacré) l'appel récursif.

Les trois codes suivants illustrent ces possibilités où les traitements correspondent simplement à des print :

Avec pré-traitement :

  def foo(n):
    if n==0:
      print("cas de base :", n)
    else:
      print("pre-traitement pour :" , n)
      foo(n-1)

  foo(5)

donne :

  pre-traitement pour : 5
  pre-traitement pour : 4
  pre-traitement pour : 3
  pre-traitement pour : 2
  pre-traitement pour : 1
  cas de base : 0

Avec post-traitement :

  def foo(n):
    if n==0:
      print("cas de base")
    else:
      foo(n-1)
      print("post-traitement pour :" , n)

  foo(5)

donne :

  cas de base :  0
  post-traitement pour : 1
  post-traitement pour : 2
  post-traitement pour : 3
  post-traitement pour : 4
  post-traitement pour : 5

Avec pré et post-traitements :

  def foo(n):
    if n==0:
      print("cas de base : ", n)
    else:
      print("pre-traitement pour :" , n)
      foo(n-1)
      print("post-traitement pour :" , n)

  foo(5)

donne :

 pre-traitement pour : 5
 pre-traitement pour : 4
 pre-traitement pour : 3
 pre-traitement pour : 2
 pre-traitement pour : 1
 cas de base :  0
 post-traitement pour : 1
 post-traitement pour : 2
 post-traitement pour : 3
 post-traitement pour : 4
 post-traitement pour : 5

Notons qu'ici on suppose que l'instance n appelle une fois l'instance n-1. Il se peut qu'elle appelle plusieurs instances n-1 comme nous le verrons dans certains exemples plus bas.

Quand une instance donnée (par exemple de paramètre n) de la fonction foo appelle récursivement une instance plus petite (par exemple de paramètre n-1), on dit généralement que l'instance père foo(n) appelle une instance fils foo(n-1).

Illustrons ces trois canevas.

Fonction récursive avec pré-traitement

Le code récursif du test de Syracuse ainsi que celui de la recherche dichotomique sont des exemples de code avec uniquement un pré-traitement ou un traitement de base (excepté le return du résultat obtenu qui constitue un post-traitement très simple). Dans les deux codes, on fait un test en début de fonction et ensuite on appelle récursivement la fonction avec des paramètres modifiés.

Les deux exemples suivant illustrent aussi bien un traitement récursif avec pré-traitement :

Calcul de toutes les permutations des éléments d'une séquence

L'idée est simple : l'ensemble des permutations des éléments d'une séquence s est donné en prenant l'ensemble des séquences commençant par un symbole quelconque de s suivi de toutes les permutations des symboles restants.

On obtient facilement le code suivant :

 def permutations(prefixe, s):
    """Imprime les permutations de s."""
    if len(s) == 0:  # prefixe est une nouvelle permutation
       print(prefixe)
    else:  # prend un élément de la séquence comme suivant 
           # et construit la suite avec ce qu'il reste à permuter
       for i in range(len(s)):
          permutations(prefixe + s[i], s[:i]+s[i+1:])

 permutations("", "abcd")
 print()
 permutations("", ("belle Marquise ", "vos beaux yeux ", "me font ",\
                   "mourir ", "d'amour ", "pour vous "))

On peut aussi stocker les résultats dans une liste :

 def permutations(prefixe, s, liste):
    """Construit la liste des permutations de s."""
    if len(s) == 0:
       liste.append(prefixe)
    else:
       for i in range(len(s)):
          permutations(prefixe + s[i],s[:i]+s[i+1:], liste)


 # fact est utilisé pour l'impression du résultat
 def fact(n):
    """Renvoie la factorielle de n."""
     return 1 if n==0 or n == 1 else n * fact(n-1)

 sequence= input("séquence : ") # lecture de la séquence 
                                # de caractères dont on veut les permutations
 liste = [] # contiendra les résultats construits par la fonction permutations
 permutations("", sequence, liste)

 # imprime les résultats
 for i,j in zip(range(fact(len(sequence))),liste):
    print("{0:5d} : {1}".format(i,j))

Tri rapide (Quicksort)

Le tri rapide est également un algorithme récursif avec pré-traitement.

L'idée est que pour trier un vecteur (liste python), on choisit au hasard un (par exemple le premier) élément du vecteur : il sera appelé l'élément pivot. Ensuite on classe les éléments du vecteur de manière à placer avant le pivot les éléments qui lui sont inférieurs, et après ceux qui lui sont supérieurs. On appelle (récursivement) le tri rapide sur les deux moitiés de part et d'autre du pivot. Lorsque la séquence à trier est de taille 0 ou 1, il n'y a plus rien à faire, car le tableau est déjà trié.

Le tri rapide sera donné ultérieurement dans un cours d'algorithmique.

Une implémentation naïve du quicksort donne :

def quick_sort(s):
    """Tri rapide (quicksort) de s (liste de couples (clé, valeur))."""
    if len(s) <= 1:
        res = s
    else:
        pivot = s[0]
        prefixe = quick_sort([x for x in s[1:] if x[0] < pivot[0]])
        suffixe = quick_sort([x for x in s[1:] if x[0] >= pivot[0]])
        res =  prefixe + [pivot] + suffixe
    return res

Notez qu'ici s n'est pas modifié, mais que la fonction renvoie une nouvelle liste triée. Une version en place et plus efficace du tri rapide est possible.

Fonction récursive avec post-traitement :

Ce cas intervient souvent quand pour calculer le résultat de l'instance père de la fonction, on doit d'abord avoir la valeur de son ou ses fils.

La fonction récursive fact(n) en est un exemple très simple.

Donnons en deux autres exemples.

Évaluation d'expressions arithmétiques

C'est un exemple typique de post-traitement : par exemple, 3 + 4 * 5 prend la valeur 3 (dont on a directement la valeur) et (4 * 5) évaluée avant, pour finalement avoir le résultat de la somme.

 def evalue(v):
    """eval(v) récursive."""
    if type(v) is not list:
        res= v
    elif v[1]=='+':
        res = evalue(v[0]) + evalue(v[2])
    elif v[1]=='-':
        res = evalue(v[0]) - evalue(v[2])
    elif v[1] == '*':
        res = evalue(v[0]) * evalue(v[2])
    elif v[1]=='/':
        res = evalue(v[0]) / evalue(v[2])
    elif v[1] == '^':
        res = evalue(v[0]) ** evalue(v[2])
    else:
        res = None # error
    return res

Tri fusion (Mergesort)

Un autre exemple de récursivité avec post-traitement est le tri fusion. On divise la séquence de n éléments à trier en deux sous-séquences de n/2 éléments, on trie les deux sous-séquences à l'aide du tri fusion (appel récursif), on combine, en les fusionnant, les deux sous-séquences triées pour produire la séquence triée.

Le cas de base est le tri d'une séquence de taille 1.

Le code suivant est une version non optimisée du tri fusion :

 def merge(t1, t2): 
     """Fusion de t1 et t2."""
     if len(t1) == 0:
        res = t2 
     elif len(t2) == 0: 
        res =  t1
     elif t1[0][0] < t2[0][0]: 
        res =  [t1[0]] + merge(t1[1:], t2)
     else: 
        res =  [t2[0]] + merge(t1, t2[1:])
     return res

 def merge_sort(t): 
     """Tri par fusion de t."""
     if len(t) > 1:
        (t1, t2) = (t[:len(t)//2], t[len(t)//2:])
        t1 = merge_sort(t1) 
        t2 = merge_sort(t2) 
        res =  merge(t1, t2)
     else: 
        res =  t
     return res

 ma_liste = list(zip("bonjour", range(10)))
 res = merge_sort(ma_liste)
 print(res)

Notez aussi que ici ma_liste n'est pas modifiée, mais que la fonction renvoie une nouvelle liste triée.