Feuille 2 : récursivité

22. Feuille 2 : récursivité#

Le symbole $\blacksquare$ indique les exercices ou questions obligatoires. Commencez pas ceux-là.
Les symboles $\star$ et $\star\star$ indiquent les exercices ou questions de difficulté relative plus importante.

Focus

récursivité et notions associées : arbre et pile des appels, environnements
recherche dichotomique

Compétences

Savoir conduire une approche diviser pour régner et en déduire une solution récursive : application à des exemples calculatoires simples – comme ceux vus en cours, e.g. factorielles, exponentiation entière, exponentiation rapide.
Savoir identifier la (ou les) terminaison, la récursion et l’initialisation d’un traitement avec un algorithme récursif : application à des exemples simples – comme ceux vus en cours, e.g. factorielles, exponentiation entière, exponentiation rapide.
Savoir exprimer la complexité d’un algorithme récursif
Savoir écrire sous la forme d’une fonction de même signature les versions itérative et récursive d’un traitement calculatoire simple
Construire la pile des appels et son évolution lors d’un traitement récursif

22.1. Objectif 10#

22.1.1. $\blacksquare$ Exercice.#

Écrire puis coder une version itérative de $u(n)= 2^n$ pour $n>0$

def twopower_it(n: int) ->int:
    '''
    calcule et retourne 2**n pour n > 0 
    version itérative
    '''
    assert n > 0
    
    res = 1
    for i in range(n):
        res = res * 2
    return res

from math import factorial
from random import randint

def tu_2_to_n() -> None:
    # valeurs de base
    assert twopower_it(1) == 2
    assert twopower_it(2) == 4

    # tests aléatoires 
    for i in range(10):
        val = randint(2,100)
        assert twopower_it(val) == 2 * twopower_it(val - 1)
        assert twopower_it(val) == 2 ** val
        
    print("twopower_it: tests unitaires OK") 
        
tu_2_to_n()

twopower_it: tests unitaires OK

Écrire puis coder une version récursive de ce même calcul.

def twopower(n: int) -> int:
    '''
    calcule u(n)=2**n pour n > 0
    version récursive
    '''
    assert n > 0
    
    if (n == 1):
        return 2
    else:
        return 2 * twopower(n-1)

def tu_2_to_n() -> None:
    # valeurs de base
    assert twopower(1) == 2
    assert twopower(2) == 4

    # tests aléatoires 
    for i in range(10):
        val = randint(2,100)
        assert twopower(val) == 2 * twopower_it(val - 1)
        assert twopower(val) == 2 ** val
    
    # tests aléatoires avec version iterative de référence
    for i in range(50):
        val = randint(2,100)
        assert twopower(val) == twopower_it(val)
    
    print("twopower: tests unitaires OK") 
        
tu_2_to_n()

twopower: tests unitaires OK

Expliciter l’arbre des appels et les calculs associés lors de l’évaluation de $u(5)$. Combien d’appels récursifs à $u$ sont nécessaires ?

u(5) -> u(4) -> u(3) -> u(2) -> u(1) qui termine les 5 appels.

Expliciter l’évolution de la pile des appels lors de l’évaluation de $u(5)$.

Compter le nombre d’opérations arithmétiques effectuées dans le calcul itératif de $u(5)$.

4 *

Faire de même pour le calcul récursif.

1 * par appel excepté celui de terminaison donc 4 *

Conclure.

Les traitements itératif et récursif sont identiques.

22.1.2. $\blacksquare$ Exercice.#

De façon plus générale qu’à l’exercice précédent, on calcule la valeur de $x^n$ où $n$ et un entier positif, et $x$ un flottant. On rappelle que $x^0 = 1.0$.

Rappeler et écrire les algorithmes itératif et récursif (naïf) qui calculent $x^n$.

Version récursive : voir cours section 3.4.1

Expliciter l’évolution de la pile des appels lors de l’évaluation de $x^n$ pour $n = 8$ et $n = 9$.

Combien de multiplications sont nécessaires à ces calculs pour $n=2, 4, 8, 16, \dots, 2^p$ ?

n = 2 -> 2 *
n = 4 -> 4 *
n = 8 -> 8 *
n = 16 -> 16 *
n = 2p -> 2p

