Formation I.S.N.

Somme

Exercice : sommer les éléments d'une liste

Écrire une fonction python récursive :

Entrée Une liste de nombres.
Sortie la somme des nombres de cette liste.
  • définition récursive
  • un premier code
  • splat
  • traceur
  • avec accumulateur
  • code en jouant sur les indices
  • Cas de base :
    • lorsque la liste est vide, la somme est 0.
    • lorsque la liste ne contient qu'un seul élément, la somme est la valeur de cet élément.
  • Dans les autres cas : la somme des éléments de L = [a0 , a1 , a2 , ..., an] est la somme de la liste L'= [a0 , a1 , a2 , ..., an-1] et de l'élément an.

Dans cette définition, on exprime la somme des éléments de L en fonction de la somme des éléments d'une liste strictement moins longue. Donc en réitérant le procédé, on arrivera nécessairement au cas de base et le processus récursif se terminera. 


def SommeListe(L) :    
    # cas de base 
    if L == [] : return 0
    
    # cas général
    return L[-1] + SommeListe(L[:-1]) # L[-1] : dernier élément de liste
                                      # L[:-1] : liste L tronquée 
                                      #          de son dernier élément
    
print(SommeListe([1,2,3,4]))

Décomposition sur un exemple :

sommeListe([1,2,3,4])  =   4 + sommeListe([1,2,3])
  =   4 + (3 + sommeListe([1,2]))
  =   4 + (3 + ( 2 + sommeListe([1])))
  =   4 + (3 + ( 2 + (1 + sommeListe([]))))
  =   4 + (3 + ( 2 + (1 + 0)))
  =   4 + (3 + ( 2 + 1))
  =   4 + (3 + 3)
  =   4 + 6
  =   10

Le code 


*a, b = [1,2,3,4,5]

print(a)
print(b)

affiche : 

[1, 2, 3, 4]
5

On en déduit une autre écriture du code du programme déjà présenté :


def SommeListe(L) :
    # cas de base
    if L == [] : return 0

    # cas général
    *tete, queue = L
    return queue + SommeListe(tete) 

print(SommeListe([1,2,3,4]))

ou :


def SommeListe(L) :
    # cas de base
    if L == [] : return 0

    # cas général
    tete, *queue = L
    return tete + SommeListe(queue) 

print(SommeListe([1,2,3,4]))

Pour aller plus loin sur cette utilisation de *, chercher sur le web avec les mots clefs : splat, packing, unpacking.

On peut tracer l'exécution avec python, par exemple comme suit : 


def trace(f):
	decale = 0
	def g(L):
		nonlocal decale
		if L == [] : pass
		else : print('|  ' * decale + '|--', f.__name__, '(', L ,') =', L[-1], '+', f.__name__, '(', L[:-1] ,')')
		decale += 1
		valeur = f(L)
		if L == [] : print('|  ' * decale , f.__name__, '(', L,') =', repr(valeur))
		else  : 
			print('|  ' * decale ,  L[-1], '+' , f.__name__, '(', L[:-1],') =', repr(valeur), end=" --> " )
			print(  f.__name__, '(', L,') =', repr(valeur) )
		decale -= 1
		return valeur
	return g

 

def SommeListe(L) :    
    # cas de base 
    if L == [] : return 0
    
    # cas général
    return L[-1] + SommeListe(L[:-1]) # L[-1] : dernier élément de liste
                                      # L[:-1] : liste L tronquée 
                                      #          de son dernier élément
    


SommeListe = trace(SommeListe)
SommeListe([1,2,3,4])

On obtient :

|-- SommeListe ( [1, 2, 3, 4] ) = 4 + SommeListe ( [1, 2, 3] )
|  |-- SommeListe ( [1, 2, 3] ) = 3 + SommeListe ( [1, 2] )
|  |  |-- SommeListe ( [1, 2] ) = 2 + SommeListe ( [1] )
|  |  |  |-- SommeListe ( [1] ) = 1 + SommeListe ( [] )
|  |  |  |  |   SommeListe ( [] ) = 0
|  |  |  |   1 + SommeListe ( [] ) = 1 --> SommeListe ( [1] ) = 1
|  |  |   2 + SommeListe ( [1] ) = 3 --> SommeListe ( [1, 2] ) = 3
|  |   3 + SommeListe ( [1, 2] ) = 6 --> SommeListe ( [1, 2, 3] ) = 6
|   4 + SommeListe ( [1, 2, 3] ) = 10 --> SommeListe ( [1, 2, 3, 4] ) = 10


