Algo & Prog 1 Python : CM séance 03
3. Exceptions, contrôles et récursivité
3.1. Exceptions
On a vu que l'interpréteur Python détecte toutes sortes d'erreurs :
>>> print(zztop) # NameError: name 'zztop' is not defined
>>> 10/0 # ZeroDivisionError: division by zero
>>> int("toto") # ValueError: invalid literal for int() with base 10: 'toto'
Ces erreurs s'appellent des exceptions et on peut les gérer dans le programme :
try :
bloc1
except nomException:
bloc2
Le bloc 1 est exécuté ; si il y a une erreur nomException, le bloc 1 est interrompu et on saute au bloc 2. Le programme ne s'arrête pas : on dit que l'exception a été captée.
Exemple :
try :
a = int("toto")
print("conversion réalisée")
except ValueError :
print("pas possible")
a = None
On peut aussi récupérer le message d'erreur :
try :
bloc1
except nomException as detail :
bloc2
Exemple :
try :
a = int("toto")
print("conversion réalisée")
except ValueError as detail :
print ("Erreur:", detail)
a = None
Affiche :
Erreur: invalid literal for int() with base 10: 'toto'
On peut aussi capter plusieurs exceptions : donner un tuple
try :
bloc1
except (nomException1, nomException2, ...) as detail :
bloc2
Exemple :
try :
foo = {}
a = foo['bar']
print("foobar")
except (NameError, KeyError, ValueError) as detail :
print ("Erreur:", detail)
On peut mettre plusieurs except pour différentier les exceptions :
try :
bloc1
except nomException1 :
bloc2
except nomException2 :
bloc3
...
except : # on capte toute autre exception
blocn
Il est possible d'émettre une exception avec raise :
try :
a = int(input("Entrez un nombre > 10 : "))
if a <= 10 :
raise ValueError("Entier <= 10")
print ("L'entier est correct")
except ValueError as detail :
print("Erreur :", detail)
>>>
Entrez un nombre > 10 : 20 # L'entier est correct
>>>
Entrez un nombre > 10 : toto # Erreur : invalid literal ... 'toto'
>>>
Entrez un nombre > 10 : 8 # Erreur : Entier <= 10
Lorsqu'une exception est émise (par raise ou une erreur) dans une fonction,
cette fonction est interrompue, de même pour la fonction qui l'appelait,
et ainsi de suite jusqu'à l'appel par le programme principal,
tant que l'exception n'est pas captée par un except.
3.2. Contrôle de boucle
On peut contrôler les boucles while et for avec : break, continue
breaksort immédiatement de la boucle ;continuepasse immédiatement à l'itération suivante.
Exemple : afficher les 5 premiers entiers pairs d'une liste
li = [ 5, 7, 8, 2, 6, 12, 7, 5, 11, 14, 8, 17 ]
n = 0
for e in li :
if e % 2 != 0 :
continue
n += 1
print (e)
if n >= 5 :
break
On peut rajouter un else à la fin d'un while ou d'un for :
le bloc du else sera exécuté si la boucle s'est terminée sans break.
Exemple : recherche du premier élément > k dans une liste
k = 10 # essayer aussi avec 20
li = [ 5, 7, 8, 2, 6, 12, 7, 5, 11, 14, 8, 17 ]
for e in li :
if e > k :
print (e)
break
else :
print ("non trouvé")
Le bloc du else est aussi exécuté s'il n'y a aucune itération (puisqu'il n'y a
pas eu de break) :
while False :
print ("glop glop")
else :
print ("pas glop")
for i in [] :
print ("glop glop")
else :
print ("pas glop")
Sorties par force croissante :
break: sort de la bouclereturn: sort de la fonctionraise: sort de toutes les fonctions jusqu'à untryexceptexit: fin du programme (import sys ; sys.exit())
- Bibliographie : à propos de
breaketreturn - Eric S. Roberts, Loop exits and structured programming: reopening the debate, SIGCSE pp 268-272, 1995. https://dl.acm.org/doi/abs/10.1145/199688.199815
3.3. Récursivité
Une fonction peut s'appeler elle même ; on dit alors qu'elle est récursive. Les appels intermédiaires sont mémorisés dans la pile d'exécution.
Il y a un moment où la fonction doit arrêter de s'appeler, et renvoyer un résultat : c'est le cas terminal.
Voici des exemples.
3.3.1. Factorielle
Définie par : \(1! = 1\) et \(n! = n * (n-1)!\)
def factorielle (n) :
if n <= 1 :
return 1 # cas terminal
return n * factorielle (n-1) # cas général
>>> factorielle(5) # 120
Version avec des traces :
def factorielle (n) :
print ("début factorielle (", n, ")", sep="")
if n <= 1 :
print ("renvoie 1, cas terminal")
return 1 # cas terminal
print ("appel factorielle (", n, "-1)", sep = "")
f = factorielle (n-1)
print ("résultat obtenu :", f)
print ("renvoie n * f =", n,"*",f,"=", n*f)
return n * f
Profondeur de récursion = niveau d'appel maximum.
L'appel initial est à profondeur 1.
Pour factorielle(n), la profondeur est n :
- au niveau 1,
factorielle(n)appellefactorielle(n-1); - au niveau 2,
factorielle(n-1)appellefactorielle(n-2); - ...
- au niveau n-1,
factorielle(2)appellefactorielle(1); - au niveau n,
factorielle(1)est le cas terminal.
En python la profondeur de récursion est limitée :
>>> factorielle(998) # gros chiffre
>>> import math
>>> math.log(factorielle(998),10) # 2561.605078733907
>>> factorielle(999) # RuntimeError: maximum recursion depth exceeded
On peut consulter ou modifier la profondeur limite :
>>> import sys
>>> sys.getrecursionlimit()
1000
>>> sys.setrecursionlimit(2000)
3.3.2. Suite de Fibonacci
Définie par : \(F_n = F_{n-1} + F_{n-2}\) ; \(F_1 = F_2 = 1\)
Les valeurs sont : 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
def fibonacci (n) :
if n <= 2 :
return 1 # cas terminal
return fibonacci (n-1) + fibonacci (n-2)
>>> fibonacci(10) # 55
Efficacité, nombre d'appels ? → rajouter un print
def fibonacci (n) :
print ("fibo", n)
if n <= 2 :
return 1
return fibonacci (n-1) + fibonacci (n-2)
>>> fibonacci(10) # 109 appels !
→ Beaucoup de recalculs !
Meilleure approche : avec variables auxiliaires
def fibonacci (n) :
return fibo_rec (n, 1, 1)
def fibo_rec (n, a, b) :
print ("fibo_rec", n, a, b)
if n <= 2 :
return a
return fibo_rec (n-1, a+b, a)
>>> fibonacci(10)
fibo_rec 10 1 1
fibo_rec 9 2 1
fibo_rec 8 3 2
fibo_rec 7 5 3
fibo_rec 6 8 5
fibo_rec 5 13 8
fibo_rec 4 21 13
fibo_rec 3 34 21
fibo_rec 2 55 34
55
Il s'agit d'une récursion terminale (= appel sans calcul de la fonction récursive).
Cette approche s'inspire de la version itérative :
def fibonacci2(n) :
if n <= 2 :
return 1
a = 1 ; b = 1
for i in range(2,n) :
a,b = a+b,a
return a
Certains langages dits fonctionnels détectent les récursions terminales et les transforment en itérations (en économisant au passage de mémoriser les résultats intermédiaire dans la pile d'exécution).
3.3.3. Arbres binaires
Les arbres binaires sont des structures naturellement récursives.
Un arbre binaire est un arbre avec racine dans lequel tout noeud a au plus deux fils : un éventuel fils gauche et un éventuel fils droit.
Exemple d'arbre binaire et de codage :
# Racine
# / \
# A B
# \ / \
# C D E
# /
# F
nF = { "gauche" : None, "droit" : None, "valeur" : "F" }
nC = { "gauche" : None, "droit" : None, "valeur" : "C" }
nD = { "gauche" : None, "droit" : None, "valeur" : "D" }
nE = { "gauche" : nF , "droit" : None, "valeur" : "E" }
nA = { "gauche" : None, "droit" : nC , "valeur" : "A" }
nB = { "gauche" : nD , "droit" : nE , "valeur" : "B" }
nR = { "gauche" : nA , "droit" : nB , "valeur" : "R" }
>>> nR
Quelle est la profondeur de l'arbre ? (la niveau de la racine étant 1).
→ 1 + max (profondeur(fils gauche), profondeur(fils droit))
def profondeur (noeud) :
if noeud == None :
return 0
return 1 + max (profondeur(noeud["gauche"]),
profondeur(noeud["droit"]))
>>> profondeur(nR) # 4
Ordre de parcours et unicité des appels :
def profondeur (noeud) :
if noeud == None :
return 0
print (noeud["valeur"], end=" ") # trace rajoutée
return 1 + max (profondeur(noeud["gauche"]),
profondeur(noeud["droit"]))
>>> profondeur (nR)
R A C B D E F 4
Cet ordre est celui d'un parcours en profondeur.
On peut aussi réaliser un parcours en largeur, c'est-à-dire niveau par niveau,
avec une approche itérative :
à partir d'une ligne courante de nœuds liste1, on construit la liste2 des fils
de ces nœuds, puis on itère.
def profondeur2 (noeud) : # version avec parcours en largeur
res = 0
if noeud == None :
return res
print (noeud["valeur"], end=" ")
liste1 = [noeud["gauche"], noeud["droit"]]
while len(liste1) > 0 :
res += 1
liste2 = []
for s in liste1 :
if s == None :
continue
print (s["valeur"], end=" ")
liste2 += [s["gauche"], s["droit"]]
liste1 = liste2
return res
>>> profondeur2 (nR)
R A B C D E F 4