Rappeler le principe de l’exponentiation entière rapide.

Version récursive : voir cours section 3.4.2

Ecrire les versions itératives et récursives de cet algorithme. On pourra utiliser l’opérateur python divmod.

Dans chacun des cas, combien de multiplications sont nécessaires à ce calcul pour $n=2, 4, 8, 16, \dots, 2^p$ ? Conclure.

n = 2 -> 1 *
n = 4 -> 2 *
n = 8 -> 3 *
n = 16 -> 4 *
n = 2**p -> p = log_2(n)

Compter le nombre d’appels récursifs pour les valeurs suivantes de $n = 7, 8, 9$ et $n = 63, 64, 65$. Conclure.

n = 7 -> 4 appels (7 - 3 - 1 - 0)
n = 8 -> 5 appels (8 - 4 - 2 - 1 - 0)
n = 9 -> 5 appels (9 - 4 - 2 - 1 - 0)
n = 63 -> 7 appels (63 - 31 - 15 - 7 - 3 - 1 - 0)
n = 64 -> 8 appels (64 - 32 - 16 - 8 - 4 - 2 - 1 - 0)
n = 65 -> 8 appels (65 - 32 - 16 - 8 - 4 - 2 - 1 - 0)

On a $\log_2(n) = p$ pour $n$ tel que $2^p \le n < 2${p+1}$.

($\star$) Expliciter l’évolution de la pile des appels lors de l’évaluation de $x^n$ pour des valeurs de $n$ que vous choisirez dans la liste précédentes comme significatives des différents cas de traitement.

On note u(n) la fonction $x^n$. On exhibe la pile des appels pour $x^7$ et $x^8$. Celle de $x^9$ est identique à celle de $x^8$.

22.1.3. $\blacksquare\blacksquare$ Exercice. Si il n’y avait qu’un seul exercice à faire, c’est celui-ci !#

Donner la forme récursive qui produit le même traitement que celui d’une boucle for qui (parcourt et) affiche les indices entiers successifs de 11 à 1.

def loop_down(n: int) -> None:
    '''Boucle for decroissante
       affichage de n a 1'''
    # terminaison une fois arrivé à 0
    if n > 0:
        print(n)
        loop_down(n-1)
        return None

# appel principal
loop_down(11)

Même question pour obtenir l’affichage : 1, 2, …, 10, 11.

def loop_up(n: int) -> None:
    '''Boucle for croissante
       affichage de 1 a n'''
    # terminaison une fois arrivé à 0 aussi !
    if n > 0:
        loop_up(n - 1)
        print(n)
        return None

# appel principal
loop_up(11)

22.1.4. $\blacksquare$ Exercice. (recherche dichotomique)#

Écrire un algorithme itératif qui calcule un booléen indiquant si un tableau d’entiers donné trié par ordre croissant contient une valeur donnée. La recherche sera effectuée par dichotomie.

def dichotomie_iterative(val: int, t: list[int], dim_t: int,):
    '''recherche dichotomique : version itérative
    - val :int cherché
    - t : tableau d'int de taille dim_t, trié par ordre croissant
    sortie : vrai si val est dans t, faux sinon
            
    '''
    assert dim_t == len(t)
    for i in range(dim_t - 1):
        assert t[i] <= t[i+1]

    present = False # la réponse
    g = 0          # indice de gauche du tableau exploré
    d = dim_t - 1  # indice de droite du tableau exploré
    
    while (present == False) and (g <= d):
        m = (g + d)//2   # indice milieu de t[g,d]
        if t[m] == val:
            present = True
        elif t[m] > val: # val est dans la partie gauche : t[g,m-1]
            d = m - 1
        else:            # val est dans la partie droite : t[m+1,d]
            g = m + 1
    return present 

'''tests unitaires appel de recherche dichotomique (itérative)'''

tab10 = [i for i in range(10)] # tab10 est bien rangé par ordre croissant

# 3 est présent dans tab10
assert dichotomie_iterative(3, tab10, len(tab10))

# 13 n'est pas présent dans tab10
assert not(dichotomie_iterative(13, tab10, len(tab10)))

