Recursivité

04-04-2022

Objectifs

  • programmer quelques fonctions récursives.

  • évaluer des coûts en nombre de multiplications.

Matériel fourni : une archive materiel_tp_recursivite.zip contenant :

  • le fichier squelette_recursivite.py qui contient les spécifications des fonctions à réaliser. Il faudra compléter ce fichier.

  • le fichier ap2_decorators.py qui contient la définition des décorateurs @count et @trace qui ont déjà été présentés en cours.

Avant de commencer

À faire

  • Téléchargez le matériel fourni.

  • Décompressez le fichier dans votre dossier de travail.

  • Renommez le fichier squelette_recursivite.py en recursivite.py

  • Completez l’entête.

Une première partie binaire

Tout entier naturel n peut être écrit de manière unique comme une somme de puissance de deux, chaque terme étant strictement inférieur au précédent s’il existe.

Note

Exemple

2021 = 1024 + 512 + 256 + 128 + 64 + 32 + 4 + 1

Par conséquent, tout entier naturel \(n\) non nul peut s’écrire ainsi:

\[n = \sum_{i=0}^{k} b_i 2^i\]

\(b_k=1\) et \(\forall i \qquad b_i\in\left\{0,1\right\}\)

Note

Exemple

\(2021 = 1\times 2^{10} + 1\times 2^{9} +1\times 2^{8}+ 1\times 2^{7}+1\times 2^{6}\\ +1\times 2^{5}+0\times 2^{4}+0\times 2^{3}+1\times 2^{2}+0\times 2^{1}+1\times 2^{0}\)

Les \(b_i\) sont appelés chiffres binaires ou bits (contraction de binary digit).

On dit que \(b_i\), coefficient de \(2^i\) dans la décomposition binaire de \(n\) est le bit de poids \(i\) de l’entier \(n\).

Le nombre de bits intervenant dans la décomposition binaire de \(n\) est appelé taille binaire de \(n\) Le nombre de bits 1, ou encore \(\sum_{i=0}^{k} b_i\) est appelé poids binaire de \(n\)

On construit la représentation binaire d’un entier en listant les bits par poids décroissants. ainsi une représentation binaire de 2021 est 11111100101. Bien sûr, comme il est difficile de faire la différence entre les chiffres de la base 2 et les chiffres 0 et 1 du système décimal, il faut préciser la base dans laquelle on travaille sinon on arrive à des situations ambigües.

Note

Remarque

il y a 10 sortes d’étudiants,

  • ceux qui connaissent le binaire,

  • et les autres.

Pour faire la distinction, plusieurs solutions sont utilisées

  • en Python, on peut préciser qu’on utilise une représentation binaire d’un entier dans une expression litérale en ajoutant 0b devant

    Note

    Exemple

    >>> 0b110
    6
    >>> 0b110 + 12
    18
    
  • dans le contexte des cours d’informatique, on utilise souvent une notation parenthésée avec en indice la base utilisée.

    Note

    Exemple

    \((1001)_2\) représente l’entier neuf.

En python, la fonction bin permet d’obtenir la représentation binaire d’un entier. Elle prend comme paramètre un entier et renvoie une chaîne de caractères.

Note

Exemple

>>> bin(2021)
'0b11111100101'

En python, la fonction int peut être utilisée avec deux paramètres, le premier une représentation de type chaîne de caractères, le second est la base de type entier.

Note

Exemple

>>> int('11111100101', 2)
2021

On se propose de coder quelques fonctions sans utiliser int et bin

À faire

Réalisez la version récursive taille_binaire_recursive de la fonction taille_binaire.

À faire

Réalisez la version récursive poids_binaire_recursif de la fonction poids_binaire.

Une seconde partie puissante

À faire

Complétez le corps de la fonction puissance, pour donner une définition récursive de la fonction puissance.

À faire

Lisez le code de la fonction fois.

@count
def fois(x, y):
    """
    renvoie le produit de x par y

    :param x: (int or float)
    :param y: (int or float)
    :return: (int or float)
    :CU: les mêmes que l'opérateur *

    :ExU:
    >>> fois(8, 7)
    56

    """
    return x * y

Puis réalisez une fonction puissance_v2, où vous remplacerez les utilisations de l’opérateur de multiplication * par un appel à la fonction fois

La fonction fois à été décorée grâce au décorateur @count qui permet de compter le nombre d’appels à cette fonction.