def sommeListe(L, s = 0) :
	if L == [] : return s
	else : return sommeListe(L[:-1], s + L[-1])

 
print( sommeListe([1,2,3,4]) )


def sommeListe(L, i = 0) :
	if i == len(L) : return 0
	else : return L[i] + sommeListe(L, i+1)
	
	
print( sommeListe([1,2,3,4]) )

Le principe utilisé ici est le suivant :

sommeListe([1,2,3,4])   =  sommeListe([1,2,3,4], 0)
  =   L[0] + sommeListe([1,2,3,4], 1)
  =   L[0] + ( L[1] + sommeListe([1,2,3,4], 2))
  =   L[0] + ( L[1] + ( L[2] + sommeListe([1,2,3,4], 3)))
  =   L[0] + ( L[1] + ( L[2] + (L[3] + sommeListe([1,2,3,4], 4))))
  =   L[0] + ( L[1] + ( L[2] + (L[3] + 0)))
  =   L[0] + ( L[1] + ( L[2] + 4 ))
  =   L[0] + ( L[1] + 7)
  =   L[0] + 9
  =   10

Avec accumulateur : 


def sommeListe(L, i = 0, s = 0) :
	if i == len(L) : return s
	else : return sommeListe(L, i + 1, s + L[i])

 
print( sommeListe([1,2,3,4]) )

Traceur en ligne

On a donné ci-dessus un code permettant de "tracer" le déroulement de la fonction.

Une autre façon de détailler l'exécution est de passer par Python Tutor. Vous pouvez copier et coller le code ci-dessous :


def SommeListe(L) :    
    # cas de base 
    if L == [] : return 0
    
    # cas général
    return L[-1] + SommeListe(L[:-1]) # L[-1] : dernier élément de liste
                                      # L[:-1] : liste L tronquée 
                                      #          de son dernier élément
    
SommeListe([1,2,3,4])
dans l'éditeur de python tutor puis cliquer sur "vizualise execution" puis sur la touche "forward".

Complément Python

En langage python, on n'a évidemment aucun intérêt à programmer le calcul de la somme d'une liste comme ci-dessus.

Mais le principe utilisé dans la récursion avec accumulateur peut permettre de mieux saisir les outils de programmation fonctionnelle de python : 


from functools import reduce

s = reduce( lambda a, x : a+x, [1,2,3,4] ) 
print(s)

Dans ce calcul de la somme d'une liste, on peut comprendre le fonctionnement de reduce ainsi :

  • a joue le rôle d'accumulateur.
  • x est l' élément courant de l'itération.

Plus en détail :

  • Initialisation de a avec le premier élément de liste et de x avec la seconde valeur de la liste.
  • a devient la somme de l'ancienne valeur de a et la valeur courante de x, puis x prend la valeur du troisième élément de liste.
  • a devient la somme de l'ancienne valeur de a et la valeur courante de x, puis x prend la valeur du quatrième élément de liste.
  • ...

Ce schéma est bien sûr également celui de la version itérative.

Le fait que a soit initialisé avec la première valeur de la liste peut parfois être gênant. Mais reduce permet, avec un troisième argument d'initialiser explicitement a (dans ce cas, x commence avec la valeur du premier élément de la liste) :


from functools import reduce

s = reduce( lambda a, x : a+x, [1,2,3,4], 0  ) 
print(s)

Pour bien saisir le rôle du 0, donnez lui une autre valeur et testez...

Complément python

On signale au passage que python dispose d'une fonction sum pour le calcul de la somme des éléments d'une liste.


print( sum([1,2,3,4]) )