Écrire une fonction récursive trouve (c’est-à-dire son en-tête, puis l’appel puis le corps) qui retourne le booléen précédent en appliquant aussi une recherche par dichotomie.

        
def trouve(val: int, t: list[int], dim_t: int,) -> bool:
    '''recherche dichotomique de val dans t de taille dim_t 
    encapsulation et appel principal
    '''
    def dichotomie(val: int, t: list[int], dim_t: int, g: int, d: int) -> bool:
        '''recherche dichotomique : version récursive
        recherche val dans t[g, d] et retourne True ou False
        entrées. val : int, t: tableau d'int de taille n,
        g, d : int indices gauche et droite
        '''
        if g > d:
            return False # t est vide
        m = (g + d) // 2 
        if t[m] == val:
            return True
        elif val < t[m]: # val est dans la partie gauche
            dim_t = m - g 
            return dichotomie(val, t, dim_t, g, m-1)
        else:            # val est dans la partie droite
            dim_t = d - m
            return dichotomie(val, t, dim_t, m+1, d)
    
    return dichotomie(val, t, dim_t, 0, dim_t - 1)

22.1.5. $\blacksquare$ Exercice. (recherche dichotomique)#

Dérouler l’algorithme de recherche dichotomique (version itérative) pour rechercher la valeur 3 dans le tableau [0,1,2,3,4,5,6,7,8,9].
Donner une valeur à rechercher qui minimise le nombre d’itérations de la recherche.
Même question pour celle qui maximise ce nombre.

Réponses. voir code et traitements de la question suivante.

Coder ces traitements et vérifier votre analyse.

def dichotomie_iterative(val: int, t: list[int], dim_t: int, aff: bool = False) -> bool:
    '''recherche dichotomique : version itérative avec affichages
    - val :int cherché
    - t : tableau d'int de taille dim_t, trié par ordre croissant
    - aff == True affichera le num de l'itération et l'intervalle de recherche
    sortie : vrai si val est dans t, faux sinon
    '''
    assert dim_t == len(t)
    for i in range(dim_t - 1):
        assert t[i] <= t[i+1]
        
    
    present = False # la réponse
    g = 0          # indice de gauche du tableau exploré
    d = dim_t - 1  # indice de droite du tableau exploré
    nbit = 0
    print("nb iter, g, d, m, t[m]")
    while (present == False) and (g <= d):
        nbit = nbit + 1
        m = (g + d)//2   # indice milieu de t[g,d]
        if aff == True:
            print("  {:^4d}  {:^4d}{:^3d}{:3d}{:4d}".format(nbit, g, d, m, t[m]))
        if t[m] == val:
            present = True
        elif t[m] > val: # val est dans la partie gauche : t[g,m-1]
            d = m - 1
        else:            # val est dans la partie droite : t[m+1,d]
            g = m + 1
    return present 

'''appel de recherche dichotomique (itérative)'''

tab10 = [i for i in range(10)] # tab10 est bien rangé par ordre croissant
print("tab10 =", tab10)

print("nb itérations pour trouver 3 dans tab10")
res = dichotomie_iterative(3, tab10, len(tab10), True)

print("meilleur cas pour tab10: trouver 4")
best = dichotomie_iterative(4, tab10, len(tab10), True)

print("pire cas pour tab10: trouver 9")
worst = dichotomie_iterative(9, tab10, len(tab10), True)
              

tab10 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
nb itérations pour trouver 3 dans tab10
nb iter, g, d, m, t[m]
   1     0   9   4   4
   2     0   3   1   1
   3     2   3   2   2
   4     3   3   3   3
meilleur cas pour tab10: trouver 4
nb iter, g, d, m, t[m]
   1     0   9   4   4
pire cas pour tab10: trouver 9
nb iter, g, d, m, t[m]
   1     0   9   4   4
   2     5   9   7   7
   3     8   9   8   8
   4     9   9   9   9

Reprendre les questions précédentes sur une version récursive de cette recherche en complétant avec l’évolution de la pile des appels de ce traitement (rechercher la valeur 3 dans le tableau indiqué).

