Aller au contenu

Récursivité et listes

Arbre d'appel

On définit la fonction f par le code suivant :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def f(x):
    """ int -> None """
    if x <= 2:
        print("Puf")
    else:
        print("Pof")
        f(x - 1)
        if x % 2 == 0:
            print("Pif")
        else:
            print("Paf")
        f(x - 2)
        print("Pef")

  1. Dresser l'arbre d'appel de l'instruction f(4). Vous indiquerez :

    • à gauche des nœuds les numéros des lignes exécutées avant le premier appel récursif ;
    • sous les appels les numéros des lignes exécutées entre deux appels récursifs ;
    • à droite des nœuds les numéros des lignes exécutées après les appels récursifs ;
    • En déduire l'affichage réalisé par f(4).
    1
    f(4) 

    Pof
Pof
Puf
Paf
Puf
Pef
Pif
Puf
Pef

Listes

Cet exercice porte sur le type Liste définit en tp. On en rappelle ci-dessous l'interface.

Fonction Description
creer_vide() Renvoie une liste vide
est_vide(l) Renvoie True si et seulement si la liste est vide
tete(l) Renvoie le premier élément de la liste \(l\) (l'élément dit de tête)
queue(l) Renvoie la liste constituée de tous les éléments de \(l\) à l'exception du premier
ajoute(l, e) Renvoie la liste constituée de l'élément \(e\), suivi des éléments de \(l\)
affiche(l) Affiche la liste des éléments de \(l\) sur la sortie standard, séparés par le caractère -.
  La liste vide est représentée par x.

Vous n'utiliserez que ces fonctions pour répondre aux questions de l'énoncé.

  1. Écrire une fonction python récursive appartient qui étant donné une liste l et un élément e, renvoie True si et seulement si l'élément e est un des éléments de la liste l. 

    1
2
3
4
5
6
7
    def appartient(l, e):
    """ Liste, int -> bool
    Détermine si l'élément e fait partie de la liste l """
    if est_vide(l):
        return False
    else:
        return tete(l) == e or appartient(queue(l), e)

  2. Souhaite écrire le code python d'une fonction que_des_pairs, récursive, qui étant donné une liste l d'entiers renvoie la liste des éléments de l qui sont pairs (ceux-ci apparaîtront dans la liste résultante dans le même ordre que dans la liste initiale).

    1. Compléter le tableau ci-dessous. On représentera une liste par la liste de ses éléments entre parenthèses, sans se soucier de l'implémentation du type Liste. Ainsi la liste dont le premier élément est 1 et le second élément est 2 sera représentée par (1, 2).

      l que_des_pairs(l)
      () ()
      (1) ()
      (2) (2)
      (1, 4, 15, 6, 9) (4, 6)
      (42, 3, 9, 4, 1, 4, 2) (42, 4, 4, 2)

    2. Écrire le code python d'une fonction que_des_pairs qui réponde à la question de l'énoncé. 

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
      def que_des_pairs(l):
    """ Liste -> Liste
    Renvoie la liste des éléments pairs de l """
    if est_vide(l):
        return creer_vide()
    else:
        avant = que_des_pairs(queue(l))
        if tete(l) %2 == 0:
            return ajoute(avant, tete(l))
        else:
            return avant

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
      l = creer_vide()
affiche(que_des_pairs(l))
l = ajoute(creer_vide(), 1)
affiche(que_des_pairs(l))
l = ajoute(creer_vide(), 2)
affiche(que_des_pairs(l))
l = ajoute(ajoute(ajoute(ajoute(ajoute(creer_vide(), 9), 6), 15), 4), 1)
affiche(que_des_pairs(l))
l = ajoute(ajoute(ajoute(ajoute(ajoute(ajoute(ajoute(creer_vide(), 2), 4), 1), 4), 9), 3), 42)
affiche(que_des_pairs(l))

      x
x
2 - x
4 - 6 - x
42 - 4 - 4 - 2 - x