Récursivité

3.3.3. Récursivité#

3.3.3.1. Parcours récursif d’une liste#

On va voir dans ce chapitre une nouvelle façon d’écrire des fonctions qui s’appellent elle même. On parle pour ça de récursivité et de fonctions récursives. Il existe un lien assez fort entre ces fonctions récursives et la notion de récurrence vue en mathématiques, que nous ne développerons pas dans un premier temps.

On importe la structure de liste telle que définie préalablement.

from cours.structures import Liste

On définit une première fonction qui s’appelle elle même.

def Dernier(liste, cdr):
    if liste.estVide():
        return cdr
    else:
        cdr = liste.queue()[0]
        return Dernier(liste.queue()[1], cdr)

Cette fonction renvoie l’élément qui a été sortie en dernier tant que la liste n’est pas vide et sinon, elle renvoie le dernier élément retiré de la liste et la liste des éléments restants. On initialise cet élément à renvoyé (ici cdr par None de façon à ne rien renvoyer lorsque la liste est vide.

Voyons sur quelques exemples.

liste = Liste(1,2,3,4)
Dernier(liste,None)

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[3], line 2
      1 liste = Liste(1,2,3,4)
----> 2 Dernier(liste,None)

Cell In[2], line 2, in Dernier(liste, cdr)
      1 def Dernier(liste, cdr):
----> 2     if liste.estVide():
      3         return cdr
      4     else:

AttributeError: 'Liste' object has no attribute 'estVide'

liste = Liste(1)
Dernier(liste,None)

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[4], line 2
      1 liste = Liste(1)
----> 2 Dernier(liste,None)

Cell In[2], line 2, in Dernier(liste, cdr)
      1 def Dernier(liste, cdr):
----> 2     if liste.estVide():
      3         return cdr
      4     else:

AttributeError: 'Liste' object has no attribute 'estVide'

liste = Liste()
Dernier(liste,None)

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[5], line 2
      1 liste = Liste()
----> 2 Dernier(liste,None)

Cell In[2], line 2, in Dernier(liste, cdr)
      1 def Dernier(liste, cdr):
----> 2     if liste.estVide():
      3         return cdr
      4     else:

AttributeError: 'Liste' object has no attribute 'estVide'

On peut visualiser l’appel de fonctions :

##!pip3 install pycallgraph2

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Cell In[7], line 1
----> 1 from pycallgraph2 import PyCallGraph
      2 from pycallgraph2 import Config
      3 from pycallgraph2 import GlobbingFilter

ModuleNotFoundError: No module named 'pycallgraph2'

L’appel est bien récursif, comme peut le voir ici

3.3.3.2. Exercices#

Écrire une fonction itérative (non récursive) qui renvoie le dernier élément.

def Dernier(Liste):
    pass
Hide code cell source 
def Dernier(Liste):
    ### BEGIN SOLUTION
    dernier = None
    while not Liste.estVide():
        dernier , Liste = Liste.queue()
    return dernier
    ### END SOLUTION

Tester cette fonction sur quelques exemples.

liste = Liste(1,2,3,4)
assert Dernier(liste) == 4
liste = Liste(1)
assert Dernier(liste) == 1
liste = Liste()
assert Dernier(liste) == None

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[10], line 2
      1 liste = Liste(1,2,3,4)
----> 2 assert Dernier(liste) == 4
      3 liste = Liste(1)
      4 assert Dernier(liste) == 1

Cell In[9], line 4, in Dernier(Liste)
      1 def Dernier(Liste):
      2     ### BEGIN SOLUTION
      3     dernier = None
----> 4     while not Liste.estVide():
      5         dernier , Liste = Liste.queue()
      6     return dernier

AttributeError: 'Liste' object has no attribute 'estVide'

Écrire une fonction itérative qui donne la longueur de la liste.

def longueur(liste):
    pass
Hide code cell source 
def longueur(liste):
    ### BEGIN SOLUTION
    l = 0
    while not liste.estVide():
        l = l + 1
        liste = liste.queue()[1]
    return l
    ### END SOLUTION

Tester cette fonction sur quelques exemples.

liste = Liste(1,2,3,4)
assert longueur(liste) == 4
liste = Liste(1)
assert longueur(liste) == 1
liste = Liste()
assert longueur(liste) == 0

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[13], line 2
      1 liste = Liste(1,2,3,4)
----> 2 assert longueur(liste) == 4
      3 liste = Liste(1)
      4 assert longueur(liste) == 1

Cell In[12], line 4, in longueur(liste)
      1 def longueur(liste):
      2     ### BEGIN SOLUTION
      3     l = 0
----> 4     while not liste.estVide():
      5         l = l + 1
      6         liste = liste.queue()[1]

AttributeError: 'Liste' object has no attribute 'estVide'

Écrire une fonction récursive qui donne la longueur de la liste.

def longueur(liste):
    pass
Hide code cell source 
def longueur(liste):
    ### BEGIN SOLUTION
    if liste.estVide():
        return 0
    else:
        return longueur(liste.queue()[1]) + 1
    ### END SOLUTION

Tester cette fonction sur quelques exemples.

liste = Liste(1,2,3,4)
assert longueur(liste) == 4
liste = Liste(1)
assert longueur(liste) == 1
liste = Liste()
assert longueur(liste) == 0

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[16], line 2
      1 liste = Liste(1,2,3,4)
----> 2 assert longueur(liste) == 4
      3 liste = Liste(1)
      4 assert longueur(liste) == 1

Cell In[15], line 3, in longueur(liste)
      1 def longueur(liste):
      2     ### BEGIN SOLUTION
----> 3     if liste.estVide():
      4         return 0
      5     else:

AttributeError: 'Liste' object has no attribute 'estVide'
Contenu