def dichotomie(val: int, t: list[int], dim_t: int, g: int, d: int, nb_app: int, aff: bool = False) -> bool:
    '''recherche dichotomique : version récursive
    recherche val dans t[g, d] et retourne True ou False
    entrées. val : int, t: tableau d'int de taille n,
    g, d : int indices gauche et droite
    -- specificites questions et affichage
    nb_app: nb d'appels -- nécessaire si aff = True 
    aff: affiche les traces d'appels et les paramètres assciés 
    '''
    nb_app = nb_app + 1
    if g > d:
        print("terminaison après {:3d} appels et g > d: {:3d} {:3d}".format(nb_app, g, d))
        return False # t est vide
    m = (g + d) // 2 
    print("appel {:^4d},{:^4d}{:^3d}{:3d}{:4d} (g, d, m, t[m])".format(nb_app, g, d, m, t[m]))
    if t[m] == val:
        print("recherche gagnante après {:3d} appels".format(nb_app))
        return True
    elif val < t[m]: # val est dans la partie gauche
        dim_t = m - g 
        return dichotomie(val, t, dim_t, g, m-1, nb_app, True)
    else:            # val est dans la partie droite
        dim_t = d - m
        return dichotomie(val, t, dim_t, m+1, d, nb_app, True)
        
def trouve(val: int, t: list[int], dim_t: int,) -> bool:
    '''recherche dichotomique de val dans t de taille dim_t 
    encapsulation et appel principal
    --
    version avec affichage des traces
    '''
    return dichotomie(val, t, dim_t, 0, dim_t - 1, 0, True)

'''appel de recherche dichotomique'''

tab10 = [i for i in range(10)] # tab10 est bien rangé par ordre croissant

#for i in range(len(tab10)):
#    print(tab10[i] )

# 3 est présent dans tab10
rep_vrai = trouve(3, tab10, len(tab10))

# 13 n'est pas présent dans tab10
rep_fausse = trouve(13, tab10, len(tab10))

assert rep_vrai
assert not(rep_fausse)

appel  1  , 0   9   4   4 (g, d, m, t[m])
appel  2  , 0   3   1   1 (g, d, m, t[m])
appel  3  , 2   3   2   2 (g, d, m, t[m])
appel  4  , 3   3   3   3 (g, d, m, t[m])
recherche gagnante après   4 appels
appel  1  , 0   9   4   4 (g, d, m, t[m])
appel  2  , 5   9   7   7 (g, d, m, t[m])
appel  3  , 8   9   8   8 (g, d, m, t[m])
appel  4  , 9   9   9   9 (g, d, m, t[m])
terminaison après   5 appels et g > d:  10   9

22.1.6. Exercice. (palindrome … encore)#

Dans l’exercice de la feuille 1, on a défini et donné un algorithme itératif qui vérifie si un mot est ou non un palindrome.

Donner une version récursive de cette vérification.

def est_palin(s: str, g: int, d: int) -> bool:
    '''
    verifie si s[g, d[ est ou non un palindrome
    '''
    if g < d:
        if s[g] != s[d-1]:
            return False
        else:
            return est_palin(s, g+1, d-1)
    return True
    
def est_palindrome(s: str, n: int) -> bool:
    '''
    verifie si la str s de longuer n est ou non un palindrome
    version recursive
    '''
    assert len(s) == n
    
    return est_palin(s, 0, n)

Vérifier sa correction avec les tests unitaires de la version itérative.

def tester_est_palindrome() -> None:
    """
    Teste la fonction est_palindrome() avec plusieurs cas.
    """
    assert est_palindrome("ete", 3) == True  # Mot palindrome
    assert est_palindrome("kayak", 5) == True  # Mot palindrome
    assert est_palindrome("mon nom", 7) == True  # Prend en compte l'espace
    assert est_palindrome("hello", 5) == False  # Pas un palindrome, mot de longueur impaire
    assert est_palindrome("helllo", 6) == False  # Pas un palindrome, mot de longueur paire
    assert est_palindrome("aa", 2) == True  # Deux lettres identiques
    assert est_palindrome("a", 1) == True  # Une seule lettre
    assert est_palindrome("", 0) == True  # Chaîne vide est un palindrome

    print("Tous les tests pour est_palindrome() sont passés.")

