Skip to content

Récursivité

Voir aussi

Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein - Algorithmique - 3ème édition - Cours avec 957 exercices et 158 problèmes, Dunod, 2010, ISBN: 978-2-10-054526-1

Motivation et introduction du concept

Un algorithme est dit récursif s'il s'appelle lui-même directement ou indirectement via l'appel d'une ou de plusieurs autres fonctions qui elles-mêmes finissent par l'appeler.

La récursivité est un concept fondamental en informatique qui met naturellement en pratique un mode de pensée puissant qui consiste à pouvoir découper la tâche à réaliser en sous-tâches de mêmes natures mais plus petites qui finalement sont simples à résoudre.

La démarche s'inspire de la démarche inductive mathématique utilisée dans les preuves par récurrence:

Rappel du principe

Si l'on doit prouver l'assertion S(n) = f (n) pour tout n supérieur ou égal à n_0

Pour le cas de base on prouve l'assertion pour certaines petites valeurs de n (n_0 par exemple)

Pour l'étape de récurrence : on suppose que c'est vrai pour n inférieure ou égale à k (avec k supérieure ou égal à n0), et prouve que c'est également vrai pour n = k + 1

Remarque : on peut aussi supposer que c'est vrai pour n inférieur ou égal à k - 1 et prouver que c'est vrai pour n = k.

C'est ce qu'on fera ici : souvent plus intuitif d'un point de vue informatique.

Prenons par exemple le calcul de la factorielle d'un nombre n. Par définition pour un n entier strictement positif, n! est égale au produit des entiers strictement positifs inférieurs à n. Par convention on a aussi 0! = 1.

Donnons le code itératif d'une fonction calculant la factorielle:

  def fact(n):
    """Renvoie la factorielle de n."""
    res = 1
    i = 1
    for i in range(1,n+1):
      res = res * i  
    return res

La définition récursive se base sur la définition n! = n.(n-1)! pour tout n>0 avec 0! = 1

On obtient le code:

  def fact(n):
    """Renvoie la factorielle de n (méthode récursine)."""
    if n == 0:
      res = 1
    else:
      res = n*fact(n-1)
    return res

ou plus court:

  def fact(n):
    """Renvoie la factorielle de n (méthode récursive)."""
    return 1 if n == 0 else n * fact(n-1)

De nombreux algorithmes écrits de façon itérative sont énoncés de façon récursive.

Par exemple la conjecture de syracuse est la suivante : ayant un nombre n entier strictement positif, à chaque étape si n est pair on le divise par 2 sinon on le multiplie par 3 et ajoute 1.

Le programme de test de la conjecture de syracuse:

  def test_syracuse(n):
     """Teste si à partir de n le code s'arrête bien (la conjecture de syracuse est respectée pour n)."""
     while n != 1:
        if n % 2 == 0:
           n = n//2
        else:
           n = n*3+1
     return True

Littéralement on pourrait l'écrire:

  def test_syracuse(n):
     """Teste si à partir de n le code s'arrête bien (la conjecture de syracuse est respectée pour n)."""
     if  n == 1:
        res = True
     else:
        if n%2 == 0:
           n = n//2
        else:
           n = 3*n+1
        res = test_syracuse(n)
     return res

