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.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: Votre implémentation ne peut accéder à la liste passée en paramètre que via les méthodes de la classe List. En effet, dans un bon design orienté-objet, il n'est pas permis d'accéder aux variables d'instance, ici first_elem et tail_list en dehors de la classe elle-même. Ce sont donc exclusivement le constructeur ou les autres méthodes de cette classe qui peuvent assigner, modifier ou renvoyer les valeurs de ces variables. Rien ne vous empêche, par contre, de définir une seconde liste qui pourrait servir à mémoriser un résultat intermédiaire du calcul, pour autant que vous respectiez le même principe pour cette seconde liste: accès ou modification de la liste uniquement via les méthodes déjà définies de la classe List.

Vous n'êtes pas non plus sensé modifier ou étendre la classe List. Ce n'est pas nécessaire pour résoudre l'exercice.

def cum_sum(l: List):
    """
    Calcule la liste des sommes cumulées des éléments de `l`
    par itération
    pre: -
    post: retourne une liste dont le `i`^ième élément est la somme
        des `i` premiers éléments de `l`
    """

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.

Bien que votre implémentation soit "aussi itérative que possible", des appels récursifs pourraient être effectués. Sélectionnez, parmi les propositions suivantes, celles qui induisent des appels récursifs.