Skip to content

TD15. Entiers récursifs

L'objectif de ce TD est de continuer à se familiariser avec l'écriture de fonctions récursives. Pour ce faire, on se propose ici de stocker des entiers naturels comme une liste chaînée de bits. On utilise le type Cellule suivant :

class Cellule:
    """Cellule d’une liste chaînée de bits."""
    def __init__(self, bit, suivant=None):
        self.bit = bit
        self.suivant = suivant

Contrairement aux listes chaînées vues précédemment, il n'y a pas ici de classe ListeChainee. On considère directement la liste chaînée des cellules à partir d’une première cellule donnée. On stocke les bits en partant du bit de poids faible. L’entier 13, 1101 en binaire sera donc codé par une liste chaînée de 4 cellules :

  • une première cellule contenant le bit 1 ;
  • une seconde cellule contenant le bit 0 ;
  • une troisième cellule contenant le bit 1 ;
  • une dernière cellule contenant le bit 1.

Les listes chaînées devront être sous forme canonique, c’est-à-dire sans 0 inutile en queue. Chaque entier aura donc un codage unique, et 0 sera codé par None.

Dans ce TD, toutes les fonctions demandées doivent être récursives.

Exercice 1 : représentation

Question 1

Dessiner la liste codant 8 et la liste codant 19.

Cliquez ici pour révéler la correction. 8 = 1000b = 0 → 0 → 0 → 1 → None

19 = 10011b = 1 → 1 → 0 → 0 → 1 → None

Normalement, nous avons assez dessiné de listes chaînées sous la forme d'instances Python en arrivant ici. Donc pas forcément la peine de dessiner les instances mais on peut le faire quand même hein si ça nous semble encore nécessaire :)

Question 2

Implémenter une fonction calcule_valeur(entier) renvoyant la valeur de l'entier codé par la liste chaînée de bits entier.

Cliquez ici pour révéler la correction.

def calcule_valeur(entier_liste_chainee):
    """Renvoie la valeur de l'entier codé par la liste chaînée de bits donnée."""
    if entier_liste_chainee is None:
        return 0
    return 2 * calcule_valeur(entier_liste_chainee.suivant) + entier_liste_chainee.bit

Pour bien comprende, voici l'arbre d'appels de calcule_valeur(dixneuf) avec dixneuf étant une référence sur la liste chaînée 1 → 1 → 0 → 0 → 1 → None :

arbre d'appels

Correction vidéo :

Question 3

Implémenter une fonction construit_liste(entier) prenant un entier naturel > 0 et renvoyant la liste chaînée de bits qui le code.

Cliquez ici pour révéler la correction.

def construit_liste(entier):
    """Renvoie la liste chaînée de bits qui code entier (qui doit être >= 0)."""
    if entier == 0:
        return None
    return Cellule(entier & 1, construit_liste(entier >> 1))

Pour bien comprendre, voici l'arbre d'appels de construit_liste(19) :

arbre d'appels

Correction vidéo :

Question 4

Implémenter la méthode de stringification __str__ pour la classe Cellule. Celle-ci devra retourner une chaîne de caractères contenant les bits dans le sens classique de lecture, c'est à dire du poids fort au poids faible. Quelle est la complexité de cette méthode ?

Cliquez ici pour révéler la correction.

    def __str__(self):
        """Stringification quadratique en le nombre de cellules == le nombre de bits.

        Quadratique car "a + b" est en O(len(a) + len(b)) et le type str est immutable.
        Donc sur la liste 19 = 1 → 1 → 0 → 0 → 1 on va faire
           (((("1") + "0") + "0") + "1") + "1"
        Voir le dessin dans la correction.

        Voir également la version ci-dessous pour du linéaire.
        """
        if self is None:
            return "None"
        if self.suivant is None:
            return str(self.bit)
        return self.suivant.__str__() + str(self.bit)

    def cellule__str__lineaire(self):
        """Stringification linéaire en le nombre de cellules == le nombre de bits.

        Plutôt que d'utiliser l'opérateur "+" qui coûte cher, on fait du
        list.append puis du reversed (et pas du insert(0) sinon gare au quadratique
        qui reviendrait au galop).
        """

        if self is None:
            return "None"

        def get_bits_list(bits_list, cell):
            bits_list.append(cell.bit)
            if cell.suivant is not None:
                get_bits_list(bits_list, cell.suivant)

        bits_list = []
        get_bits_list(bits_list, self)
        return "".join(str(b) for b in reversed(bits_list))

    def cellule__str__lineaire_bis(self):
        """Stringification linéaire en le nombre de cellules == le nombre de bits.

        Plutôt que d'utiliser l'opérateur "+" qui coûte cher, on fait du
        list.append.
        """

        # Cas de base, quand self est None
        if self is None:
            return "None (= zéro)"

        def str_rec(cell):
            # Cas de base, une liste chainée à un seul élement
            if cell.suivant is None:
                return [cell.bit]

            # Appels récursifs
            suiv = str_rec(cell.suivant)
            suiv.append(cell.bit)
            return suiv

        return "".join(str(bit) for bit in str_rec(self))

