Kurs-Liste Einloggen

Information

Author(s) Vincent Branders, Pierre Dupont
Deadline 01/04/2026 14:00:00
Abgabenlimit No limitation

Einloggen

Einloggen

[TP07] Somme cumulée d'une liste - Récursif

Vous avez appris précédemment comment utiliser la récursion sur des entiers et des tableaux.

Dans cette séance-ci, nous travaillerons la récursion sur les listes. Ce type abstrait de données présente un exemple de récursion structurelle : la liste est définie soit comme la liste vide, soit comme un élément suivi d'une liste.

Une telle implémentation vous est fournie par la classe List.py.

La figure suivante représente graphiquement un objet de type List qui contient les entiers de 1 à 5.

\begin{equation*} \boxed{1}\rightarrow\boxed{\boxed{2}\rightarrow\boxed{\boxed{3}\rightarrow\boxed{\boxed{4}\rightarrow\boxed{\boxed{5}\rightarrow\!\bullet}}}} \end{equation*}

On vous demande d'implémenter un algorithme avec récursion. Avant d'élaborer votre algorithme, détaillez :

  1. le cas de base,
  2. comment traiter le cas de base,
  3. comment construire la solution actuelle (taille n) si je connais une solution pour un problème plus petit (par exemple de taille n-1).
Question 1: Somme cumulée d'une liste (récursif)

Vous êtes chargés d'implémenter la fonction suivante en Python. Pour préparer votre code, vous pouvez télécharger le fichier cum_sum_rec.py qui contient la signature de la fonction et quelques exemples de tests. Vous pouvez également télécharger le fichier List.py qui contient une implémentation de liste.

Note: Lorsqu'il vous est demandé d'implémenter une fonction, vous êtes invités à ne remplir que le corps de la fonction à implémenter.

Attention: Vous aurez sans doute besoin d'une fonction auxiliaire avec un argument en plus pour implémenter la fonction récursive.

Attention: Votre implémentation ne peut accéder à la liste passée en paramètre que via les méthodes de la classe List. Aucun accès aux variables d'instance de cette classe ne doit avoir lieu, en dehors de ces méthodes. Il n'est pas non plus nécessaire d'étendre ou de modifier cette classe.

def cum_sum_rec(l: List):
    """
    Calcule la liste des sommes cumulées des éléments de `l`
    par récursion
    pre: -
    post: retourne une liste dont le `i`^ième élément est la somme
        des `i` premiers éléments de `l`
    """
    def aux_sum_rec(..., ...):
    """
    Fonction auxiliaire récursive
    """
        pass
Question 2: Complexité temporelle

Quelle est la complexité temporelle de l’algorithme ? Choisissez la borne la plus simple et la plus stricte possible.

On suppose que vous n'effectuez pas d'opérations inutiles.