ou de façon plus abrégée:

  def test_syracuse(n):
     """Teste si à partir de n le code s'arrête bien (la conjecture de syracuse est respectée pour n)."""
     if  n == 1:
        res = True
     else:
        res = test_syracuse(n//2 if n%2 == 0 else 3*n+1)
     return res

ou encore plus abrégé (ce qui devient illisible):

  def test_syracuse(n):
     return True if  n == 1 else test_syracuse(n//2 if n%2 == 0 else 3*n+1)

En pratique, le nombre d'appels imbriqués de fonction est limité, par défaut, à 1000 appels. Par exemple, l'exécution de la version récursive de fact(1000) provoque l'erreur RuntimeError: maximum recursion depth exceeded in comparison.

Le code pour la recherche dichotomique sur une liste de couples triés sur la clé (premier élément des couples):

  def recherche_dichotomique(s,x):
     """Recherche de l'indice de x dans s par dichotomie."""
     bi, bs = 0, len(s)
     m = (bi+bs)//2
     while bi < bs and x != s[m][0]:
        m = (bi+bs)//2
        if s[m][0] < x:
           bi = m+1
        else:
           bs = m  # x est avant ou est trouvé

     if  len(s) <= m or s[m][0] != x:  # pas trouvé
        m = -1
     return m

peut s'écrire récursivement

  def recherche_dichotomique(s,x,bi, bs):
     """Recherche de l'indice de x dans s par dichotomie (version récursive)."""
     if bi >= bs:
        res = -1
     else:
        m = (bi+bs)//2
        if s[m][0] < x:
           res = recherche_dichotomique(s,x,m+1,bs)
        elif s[m][0] > x:
           res = recherche_dichotomique(s,x,bi,m)
        else:
           res = m
     return res

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 exprimé 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 exprimé 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-traitement :

  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 a 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:

Dans ce cas, 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.

Evaluation 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é, mais que la fonction renvoie une nouvelle liste triée.

Structures de données récursives

Le récursivité est intensivement utilisée dans des structures de données telles que les graphes ou les arbres informatiques.

Graphe

Un graphe G = (V,E) est une structure de données, formée d'un ensemble V d'éléments et d'un ensemble de pairs (ou de couples) établissant les liens entre ces éléments.

Si E est un ensemble de pairs, on dit que le graphe est non orienté, s'il s'agit de couples, le graphe est orienté.

Le graphique suivant décrit un graphe orienté donnant un ensemble V de personnes (V= {Jean, Germaine, Catherine, Luc, Bernadette, Jules, Michel} avec la relation E (connaît).

E = { Jean -> Germaine ; Germaine -> Catherine ; Catherine -> Jean ; Bernadette -> Luc ; Bernadette -> Michel ; Michel -> Luc ; Bernadette -> Jules ; Jules -> Bernadette }

Une façon simple d'implémenter un tel graphe en python est avec un dictionnaire dont les éléments sont les clés, et la liste de leurs connaissances, leur valeur. Dans l'exemple plus haut on aurait:

 graphe = { "Jean"       : ["Germaine"] ,
            "Germaine"   : ["Catherine"],
            "Catherine"  : ["Jean"] ,
            "Luc"        : [],
            "Michel"     : ["Luc"],
            "Bernadette" : ["Luc", "Michel", "Jules"],
            "Jules"      : ["Bernadette"] }

Arbre binaire

L'exemple de l'expression à évaluer, vu plus haut, est en fait une implémentation python, avec des listes, de la notion d'arbre binaire.

Un arbre binaire est une structure de données soit vide soit formée d'un noeud et de deux sous-arbres binaires, appelés respectivement fils gauche et un fils droit.

Chaque noeud contient une information appelée contenu.

Ainsi l'expression `3 + 4 * 5`` est vu comme l'arbre binaire illustré par la figure suivante :

où les noeuds vides ne sont pas représentés.

Notre implémentation python donnait: exp = [3,'+',[4,'*',5]]

La récursivité ainsi que de nombreux algorithmes sur les arbres et les graphes seront vus plus en détails dans la partie algorithmique.

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

Traduction de fonction récursive en fonction itérative

Toute récursivité peut plus ou moins facilement être traduite en fonction non récursive.

Dans le cas de récursivité terminale (tail recursion) c'est-à-dire où la dernière action de la fonction consiste en un appel récursif, il est assez simple de remplacer la récursivité par une boucle while.

C'est le cas pour les codes donnés dans ce module test_syracuse, recherche_dichotomique.

Dans le cas où le traitement est uniquement un post-traitement, il est possible de prendre le code à "l'envers" c'est-à-dire, de traduire le code en boucle qui fait le traitement de base, suivi du post-traitement pour n valant 1 ensuite pour n valant 2, ... jusqu'à avoir traité le cas pour la valeur n initiale. C'est ce qui se passe pour le code non récursif de la factorielle.

Quand la fonction à plusieurs appels à des instances plus petites ou qu'il y a à la fois un pré-traitement et un post-traitement, il est plus difficile de supprimer la récursivité et ne peut souvent être fait qu'avec une pile (stack) simulant cette récursivité.

Gestion de la mémoire à l'exécution

Noms et objets (rappel)

En Python, une variable est une référence à un objet. Manipuler cet objet se fait grâce à cette variable qui en quelque sorte l'identifie.

Ainsi :

 a = 3
 a = a + 1

crée un objet de classe entière (int) dont la valeur est 3, et place dans la variable a son adresse (sa référence). Ensuite l'addition crée un autre objet de type (classe) int et de valeur 4 et a reçoit la référence à ce nouvel objet.

  >>> dir(a) 
 ['__abs__', '__add__', '__and__', '__bool__', '__ceil__', '__class__',
  '__delattr__', '__divmod__', '__doc__', '__eq__', '__float__',
  '__floor__', '__floordiv__', '__format__', '__ge__',
  '__getattribute__', '__getnewargs__', '__gt__', '__hash__',
  '__index__', '__init__', '__int__', '__invert__', '__le__',
  '__lshift__', '__lt__', '__mod__', '__mul__', '__ne__', '__neg__',
  '__new__', '__or__', '__pos__', '__pow__', '__radd__', '__rand__',
  '__rdivmod__', '__reduce__', '__reduce_ex__', '__repr__',
  '__rfloordiv__', '__rlshift__', '__rmod__', '__rmul__', '__ror__',
  '__round__', '__rpow__', '__rrshift__', '__rshift__', '__rsub__',
  '__rtruediv__', '__rxor__', '__setattr__', '__sizeof__', '__str__',
  '__sub__', '__subclasshook__', '__truediv__', '__trunc__',
  '__xor__', 'bit_length', 'conjugate', 'denominator', 'from_bytes',
  'imag', 'numerator', 'real', 'to_bytes']

dir(a) renvoie la liste des attributs et méthodes de l'objet référencé par la variable a.

En fait en Python tout est objet (ou référence à un objet).

Dans le vocabulaire Python, une variable est appelé nom et est liée à un objet. Un objet peut avoir plusieurs noms, par exemple dans le code ci-dessous où l'objet de type liste est connu sous les noms s et t dans un code appelant et x dans la fonction foo appelée.

  def foo(x):
    x[0] = 3

  s = [0, 0, 7]
  t = s
  foo(s)

Tout objet Python x a un identificateur (donné par id(x)), un type (donné par type(x)), et un contenu.

Lors de son exécution, un programme Python gère des espaces de noms (namespace). Un espace de nom est un mappage (mapping) de noms vers des objets. Des exemples de tels espaces de noms sont donnés par l'ensemble des noms globaux (donné par globals()) ou des noms locaux à une instance de fonction (donné par locals()).

  • Les espaces de nom peuvent être implémentés sous forme de dictionnaires Python.

  • Ainsi, l'assignation ainsi que le passage de paramètres à une fonction modifient les espaces de noms et pas les objets eux mêmes !

  • Par contre :

  x = []
  x.append(3)

crée un liste et un nom dans l'espace de nom courant et ensuite appelle la méthode append() qui va modifier l'objet référencé par x.

Scope et espace de nom (namespace)

En pratique la gestion des objets et des espaces de nom en mémoire implique deux espaces mémoire:

1- l'un, appelé pile d'exécution (runtime stack) qui va contenir l'espace de nom global et les espaces de noms locaux;

2- l'autre, tas d'exécution (runtime heap), qui contient les objets.

La gestion des espaces de nom locaux (ainsi que d'autres éléments en mémoire, nécessaires pour le bon fonctionnement du programme) est effectuée dans des trames (frames) dans la pile d'exécution (runtime stack): chaque fois qu'une instance de fonction foo() est appelée, une trame associée à cette instance est créée et mise comme un élément supplémentaire de la pile d'exécution. Cette trame contient en particulier, l'espace de nom local à cette instance. Cette trame sur la pile d'exécution continuera a exister jusqu'à la fin de l'exécution de cette instance de foo(). Ensuite (au moment du return), la trame est enlevée de la pile système et on revient à l'instance appelante dont la trame se trouve maintenant au sommet de la pile d'exécution.

Par contre un objet créé, continue à exister jusqu'à ce qu'il ne soit plus relié à aucun nom dans un espace de noms quelconque et que le système décide de récupérer l'espace mémoire qui lui était attribué. Cette opération est nommée garbage collection et s'effectue de façon transparente pour le programmeur, si ce n'est qu'il peut observer un ralentissement ponctuel du programme pendant que le garbage collector s'exécute. C'est en raison de la gestion sans ordre de cet espace mémoire où se trouvent les objets Python, qu'il est appelé le tas d'exécution (runtime heap).

Exemple d'exécution d'un programme

Prenons l'exécution du programme suivant qui est une version simplifiée du tri par fusion pour des listes de caractères, exécutée sur la liste list("CDAB").

 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) 
        # merge
        res = [] 
        while len(t1) > 0 and len(t2) > 0:
           if t1[0] < t2[0]: 
              res.append(t1[0])
              del t1[0]
           else: 
              res.append(t2[0])
              del t2[0]
        res += t1 + t2
     else: 
        res =  t
     return res

 liste = list("DCBA")
 print(merge_sort(liste))

Illustrons en particulier les valeurs des variables t1 et t2 avant et après les appels récursifs et au moment des return (pour simplifier les diagrammes d'états, on représente par le caractère "X" la référence à ce caractère "X").

Etat dans l'instance de fonction de niveau 1 ("DCBA") avant les appels au niveau 2.

Etat dans l'instance de fonction de niveau 2 ("DC") avant les appels au niveau 3.

Etat dans l'instance de fonction de niveau 3 pour ("D")

Etat dans l'instance de fonction de niveau 3 pour ("C")

Etat dans l'instance de fonction de niveau 2 après la fusion de "D" et "C".

Modification de t1 dans l'instance de fonction de niveau 1.

Etat dans l'instance de fonction de niveau 2 ("BA") avant les appels au niveau 3.

Etat dans l'instance de fonction de niveau 3 pour ("B")

Etat dans l'instance de fonction de niveau 3 pour ("A")

Etat dans l'instance de fonction de niveau 2 après la fusion de "B" et "A".

Modification de t2 dans l'instance de fonction de niveau 1.

Après fusion de "CD" avec "AB" dans l'instance de niveau 1 de merge_sort()

Exercices

La fractale de Koch

Le flocon de Koch ([https://fr.wikipedia.org/wiki/Flocon_de_Koch] est une courbe fractale simple

On peut la créer à partir d'un segment de droite, en modifiant récursivement chaque segment de droite de la façon suivante :

  1. On divise le segment de droite en trois segments de longueurs égales.
  2. On construit un triangle équilatéral ayant pour base le segment médian de la première étape.
  3. On supprime le segment de droite qui était la base du triangle de la deuxième étape.

Flocon de Koch pour un niveau de récursivité 0 à 5

Ecrivez un code qui dessine un flocon de Koch grâce à une fonction récursive koch(niveau, taille)niveaudonne le niveau de récursivité restant (0 = segment de droite simple) et taille, la taille du segment.

Les tours de Hanoï

Sur wikipedia nous pouvons lire:

Les tours de Hanoï (originellement, la tour d'Hanoï) sont un jeu de réflexion imaginé par le mathématicien français Édouard Lucas, et consistant à déplacer des disques de diamètres différents d'une tour de départ à une tour d' arrivée en passant par une tour intermédiaire, et ceci en un minimum de coups, tout en respectant les règles suivantes : - on ne peut déplacer plus d'un disque à la fois ; - on ne peut placer un disque que sur un autre disque plus grand que lui ou sur un emplacement vide.

On suppose que la configuration de départ consiste en \(n\) (\(n \geq 0\)) disques empilés sur la tour de départ, de taille de plus en plus petit (voir figure).

Exemple de configuration initiale avec 8 anneaux sur la tour 0

Algorithme : pour déplacer une tour de \(n\) disques de A vers C,

  • soit, la tour n'a aucun disque (\(n==0\)) et alors il ne faut faire aucun déplacement, la solution est la chaîne vide,
  • soit (\(n>0\)), on effectue ces trois étapes :
  • déplacer la tour des n-1 premiers disques de A vers B (étape qui nécessite une résolution des tours avec \(n-1\) anneaux) ;
  • déplacer le plus grand disque de A vers C (un seul déplacement) ;
  • déplacer la tour des n-1 premiers disques de B vers C (à nouveau étape qui nécessite une résolution des tours avec \(n-1\) anneaux).

Nous vous demandons d'écrire une fonction récursive hanoi(dico, n, init, final).

La fonction reçoit quatre paramètres :

  • dico : qui contient toutes les solutions des tours de Hanoï déjà calculées (initialement dico est vide).
  • n (supérieur ou égal à 0) : la hauteur de la tour de Hanoï qu'il faut résoudre
  • init : le numéro (0, 1 ou 2) de la pile où se trouve initialement les anneaux
  • final: le numéro (0, 1 ou 2) de la pile où doivent se trouver les anneaux après les avoir déplacés en respectant les règles

On peut supposer que init et final sont différents.

Elle doit renvoyer une chaîne de caractères donnant la séquence des mouvements à réaliser pour déplacer la tour de n anneaux de la pile init vers la pile final en respectant les règles imposées. On suppose, les tours numérotées de 0 à 2 et les anneaux de 1 à n.

**Conseil: ** Inspirez-vous de l'algorithme décrit plus haut.

Par exemple, hanoi(dico, 3, 0, 2) doit renvoyer la chaîne de caractères:

move 1 from 0 to 2
move 2 from 0 to 1
move 1 from 2 to 1
move 3 from 0 to 2
move 1 from 1 to 0
move 2 from 1 to 2
move 1 from 0 to 2

Chaque fois qu'une nouvelle configuration a été calculée, sous forme de chaîne de caractères donnant une séquence de lignes, délimitées par le caractère '\n', la fonction hanoi la rajoute dans dico (clé : (n,init,final) et valeur la chaîne de caractères).

Si hanoi est appelée pour une configuration déjà dans dico, elle renvoie le résultat sans refaire les calculs.

La fonction de Ackermann

Écrivez de manière récursive, une fonction ackermann(m,n) qui implémente la fonction d'Ackermann \(A(m, n)\) définie comme suit : [ \begin{array}{lclcl} A(m,n) = \ n+1 & si & m = 0 \ A(m-1, 1) & si & m > 0 & et & n = 0\ A(m-1, A(m, n-1)) & si & m > 0 & et & n > 0. \end{array} ] Vérifiez que ackermann(3,6) donne 509. Que se passe-t-il pour de plus grandes valeurs ? Pourquoi ?

Retour sur trace ou retour en arrière / Backtracking

Notons que de nombreux problèmes peuvent être formalisés sous forme de jeu à un ou plusieurs joueurs et peuvent être programmés grâce à la technique algorithmique du ("retour en arrière")[https://fr.wikipedia.org/wiki/Retour_sur_trace] ("backtracking") qui recherche une solution en revenant en arrière quand le chemin pris (ou la proposition de solution envisagée) n'est pas bon. La récursivité permet "facilement" de programmer ces méthodes.