On va donc pouvoir utiliser ce principe pour connaitre le nombre de multiplications effectuées lors du calcul de puissance_v2(x,n)

On se propose d’étudier la complexité en nombre de multiplications de l’élévation à la puissance.

Pour faire une étude expérimentale, on réalise la fonction de comptage suivante :

À faire

  • Lisez le code de la fonction de comptage.

    def comptage(puissance):
        """ fabrique une liste de longueur 100 contenant
            le nombre de multiplications effectuées par la
            fonction ``puissance`` passée en paramètre
    
            :param puissance: (function)
            :return: (list)
            :CU: la fonction doit être implantée en
                 utilisant la fonction ``fois``
    
        """
        res = []
        for i in range(100):
            fois.counter = 0
            _ = puissance(2, i)
            res.append(fois.counter)
        return res
    
  • Quel est le type de son paramètre ?

  • Quel est le type du résultat ?

À faire

  • Calculez comptage(puissance).

  • Pourquoi obtient-on ce résultat ?

  • Calculez comptage(puissance_v2).

  • En observant les résultats, intuitez une expression en fonction de n de la complexité en nombre de multiplications de la fonction puissance_v2.

  • Puis prouvez le.

Raymond Calbuth a lu sur des forums d’informatique, qu’un principe appelé « Diviser pour régner » permet souvent de diminuer le coût.

Il a donc décidé d’utiliser ce principe pour réécrire la fonction puissance ainsi:

def puissance_calbuth(x, n):
    """
    calcule  x élevé à la puissance n

    :param x: (int or float)
    :param n: (int)
    :return: (int or float)
    :CU: n>=0
    :ExU:

    >>> puissance_calbuth(10,0)
    1
    >>> puissance_calbuth(10,1)
    10
    >>> puissance_calbuth(2,10)
    1024

    """
    if n == 0:
        return 1
    if n == 1:
        return x
    else:
        k = n // 2
        return puissance_calbuth(x, k) * puissance_calbuth(x, n - k)

À faire

Réalisez une fonction puissance_calbuth_v2 où vous devez remplacer les utilisations de l’opérateur de multiplication * par un appel à la fonction fois

À faire

En vous inspirant du travail fait précédemment, répondez aux questions suivantes:

  • L’idée de Raymond Calbuth permet-elle de diminuer la complexité en nombre de multiplications dans le calcul de la puissance ?

  • Si oui quel est le gain ?

  • Sinon, s’il y a une perte, quelle est-elle ?

Toutefois, l’idée n’est pas si mauvaise que cela, il aurait pu mieux l’exploiter. En effet, il a programmé le calcul de puissance(x,k) et celui de puissance(x,n-k) mais dans certain cas ces deux calculs sont identiques: Cela arrive lorsque \(k = n-k\) .

À faire

Précisez en fonction de \(n\) dans quel cas on a l’égalité \(k=n-k\).

À faire

  • Ajoutez le décorateur @trace devant la déclaration de puissance_calbuth.

  • Calculez puissance_calbuth(2,5).

  • Combien de fois est calculé puissance_calbuth(2,2) ?

Note

Remarque

Tant que le le décorateur @trace sera devant la déclaration, celle-ci ne passe plus les doctests. Une fois les observations effectuées, vous pouvez placer un # devant le décorateur.

Dans ce cas, au lieu de demander à Python de calculer deux fois la même chose, on peut stocker le résultat dans une variable et réutiliser la valeur calculée.

À faire

Lorsque \(n\) est impair, dites comment se ramener au cas où \(n\) est pair grâce à un appel récursif ?

À faire

Réalisez une fonction puissance_calbuth_v2_amelioree qui utilise ces deux idées.

À faire

En utilisant la fonction comptage, l’idée de Raymond Calbuth améliorée vous semble-t-elle diminuer la complexité en nombre de multiplications dans le calcul de la puissance ?

À faire

  • Construisez la liste des f(i) pour i variant dans range(100) où désigne f la somme de la taille binaire et du poids binaire de i.

  • Comparez cette liste avec celle obtenue en évaluant l’expression comptage(puissance_calbuth_v2_amelioree).

  • En utilisant votre intuition, donnez une expression en fonction de \(n\) de la complexité en nombre de multiplications effectuées lors du calcul de puissance_calbuth_v2_amelioree(x,n).