tester_est_palindrome()

Tous les tests pour est_palindrome() sont passés.

Expliciter l’évolution de la pile des appels des vérifications de “kayak” et de “mamama”.

Notons m= “kayak”, f() = est_palin(m, ) et g() = est_palindrome()

Notons m= “mamama”, f() = est_palin(m, ) et g() = est_palindrome(),

22.1.7. Exercice. (produit scalaire … encore)#

Dans l’exercice de la feuille 1, on a écrit un algorithme itératif qui calcule le produit scalaire de deux vecteurs de taille $n$.

Donner une version récursive de ce calcul.

def produit_scalaire(u1: list[float], n1: int, u2: list[float], n2: int) -> float:
    '''
    calcule et retourne le produit scalaire de u1 et u2 vecteurs de longueurs n1 == n2
    '''
    assert n1 == len(u1) and n2 == len(u2) and n1 == n2

    def ps_rec(u1: list[float], u2: list[float], n: int) -> float:
        '''
        fonction encapsulee qui 
        calcule récursivement le produit scalaire u1[0, n[ * u2[0, n[ 
        '''
        if n == 1:
            return u1[0] * u2[0]
        return (u1[n-1] * u2[n-1]) + ps_rec(u1, u2, n - 1)

    return ps_rec(u1, u2, n1) 

# Tests produit_scalaire()
assert produit_scalaire([1, 0, 0], 3, [0, 1, 0], 3) == 0.0  # vecteurs de base orthogonaux
assert produit_scalaire([1, 0, 0], 3, [1, 0, 0], 3) == 1.0  # vecteurs de base
assert produit_scalaire([1, 2, 3], 3, [-2, 1, 0], 3) == 0.0  # vecteurs orthogonaux
assert produit_scalaire([1, 1, 1], 3,[-1, -1, -1], 3) == -3.0  # 

Comme dans la feuille 1, appliquer cette version récursive pour vérifier si deux vecteurs donnés sont ou non orthogonaux.

def sont_orthogonaux(u1: list[float], n1: int, u2: list[float], n2: int) -> float:
    '''
    vérifie si u1 et u2 vecteurs de longueur n1 == n2 sont orthogonaux ou non
    '''
    assert n1 == len(u1) and n2 == len(u2) and n1 == n2
                     
    return produit_scalaire(u1, n1, u2, n2) == 0.0

def tester_orthogonalite() -> None:
    """
    Teste la fonction d'orthogonalité.
    """
    # Tests en 3D
    assert sont_orthogonaux([1, 0, 0], 3, [0, 1, 0], 3) == True  # Orthogonaux
    assert sont_orthogonaux([1, 2, 3], 3, [-2, 1, 0], 3) == True  # Non orthogonaux
    assert sont_orthogonaux([1, 1, 1], 3,[-1, -1, -1], 3) == False  # Pas orthogonaux

    # Tests en nD
    assert sont_orthogonaux([1, 2, 3, 4], 4, [-4, -3, -2, -1], 4) == False  # Pas orthogonaux
    assert sont_orthogonaux([1, 5, 2, 0], 4, [0, 2, -5, 1], 4) == True  # Orthogonaux
    assert sont_orthogonaux([1, 1, 1, 1], 4, [-1, -1, -1, -1], 4) == False  # Pas orthogonaux

    print("Tous les tests pour l'orthogonalité sont passés.")

tester_orthogonalite()

Tous les tests pour l'orthogonalité sont passés.

Feuille 2 : récursivité

Contents

22. Feuille 2 : récursivité#

22.1. Objectif 10#

22.1.1. \(\blacksquare\) Exercice.#

22.1.2. \(\blacksquare\) Exercice.#

22.1.3. \(\blacksquare\blacksquare\) Exercice. Si il n’y avait qu’un seul exercice à faire, c’est celui-ci !#

22.1.4. \(\blacksquare\) Exercice. (recherche dichotomique)#

22.1.5. \(\blacksquare\) Exercice. (recherche dichotomique)#

22.1.6. Exercice. (palindrome … encore)#

22.1.7. Exercice. (produit scalaire … encore)#