Pour bien comprende, voici l'arbre d'appels de dixneuf.__str__() :

arbre d'appels

Correction vidéo :

Voici l'arbre d'appels de get_bits_list([], dixneuf) appelé par dixneuf.cellule__str__lineaire() :

arbre d'appels

Concernant les performances des trois implémentation de __str__, voici les résultats sur ma (Manu) machine avec une liste assez grande :

big_int = 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084095
it took 0.000170046 seconds to __str__
it took 0.000266925 seconds to cellule__str__lineaire
it took 0.000199568 seconds to cellule__str__lineaire_bis

La version quadratique est plus rapide que les versions linéaires :-( Est-ce le cas sur vos machines également ? Une boîte de chocolats sera offerte au premier groupe de TD qui enverra un email à manuel.selva@grenoble-inp.fr avec la justification argumentée, si possible avec des exemples de code, de ce comportement étrange.

Exercice 2 : opérations d'ajout

Question 1

Implémenter une fonction ajoute_1(entier) renvoyant la liste chaînée codant 1 de plus que l'entier codé par la liste chaînée donnée en entrée.

Cliquez ici pour révéler la correction.

def ajoute_1(entier_liste_chainee):
    """Renvoie la liste chaînée codant 1 de plus que l'entier donnée en entrée."""

    # 0 + 1 = 1
    if entier_liste_chainee is None:
        return representation.Cellule(1)

    # Si on a un 0 en tête de liste, il suffit de remplacer
    # par un 1.
    # Remarque : ici on fait du partage de suffixe avec
    # l’argument entier. Cela fonctionne du moment
    # qu’on ne s’autorise jamais à modifier les listes
    # représentant des entiers une fois construites.
    if entier_liste_chainee.bit == 0:
        return representation.Cellule(1, entier_liste_chainee.suivant)

    # Si on a un 1 en tête de liste, il faut le remplacer
    # par un zéro et propager la retenue vers la droite
    return representation.Cellule(0, ajoute_1(entier_liste_chainee.suivant))

Question 2

Implémenter une fonction ajoute(entier1, entier2) renvoyant la liste chaînée codant la somme des entiers codés par les deux listes chaînées données en entrée.

Cliquez ici pour révéler la correction.

def ajoute(entier1_liste_chainee, entier2_liste_chainee):
    """Renvoie la liste chaînée codant la somme des entiers donnés."""
    # On peut faire egalement une version prenant une retenue en
    # argument

    # Si l'un des deux vaut zéro, c'est fastoche
    if entier1_liste_chainee is None:
        return entier2_liste_chainee
    if entier2_liste_chainee is None:
        return entier1_liste_chainee

    # Calcule du nouveau bit
    addition_bits = entier1_liste_chainee.bit + entier2_liste_chainee.bit
    bit = addition_bits % 2

    # Appel recursive sur les autres bits
    bits_forts = ajoute(entier1_liste_chainee.suivant,
                        entier2_liste_chainee.suivant)

    # Ajoute 1 à la somme des autres bits si besoin
    if addition_bits == 2:
        bits_forts = ajoute_1(bits_forts)

    return representation.Cellule(bit, bits_forts)

Exercice 3 : soustraction (pour aller plus loin)

Question 1

Implémenter une fonction soustrait(entier1, entier2) renvoyant la liste chaînée codant la différence des entiers codés par les deux listes en entrée.

Cette fonction ne peut pas renvoyer d’entier négatif et doit donc lever une exception si l’entier codé par entier1 est strictement inférieur à l’entier codé par entier2.

Attention à la canonicité !

Cliquez ici pour révéler la correction.

def soustrait(entier1_liste_chainee, entier2_liste_chainee):
    """Renvoie la liste codant entier1 - entier2 ou lève une exception si entier2 > entier1."""

    # On lance une exception si le résultat serait un nombre négatif
    if representation.calcule_valeur(entier2_liste_chainee) > \
       representation.calcule_valeur(entier1_liste_chainee):
        raise ValueError('entier2 > entier1')

    # Si entier2 est zéro, c'est fastoche
    if not entier2_liste_chainee:
        return entier1_liste_chainee

    # Calcule du nouveau bit
    bit = entier1_liste_chainee.bit - entier2_liste_chainee.bit

    # Appel recursif sur les bits suivants propageant la retenue avec ajoute_1 si besoin
    if bit == -1:
        diff_of_next_bits = soustrait(entier1_liste_chainee.suivant,
                                      ajout.ajoute_1(entier2_liste_chainee.suivant))
        bit = 1
    else:
        diff_of_next_bits = soustrait(entier1_liste_chainee.suivant,
                                      entier2_liste_chainee.suivant)
        if bit == 0 and not diff_of_next_bits:
            return None ## pour la canonicité

    return representation.Cellule(bit, diff_of_next_bits)