Somme d'une liste.
Écrire une fonction python récursive :
- Entrée : une liste de nombres,
- Sortie : la somme des nombres de cette liste.
Pour programmer de façon récursive les fonctions demandées, essayez de suivre le schéma suivant :
- Définir directement l'image dans les cas simples.
- Dans les autres cas, définir l'image en fonction d'un cas plus 'simple'.
Dans ce descriptif schématique, 'simple' peut désigner diverses situations :
- Dans le cas d'une liste, le cas le plus simple peut être le cas d'une liste vide ou d'une liste n'ayant qu'un seul élément et 'plus simple' désigne alors une liste ayant strictement moins d'éléments.
- Dans le cas du travail sur un entier, 'définir en fonction d'un cas plus simple' peut être 'définir en fonction d'un entier plus petit' ou dans d'autres cas 'définir en fonction d'un entier ayant strictement moins de chiffres', ou encore d'un 'entier ayant moins de facteurs premiers' ou encore ...
- ...
On présente ci-dessous plusieurs codages possibles. Attachez vous à bien saisir le fonctionnement de chaque code donné.
Le principe
Le 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.
Premier codage possible
On a utilisé ci-dessous L.pop() sur une liste L = [a0, a1, ..., an-1, an].
La ligne a = L.pop() a deux effets :
- elle supprime l'élément an de L.
- et elle affecte la valeur de an à la variable a.
Après cette instruction a = L.pop() :
- L est donc devenue : L = [a0, a1, ..., an-1].
- et a contient la valeur an.
def SommeListe(L) :
if L == [] : return 0
a = L.pop() # on supprime le dernier élément de la liste L
# et on l'affecte à a
return a + SommeListe(L)
print( SommeListe([1,2,3,4]) )
Détaillons :
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
Second codage
Pour une liste L, le dernier élément est obtenu par L[-1] et la liste constituée de tous les éléments de L
sauf le dernier est L[ : -1].
On peut donc réécrire le programme précédent comme suit :
def SommeListe(L) :
if L == [] : return 0
return L[-1] + SommeListe(L[:-1])
print( SommeListe([1,2,3,4]) )
On peut bien entendu ajouter le premier élément de la liste au lieu du dernier :
def SommeListe(L) :
if L == [] : return 0
return L[0] + SommeListe(L[1:])
print( SommeListe([1,2,3,4]) )
Variante :
Dans cette version, on voit l'une des utilisations intéressantes de la possibilité de donner une valeur par défaut à un paramètre : lors de l'appel initial, on n'a pas besoin d'indiquer un second paramètre. Mais ce second paramètre joue un rôle essentiel dans les appels récursifs.
def SommeListe(L, s = 0) :
if L == [] : return s
a = L.pop() # on supprime le dernier élément de la liste L
# et on l'affecte à a
return SommeListe(L, s + a)
print( SommeListe([1,2,3,4]) )
Détaillons :
SommeListe([1,2,3,4])
= SommeListe([1,2,3,4], s = 0)
= SommeListe([1,2,3], s = 0+4)
= SommeListe([1,2], s = 4+3)
= SommeListe([1], s = 7+2)
= SommeListe([], s = 9+1)
= 10
On pourrait aussi écrire cette variante comme suit :
def SommeListe(L, s = 0) :
if L == [] : return s
return SommeListe(L[:-1], s + L[-1])
print(SommeListe([1,2,3,4]))
Avec les indices
On peut également éviter d'agir sur la liste en ne travaillant qu'avec les indices.
Par exemple :
def somme(liste) :
def som( j, s = 0 ) :
if j < 0 : return s
else : return som( j-1, s + liste[j] )
return som(len(liste)-1)
L = [1,2,3]
print(somme(L))
Ou encore (en ajoutant l'élément de tête plutôt que l'élément de fin de liste) :
def somme(liste) :
lg = len(liste)
def som( j, s = 0 ) :
if j >= lg : return s
else : return som( j+1, s + liste[j] )
return som(0)
L = [10,20,30,40]
print(somme(L))
Détaillons :
somme([10, 20, 30, 40])
= som( j = 0, s = 0 )
= som( j = 1, s = 10 )
= som( j = 2, s = 10+20 )
= som( j = 3, s = (10+20)+30 )
= som( j = 4, s = ((10+20)+30)+40 )
= ((10+20)+30)+40
Produit d'une liste.
Écrire une fonction python récursive :
- Entrée : une liste de nombres,
- Sortie : le produit des nombres de cette liste.
Il suffit d'adapter un peu le cas de la somme vue précédemment.
def ProduitListe(L) :
if L == [] : return 1
a = L.pop() # on supprime le dernier élément de la liste L
# et on l'affecte à a
return a * ProduitListe(L)
print(ProduitListe([1,2,3,4]))
Variante :
def ProduitListe(L, p=1) :
if L == [] : return p
a = L.pop() # on supprime le dernier élément de la liste L
# et on l'affecte à a
return ProduitListe(L, p*a)
print(ProduitListe([1,2,3,4]))
Minimum d'une liste.
Écrire une fonction python récursive :
- Entrée : une liste de nombres.
- Sortie : le plus petit des nombres de cette liste.
Cas de base : si la liste ne contient qu'un élément, cet élément est le minimum.
Lorsque la liste L=[a0, a1, a2, ..., an] contient plus d'un élément, le minimum de la liste L est le plus petit des deux nombres an et minimum([a0, a1, a2, ..., an-1]).
def MinimumListe(L) :
"""L est une liste de nombres non vide.
La fonction retourne un élément de valeur minimum."""
if len(L)==1 : return L[0]
a=L.pop() # on supprime le dernier élément de la liste L
# et on l'affecte à a
b=MinimumListe(L) # minimum de la liste sans l'élément de fin
if a<b : return a
else : return b
print(MinimumListe([10,2,15,3,4,21]))
On peut décomposer comme suit cette fonction :
def minimum(a,b) :
""" retourne le plus petit des nombres a et b."""
if a<b : return a
else : return b
def minimumListe(L) :
""" L : liste non vide.
Retourne un des éléments de plus petite valeur de la liste."""
if len(L)==1 : return L[0]
return minimum(L[0], minimumListe(L[1:]))
print(minimumListe([2,8,-2,45,74,0]))
Variante :
def MinimumListe(L) :
"""L est une liste de nombres non vide.
La fonction retourne un élément de valeur minimum."""
if len(L)==1 : return L[0]
if L[0]<L[1] : # on efface le plus grand entre L[0] et L[1]
del(L[1])
else :
del(L[0])
return MinimumListe(L)
print(MinimumListe([10,2,15,3, -3,4,21]))
Variante.
Dans cette variante, on utilise le fait que n < float('inf') (où n est de type int) vaut toujours True
(on "compare" la valeur de n à l'infini).
Les cas de base : si L est vide, le minimum sera infini. Si L est de longueur 1, le minimum est l'unique élément de la liste.
Cas générique : le minimum d'une liste L=[a1, a1, a2, ..., an] est le plus petit des deux nombres minimumListe( L=[a1, a1, a2, ..., an//2-1] ) et minimumListe( L=[an//2, an//2+1, ..., an] ).
def minimum(a,b) :
""" retourne le plus petit de deux nombres."""
if a < b : return a
else : return b
def miniListe(L) :
if L==[] : return float('inf')
if len(L)==1 : return L[0]
l=len(L)//2
return minimum(miniListe(L[:l]),miniListe(L[l:]))
L=[3,8,1,45,0,47,145,2,-5,9]
print(miniListe(L))
Présence dans une liste.
Recherche 1.
Écrire une fonction python récursive :
- Entrée : une liste L de nombres et un nombre x.
- Sortie : False si x n'est pas dans L, True sinon.
Recherche 2.
Écrire une fonction python récursive :
- Entrée : une liste L de nombres et un nombre x.
- Sortie : None si x n'est pas dans L, l'indice d'une occurrence de x dans L lorsque x est présent dans L.
Recherche 1.
def RechercheDansListe(L,a) :
"""L est une liste de nombres.
La fonction retourne False si le nombre a n'est pas dans L,
True s'il est dans L."""
if L==[] : return False
b=L.pop() # on supprime le dernier élément
# de la liste et l'affecte à b
if a==b : return True
return RechercheDansListe(L,a)
L=[10,2,5,7,8,9,15,21]
a=35
print(RechercheDansListe(L,a))
Recherche 2.
def RechercheDansListe(L,a) :
"""L est une liste de nombres.
La fonction retourne None si le nombre n'est pas dans L,
l'indice d'une occurrence de a dans L sinon."""
if L==[] : return
b=L.pop() # on supprime le dernier élément
# de la liste et l'affecte à b
if a==b : return len(L)
return RechercheDansListe(L,a)
L=[10,2,5,7, 2,8,9,15,21]
a=35
print(RechercheDansListe(L,a))
Variante :
def RechercheDansListe(L,a,indice=0) :
"""L est une liste de nombres.
La fonction retourne None si le nombre n'est pas dans L,
l'indice d'une occurrence de a dans L sinon."""
if indice==len(L) : return
if a==L[indice] : return indice
return RechercheDansListe(L,a, indice+1)
L=[10,2,5,7, 2,8,9,15,21]
a=21
print(RechercheDansListe(L,a))
Nombre de 'a'.
Écrire une fonction python récursive :
- Entrée : une chaîne de caractères.
- Sortie : le nombre d'occurrences de la lettre 'a' dans la chaîne.
def Nombre_a(ch, s=0) :
if ch=='' : return s
if ch[0]=='a' : return Nombre_a(ch[1:], s+1)
else : return Nombre_a(ch[1:], s)
print(Nombre_a('abracadabra'))
print(Nombre_a('python'))
On rappelle que ch[1:] est la sous-chaîne de ch constituée de tous les caractères de ch sauf le premier.
La même programmation avec une "astuce" pour un code plus concis :
def Nombre_a(ch, s=0) :
if ch=='' : return s
return Nombre_a(ch[1:], s+(ch[0]=='a'))
print(Nombre_a('abracadabra'))
print(Nombre_a('python'))
Variante :
def Nombre_a(ch, indice=0) :
if indice==len(ch) : return 0
if ch[indice]=='a' : return 1+Nombre_a(ch, indice+1)
else : return Nombre_a(ch, indice+1)
print(Nombre_a('abracadabra'))
print(Nombre_a('python'))
Avec le même gain en concision que plus haut :
def Nombre_a(ch, indice=0) :
if indice==len(ch) : return 0
return (ch[indice]=='a')+Nombre_a(ch, indice+1)
print(Nombre_a('abracadabra'))
print(Nombre_a('python'))
Du binaire au décimal.
Écrire une fonction python récursive :
- Entrée : l'écriture binaire d'un entier (type str). Par exemple 2 est donné par '10'.
- Sortie : l'écriture décimale de cet entier (type int).
Si besoin : réviser.
def binToDec( n , p=0 ) :
""" n est un entier en binaire, type string.
Par exemple 3 est donné par n='11'.
p sera un exposant d'une puissance de 2."""
if n=='' : return 0
unite=int(n[-1]) # chiffre des unités
n=n[:-1] # on tronque n en enlevant le chiffre des unités
return unite*2**p + binToDec( n, p+1 )
print(binToDec('101'))
Variante.
Dans cette variante, on utilise la remarque suivante (à généraliser) : \[ n = a_4 \times 2^4 +a_3 \times 2^3 + a_2 \times 2^2 + a_1 \times 2^1 + a_0 \] s'écrit aussi : \[ n = \left(\left(\left( \left( a_4 \times 2 +a_3 \right) \times 2 + a_2 \right) \times 2 + a_1 \right) \times 2 \right) + a_0 \]
def binToDec(n, s=0) :
if n=='' : return s
return binToDec(n[1:], s*2+int(n[0]))
n=24
n=bin(n)[2:]
print(binToDec(n))
Du décimal au binaire.
Écrire une version récursive de l'algorithme des divisions en cascade permettant de donner l'écriture binaire (type list) de l'entier donné en entrée (type int).
Par exemple, decToBin(13) retournera la liste [1,1,0,1].
Si besoin : réviser.
def decToBin(n, L=[]) :
if n==0 :
L.reverse()
return L
L.append(n%2) # ajout du reste n%2 en fin de liste
return decToBin( n//2, L)
print(decToBin(13))
[1, 1, 0, 1]
On peut éviter le reverse() en insérant à chaque étape le nouveau bit en début de liste :
def decToBin(n, L=[]) :
if n==0 : return L
L.insert(0,n%2) # insertion du reste n%2 en position 0
return decToBin( n//2, L)
print(decToBin(13))
Partie entière de log2(x).
Écrire une fonction récursive telle que :
- Entrée : un réel x > 0.
- Sortie : l'entier i tel que 2i≤ x < 2i+1.
def encadrePuiss2(x, e=0, p=1) :
if p>x : return e-1
return encadrePuiss2(x, e+1, 2*p)
n = 17
e = encadrePuiss2(n)
print(" 2^{} <= {} < 2^{}".format(e,n,e+1) )
2^4 <= 17 < 2^5
Dans ce programme, p désigne les puissances successives de 2 et e les exposants successifs (c'est à dire p=2e).