TD N1 : Récursivité¶

Il est bien entendu nécessaire d'avoir lu (et relu !) le chapitre N (récursivité) du cours avant de s'attaquer à ce TD. Et l'avoir sous la main peut aussi être utile...

I. Les exemples du cours¶

Les nombres triangulaires¶

In [1]:

def triangle1(n):
    if n==1 :
        print('*')
    else :
        print('*'*n) #affiche n caractères '*'
        triangle1(n-1)

triangle1(5)

*****
****
***
**
*

In [4]:

def triangle2(n):
    if n==1 :
        print('*')
    else :
        triangle2(n-1)
        print('*'*n) #affiche n caractères '*'
        
        

triangle2(5)

*
**
***
****
*****

In [ ]:

def triangle3(n):
    if n == 1 :
        print('*')
        return 1
    else :
        print('*'*n) #affiche n caractères '*'
        return triangle3(n-1)+n

N=5
print(f"T({N})={triangle3(N)}")

Le nombre d'or¶

Vous connaissez déjà probablement le nombre d'or que l'on note souvent $\varphi$ et qui apparait dans de nombreux domaines liés à l'esthétisme (voir par exemple le nombre d'or sur Wikipedia). Parmi les curiosités, voici ci-dessous une manière originale d'approcher sa valeur: $$\varphi = 1+\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{1+\ldots}}}$$ Mathématiquement, l'objet précédent s'appelle une fraction continue. Pour la calculer, cela revient à déterminer la limite de la suite $(u_n)$ définie par récurrence: $$\left\{ \begin{array}{l} u_1 = 1\\ u_{n+1} = 1 + \dfrac{1}{u_n} \end{array}\right.$$

In [ ]:

# Version itérative

def u_iter(n : int) -> float :
    assert n >= 1
    u = 1
    for _ in range(2,n+1) :
        u = 1 + 1/u
    return u

for n in [5,10,100]:
    print(u_iter(n))

In [ ]:

# Version récursive 

def u_rec(n :int) -> float :
    if n == 1 : 
        return 1
    else :
        return 1+1/u_rec(n-1)
for n in [5,10,100]:
    print(u_rec(n))

Exécuter votre code avec u_rec(5) sur le site python tutor et constater que l'on empile 5 fois la fonction en mémoire...

La suite de Fibonacci¶

