Course list Sign in

Information

Author(s) Vincent Branders, Pierre Dupont
Deadline 27/03/2024 14:00:00
Submission limit No limitation

Sign in

Sign in

[TP06] Somme des n premiers éléments d'une liste - Récursif

Implémentez une version récursive de l'algorithme itératif étudié dans l'exercice précédent. Votre implémentation récursive doit garder la même complexité que l'algorithme itératif.

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).

Rappel du problème :

Supposons que l'on dispose d'un tableau t d'entiers et que l'on veuille connaître la somme de ses n premiers éléments. Par exemple, si les entrées sont

\begin{align*} t & = \boxed{10 \,\vert\, 20 \,\vert\, 30 \,\vert\, 40 \,\vert\, 50 \,\,}\\ n & = 3 \end{align*}

le résultat attendu est 60.

Question 1: Le cas de base

Identifiez, parmi les propositions suivantes, celle qui correspond au cas de base de l'algorithme récursif.

Question 2: Somme des premiers éléments (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 sum_first_rec.py qui contient la signature de la fonction et quelques exemples de tests.

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.

def sum_first_rec(t, n):
    """
    Calcule la somme des `n` premiers éléments de `t` par récursion
    pre: `t` un tableau (list) non vide
    pre: `n` un entier tel que 1<=`n`<=len(`t`)
    post: retourne la somme des `n` premiers éléments de `t`
    """