Skip to content

2 4 4 transmissions

Mécanismes de transmission de valeurs et de résultats entre les instances récursives

Un élément essentiel à maîtriser pour concevoir des algorithmes récursifs est la façon de transmettre données et résultats entre instances récursives, en supposant bien sûr que l'utilisation de variables globales est proscrite pour des raisons de bonnes pratiques de programmation.

Prenons l'exemple de fonction directement récursive (la fonction s'appelle directement elle même) permutations vu plus haut qui calcule l'ensemble des permutations d'une séquence données.

Trois mécanismes peuvent être utilisés :

  1. le passage de paramètres lors de l'appel de l'instance de la fonction
  2. le retour à la fin de l'exécution de l'instance de la fonction
  3. via un argument modifiable (tout objet d'une classe modifiable).

Un programmeur peut désirer transmettre des valeurs depuis l'instance père vers son fils (ce que l'on appelle parfois héritage) ou dans le sens inverse, depuis le fils vers son père (ce que l'on appelle parfois synthèse).

Le passage de paramètres permet évidemment l'héritage du père vers son fils.

Le retour ainsi que l'utilisation d'arguments modifiables permet de faire de la synthèse depuis le fils vers son père.

La fonction permutations initiale donnée plus haut, et donnée à nouveau ici, réalise de l'héritage jusqu'aux instances fils qui réalisent l'affichage des résultats.

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

Le second code, donné à nouveau ici, montre l'utilisation d'une liste (objet modifiable) pour synthétiser un résultat pour le code appelant (ici la liste des permutation) :

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

Ce code peut ici être modifié pour que la synthèse des résultats soit réalisée via les retours des instances de la fonction :

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


# 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 = permutations("", sequence)

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