Pour se rendre compte du problème, regardons de plus près le calcul des termes de la suite emblématique de Fibonacci: $$ \left\{ \begin{array}{l} F_0=F_1=1\\ F_n = F_{n-1}+F_{n-2} \end{array} \right.$$ Une façon simple de programmer le calcul de cette suite est d'utiliser le principe de récurisivité de la façon suivante :

In [ ]:

def fibo1(n : int) -> int:
    """ calcule le n-ieme terme de la suite de Fibonacci"""
    if n==0 or n==1 : # test d'arrêt
        return 1
    else :
        return fibo1(n-1)+fibo1(n-2)

In [ ]:

n=5
print(f"F({n})={fibo1(n)}")

Pour évaluer le nombre d'appels faits on peut introduire une variable globale de la façon suivante :

In [ ]:

def fibo1(n : int) -> int:
    """ calcule le n-ieme terme de la suite de Fibonacci par une méthode récursive"""
    global c
    c += 1
    if n==0 or n==1 : # test d'arrêt
        return 1
    else :
        return fibo1(n-1)+fibo1(n-2)

for n in [2,3,4,5,10] :
    c = 0
    fibo1(n)
    print(f"Nombre d'appels récursifs pour caluler F({n}) : {c}")

On constate que pour évaluer $F_n(5)$ on fait 15 appels à la fonction. Tester la fonction fibo1 sur python tutor pour voir ce qu'il se passe.

Pour comprendre ce qu'il se passe on peut construire l'abre des appels récursifs:

Cette façon de programmer est dans ce cas inefficace en nombres d'appels et en occupation mémoire (elle calcule plusieurs fois les même choses !) Elle est de plus inutilisable si $n$ est grand...

Il sera bien pluis efficace dans ce cas de programmer une version itérative, par exemple comme cela :

In [ ]:

def fibo2(n : int)-> int :
    """ calcule le n-ieme terme de la suite de Fibonacci par une méthode itérative"""
    if n==0 or n==1 :
        return 1
    uprec , ucour = 1 , 1
    for i in range(2,n+1):
        uprec , ucour = ucour , uprec+ucour
    return ucour

n=5
print(f"F({n})={fibo1(n)}")

Conclusion¶

Les algorithmes écrits sous forme récursive sont en principe élégants, simples à concevoir mais souvent d'une performance médiocre et peu adaptée pour un utilisation avec des données de grande taille. La complexité est souvent exponentielle ($O(a^n)$) ce qui empêche de travailler pour des valeurs de $n$ au delà de 50...

II. À vous de "jouer" : quelques exemples classiques pour se familiariser avec la récursivité¶

1. Factorielle¶

Q1 Écrire une fonction itérative (c'est à dire avec une boucle) facto1(n :int) -> int qui calcule $n!=1\times2\times3\ldots\times n$.

In [ ]:

def facto1(n : int) -> int:
    """ version itérative"""
    pass
    # à compléter

Q2 Écrire ensuite une fonction récursive facto2(n :int) -> int qui calcule $n!$.

In [ ]:

def facto2(n : int) -> int:
    """ version récursive"""
    pass
    # à compléter

In [ ]:

# On affiche quelques résultats :

for n in range(5):
    print(f"{n}!= {facto2(n)}")

2. Exponentiation rapide¶

On souhaite calculer $a^n$ pour $a\in \mathbb R$ et $n\in\mathbb N$.

Q3.a. Écrire une fonction itérative menant au résultat et donner sa complexité.

In [ ]:

def puiss_iter(a : float, n : int) -> float :
    """ calcule a^n par une méthode itérative"""
    pass
    # ... à compléter
    
print(puiss_iter(2,10))

Q3.b. Quelle est la complexité de cette fonction?

Réponse : .....

On peut faire mieux en remarquant que: $$\left\{ \begin{array}{l} a^0 =1\\ a^{2p} = (a^p)^2\\ a^{2p+1} = a*(a^p)^2 \end{array}\right.$$

Q4.a Écrire les étapes du calcul pour $a^{37}$ et donner le nombre d'étapes :

Réponse : nombre d'étapes = .....

Q4.b. Écrire une fonction récursive en utilisant ce principe.

In [4]:

def puiss_rec(a : float, n : int) -> float :
    """ calcule a^n par la méthode de l'exponentiation rapide"""
    pass
    #à compléter
    
print(puiss_rec(2,10))

Q4.c Déterminer la complexité de cette fonction.

Réponse : ....

3. Dichotomie¶

Le principe de recherche dans un tableau trié que l'on a déjà rencontré peut s'écrire de façon simple par une version récursive. Rappelons la version itérative déjà programmée :

In [ ]:

def dichotomie_iter(L : list, e : int) -> bool :
    a,b = 0,len(L)-1 # les indices gauche et droite
    
    while a<=b :
        m = (a+b)//2 # division entiere
        if e == L[m]:
            return True
        else :
            if e < L[m] :
                b = m-1
            else:
                a = m+1
    return False

In [ ]:

# on teste :
L = list(range(1000))
print("100 appartient à L ?",dichotomie_iter(L,100))
print("-10 appartient à L ?",dichotomie_iter(L,-10))

Voici en langage naturel une version récursive de l'algo de dichotomie :

Recherche(L,e,d,f)
    // cherche l'élément e dans la liste L, entre les indices d et f inclus (pour début et fin).
    // Renvoie vrai si l'élément apparait, faux si l'élément n'apparaît pas.

    Si f<d renvoyer faux
    Sinon :
        Calculer la moyenne m entre d et f (arrondie à l'entier inférieur)
        Si L[m]=e renvoyer vrai // on pourrait renvoyer aussi m...
        Si L[m]<e renvoyer ... à compléter ... //rechercher dans la moitié droite de l'intervalle
        Si L[m]>e renvoyer ... à compléter ... //rechercher dans la moitié gauche de l'intervalle

Q5 Écrire la traduction python de cet algorithme

In [ ]:

def dichotomie_rec(L : list, e : int, d : int, f : int) -> bool :
    """
    Cherche l'élément e dans la liste L, entre les indices d et f inclus (pour début et fin).
    Renvoie True si l'élément apparait, False si l'élément n'apparaît pas.
    """
    if f<d : # test d'arrêt
        return False
    else :
        m = (d+f)//2
        # ... à compléter ...

In [ ]:

# on teste :
L = list(range(1000))
print("100 appartient à L ?",dichotomie_rec(L,100,0,999))
print("-10 appartient à L ?",dichotomie_rec(L,-10,0,999))

4. Tours de Hanoi¶

Un exemple emblématique de l'utilisation de la récursivité est la résolution du jeu des tours de Hanoï:

Une tour de Hanoï de hauteur N, appelée tour(N) dans la suite, est constituée d’un ensemble de N disques de diamètres différents, percés d’un trou central, et enfilés sur un plot vertical par ordre de diamètre décroissant. On dispose de trois plots appelés 1, 2, 3. Une tour(N) est initialement installée sur le plot 1.

Le problème consiste à la déplacer vers le plot 3, en utilisant le plot 2 comme lieu de rangement intermédiaire et en respectant les règles suivantes :

on ne peut déplacer qu’un disque à la fois ;
on ne peut déplacer qu’un disque situé au sommet de sa pile ;
on ne peut poser un disque que sur un disque de diamètre supérieur ou sur un plot vide.

Q6 Essayer de voir si vous trouvez comment gagner à ce jeu...

Q7 La figure ci-dessous montre que si l'on sait déplacer $n-1$ disques, alors on sait aussi en déplacer $n$... Cela permet d'écrire une fonction récursive qui donne une solution au problème...

Compléter et tester la fonction suivante:

In [ ]:

def hanoi(n,dep,arr,libre):
    if n == 1 :
        print(f"deplacer 1 disque de {dep} vers {arr}")
    else :
        # à compléter  : hanoi(n-1, ...... )
        print(f"deplacer 1 disque de {dep} vers {arr}")
        # à compléter  : hanoi(n-1, ...... )

In [ ]:

hanoi(3,'A','C','B')

IV. Pour aller plus loin¶

On pourra se balader sur un site très complet et très visuel avec beaucoup d'exemples : site de Mickaël Péchaud

In [ ]: