PT/PT* - 2023/2024 Informatique - cours

Chapitre 1 : Principes de base en Python, récursivité

1 Les types
1 A) Les expressions
Une expression est une suite de caractères définissant une valeur. Pour connaître cette valeur, la machine
doit évaluer l’expression. Voici quelques exemples :

>>> ’str’
>>> 15 ’str’
15 >>> [2,3/1.5]
>>> 15-11 [2, 2.0]
4 >>> 4<2
>>> 2.4+3 False
5.4 >>> 3,4
(3, 4)

Les valeurs possèdent un type : par exemple entier, flottant, booléen, chaîne de caractères, liste,
fonction. Le type détermine les propriétés formelles de la valeur (par exemple, les opérations qu’elle peut subir)
et matérielles (par exemple, la façon dont elle est représentée en mémoire et la place qu’elle occupe).
Pour connaître le type d’une expression après évaluation, il suffit de le demander à Python à l’aide de la
commande type :

>>> type(15-11)
<class ’int’> >>> type(4<2)
>>> type(2.4+3) <class ’bool’>
<class ’float’> >>> type(3,4)
>>> type(’chaine’) Traceback (most recent call last):
<class ’str’> File "<console>", line 1, in <module>
>>> type([2,3/1.5]) TypeError: type() takes 1 or 3 arguments
<class ’list’>

Comme dans la plupart des langages de programmation, une expression en Python est soit :
— une constante comme 2, 8.5 ou ’chaine’ ;
— un nom de variable comme x, i, ou compteur ;
— le résultat d’une fonction appliquée à une ou plusieurs expressions, comme PGCD(8,5) ;
— la composée de plusieurs expressions réunies à l’aide d’opérateurs, comme not a, 3**6, (6+7)*8. Les
parenthèses servent à préciser quels opérateurs doivent être évalués en premier, comme en mathématiques.
On effectue maintenant quelques rappels sur les types simples de manière plus détaillée.

1 B) Entiers (int)
Les entiers (integers en anglais) sont modélisés par le type int.

1 B) a) Constantes
Les entiers permettent de faire des calculs exacts dans la limite de la représentation du nombre en binaire
dans la mémoire de l’ordinateur.
>>> 5**76
132348898008484427979425390731194056570529937744140625

Lycée Jules Ferry - Versailles 1/19 I1

PT/PT* - 2023/2024 Informatique - cours

1 B) b) Opérateurs
Les opérateurs sur les entiers sont les suivants :

Opérateur + - * // % **
Signification addition soustraction multiplication division entière modulo exponentiation

On notera bien que a//b renvoie le quotient dans la division euclidienne de a par b.

1 B) c) Règles des priorités

Certains opérateurs sont évalués avant les autres, dans l’ordre de priorité suivant :
1. exponentiation ;
2. modulo ;
3. multiplication et division entière ;
4. addition et soustraction.
Sur les opérateurs de même priorité, c’est celui le plus à gauche qui est évalué en premier, sauf pour
l’exponentiation : en cohérence avec les mathématiques, 2**3**2 donne 512 et non 64 qu’on obtiendrait si la
première exponentiation était évaluée en premier. Les parenthèses permettent de changer ces priorités.
>>> 2+25%3*2**4
18
>>> (2+25%(3*2))**4
81

1 C) Flottants (float)
Les réels sont modélisés par le type float (flottant en anglais).

1 C) a) Constantes
Les flottants sont représentés en mémoire sur 32 ou 64 bits suivant le système sous la forme x = ε × m × 2n .
Sur 64 bits, on a 1 bit pour le signe ε = ±1 , 11 bits pour l’exposant n ∈ Z et 52 bits pour la mantisse m un
nombre décimal compris entre 1 inclus et 2 exclu. On tiendra compte du fait que seul un nombre fini de réels
sont représentables en mémoire, ce qui ne permet pas de faire des calculs exacts. En effet, le plus petit nombre
strictement positif représentable exactement en flottant sur 64 bits est 2−1022 et le plus grand est à 21023 .

1 C) b) Opérateurs
Les opérateurs sur les flottants sont les suivants :
Opérateur + - * / **
Signification addition soustraction multiplication division exponentiation

1 C) c) Règles de priorités
Comme sur les entiers, certains opérateurs sont évalués avant les autres, dans l’ordre de priorité suivant :
1. exponentiation ;
2. multiplication et division ;
3. addition et soustraction.
Les opérateurs de même priorité sont évalués de gauche à droite et les parenthèses permettent de changer ces
priorités.

Lycée Jules Ferry - Versailles 2/19 I1

PT/PT* - 2023/2024 Informatique - cours

1 C) d) Conversion automatique
On remarque que la plupart des opérateurs sur les entiers et les flottants sont les mêmes. Lorsqu’on utilise
l’un de ces opérateurs avec des entiers et des flottants, les entiers sont automatiquement convertis en flottants
(on peut forcer la conversion de l’entier n en flottant avec float(n)).
>>> 4*3.1
12.4
>>> 3/4
0.75
>>> 3.0/4
0.75

1 D) Booléens (bool)
1 D) a) Constantes
Les booléens sont essentiels en informatique. Ce type comprend uniquement deux constantes : True (Vrai)
et False (Faux). Ils sont principalement utilisés dans des structures de contrôle.

1 D) b) Opérateurs
Il y a trois opérateurs sur les booléens : not qui correspond à la négation et qui est unitaire (ne prenant
qu’une opérande), and et or qui sont binaires (nécessitant deux opérandes). Voici la table de vérité qui présente
ces différents opérateurs :
a b not a a or b a and b
False False True False False
False True True True False
True False False True False
True True False True True
Pour que a and b soit vrai, il faut que a et b le soient tous les deux. Pour que a or b soit vrai, il suffit que
l’un des deux le soit. Attention, en français, le « ou » peut parfois avoir le sens d’un ou exclusif, comme dans
« fromage ou dessert ». Le or informatique est toujours inclusif : si a et b sont vrais, alors a or b aussi.
Remarque 1.1. Les opérateurs sur les booléens sont analogues aux opérateurs logiques sur les propositions
mathématiques.

1 D) c) Règles de priorité
L’ordre de priorité pour les opérations booléennes est le suivant not ; and ; or. De même que pour les entiers
et les flottants, les opérateurs de même priorité sont évalués de gauche à droite et on peut utiliser des parenthèses.
>>> False and False or True
True
>>> False and (False or True)
False

1 D) d) Opérateurs de comparaison et booléens

On utilise rarement les booléens tels quels. Leur intérêt réside dans les structures de contrôle conditionnelles
abordées plus loin dans ce cours. Celles-ci font beaucoup usage de l’évaluation d’expressions produisant des
booléens, parmi lesquelles on trouve les opérations de comparaisons sur les entiers/flottants.

Opérateur == != < <= > >=

Signification égal non égal inférieur inférieur ou égal supérieur supérieur ou égal

>>> 8<2 or 4*3>=14-2

True

Lycée Jules Ferry - Versailles 3/19 I1

PT/PT* - 2023/2024 Informatique - cours

Pour les évaluations des opérateurs binaires, les deux opérandes des opérateurs de comparaison sont amenés
à un type commun avant l’évaluation de la comparaison (flottant dans le cas d’entier et flottant).
La priorité des opérateurs de comparaison est inférieure à celle des opérateurs arithmétiques : ainsi, l’ex-
pression a==b+c signifie a==(b+c) (on ne peut de toute façon pas additionner un booléen et un flottant).

1 D) e) Caractères paresseux des opérateurs and et or.

On notera quand dans une expression de la forme a and b, où a et b sont des expressions, si a s’évalue en
False, on n’a pas besoin d’évaluer b pour s’apercevoir que a and b s’évalue en False. On peut faire la même
constatation avec a or b si a s’évalue en True.
Python respecte cette logique : si la partie gauche suffit à déterminer si l’expression s’évalue en True ou
False, il n’évalue pas la partie droite (on parle du caractère paresseux des opérateurs).
C’est particulièrement utile lors de l’évaluation d’une expression dont la seconde partie pourrait produire
une erreur, mais dont la première sert de garde-fou : x>0 and log(x)>2 ne produit pas d’erreur, même si x
est un nombre négatif. En effet, dans ce cas, x>0 s’évalue en False et on n’a pas besoin d’évaluer log x>2 qui
produirait une erreur, le log n’étant pas défini sur les nombres négatifs.

2 Les variables
2 A) Identificateurs
Un identificateur est une suite de lettres et de chiffres, qui commence par une lettre et qui n’est pas un mot
réservé du langage Python comme if, else, def, return, True notamment. Le caractère _ (underscore, ou
« tiret du 8 ») est considéré comme une lettre. Ainsi, i, j, x, x2, compteur et taille_de_la_liste sont
des identificateurs corrects, contrairement à 4a, x{}, if ou encore taille de la liste. Les identificateurs
diffèrent selon la casse : x et X sont des identificateurs distincts. On s’attachera à éviter l’usage d’accents dans les
identificateurs : ils sont autorisés mais en utiliser soumettrait la bonne exécution d’un programme à l’encodage
des caractères.

2 B) Variables
Une variable est constituée de l’association d’un identificateur à une valeur. Cette association est créée lors
de l’affectation, qui s’écrit sous la forme variable = expression. Attention à ne pas confondre = (affectation)
avec == (test d’égalité). Le mécanisme de l’affectation est le suivant : l’expression à droite du signe égal est
évaluée, puis le résultat de l’évaluation est affecté à la variable.
Après une telle affectation, chaque apparition de la variable ailleurs que dans la partie gauche d’une autre
affectation représente la valeur en question. Cette association entre la variable et la valeur est valable tant qu’il
n’y a pas de nouvelle affectation avec cette même variable.
Exemple 2.1. Compléter les lignes de codes suivantes pour permuter le contenu de x et y. Que contiennent
finalement x et y ?
>>> x = 2**5
>>> y = float(57//8)

Comme on le voit sur cet exemple, en Python :

— contrairement à plusieurs autres langages de programmation, les variables n’ont pas besoin d’être déclarées
(c’est-à-dire préalablement annoncées). La première affectation leur tient lieu de déclaration ;
— les variables ne sont pas liées à un type (mais les valeurs auxquelles elles sont associées le sont forcément).
La même variable x a été associée à des valeurs de types différents (un int, puis un float).

Lycée Jules Ferry - Versailles 4/19 I1

PT/PT* - 2023/2024 Informatique - cours

Dans la suite, on confondra sans se poser de questions l’identificateur, la variable (l’association de l’identifi-
cateur à une valeur) et la valeur elle-même. Si un identificateur n’a pas été affecté (il n’est donc pas encore un
nom de variable), son emploi ailleurs que dans le membre de gauche d’une affectation est illégale et provoque
une erreur. Par exemple :
>>> print(variable_pas_encore_affectee)
Traceback (most recent call last):

File "<ipython-input-14-9b8b981b03ef>", line 1, in <module>

print(variable_pas_encore_affectee)

NameError: name ’variable_pas_encore_affectee’ is not defined

Seul un identificateur correct peut figurer dans le membre de gauche d’une affectation. Une syntaxe de la
forme x+1=y n’a aucun sens :
>>> y=5
>>> x+1=y
File "<ipython-input-16-ed9cdbcd5701>", line 1
x+1=y
SyntaxError: can’t assign to operator
L’erreur est expliquée par Python : on ne peut pas affecter à l’opérateur +.
Un mécanisme souvent utilisé est informatique est l’incrémentation d’une variable : on lui rajoute un certain
nombre, souvent 1.
>>> x=4
>>> x=x+1
>>> print(x)
5
Il existe un raccourci en Python pour cette opération : x+=1. On peut de même écrire x-=2 ou encore x/=3.
Enfin, lors de l’affectation x=y, la variable x prend la valeur de celle de y, mais x et y ne sont pas « liées »
pour autant :
>>> y=2
>>> x=y
>>> y=5
>>> print(x)
2

3 Structures de contrôle
3 A) Python et l’indentation
Contrairement à la plupart des autres langages de programmation, Python n’utilise pas d’accolades {. . .} ou
de mots clefs de la forme begin ou end pour délimiter des blocs d’instructions. Tout est basé sur l’indentation :
le fait de laisser une marge blanche devant un bloc d’instructions. Cela allège le code mais il faut faire attention
à respecter des règles strictes :
— une séquence d’instructions est faite d’instructions écrites avec la même indentation ;
— dans une structure de contrôle (instruction conditionnelle if ou boucles for et while) ou dans la définition
d’une fonction, une séquence d’instructions subordonnées doit avoir une indentation supérieure à celle de
la séquence englobante.
— toute ligne écrite avec la même indentation que cette séance englobante marque la fin de la séquence
subordonnée ;
— l’indentation standard est de quatre espaces, ou une tabulation. Les éditeurs convenables, tels que IDLE
ou Pyzo que l’on utilisera, remplacent automatiquement une tabulation par quatre espaces.
L’utilisation de copier/coller, à cause de cette sensibilité extrême de Python à l’indentation, peut s’avérer
hasardeux.

Lycée Jules Ferry - Versailles 5/19 I1

PT/PT* - 2023/2024 Informatique - cours

Remarque 3.1. Pour éviter de revenir systématiquement à la ligne entre deux instructions, on peut séparer
les instructions par des points virgules, par exemple x=2 ; y=4, qui réalise successivement l’affectation de x
puis celle de y.

3 B) Instruction conditionnelle if/else (si/sinon)

La structure générale d’une instruction conditionnelle est la suivante (n’oubliez pas l’importance de l’inden-
tation) :
if expression:
[instructions effectuées si expression s’évalue en True]
elif expr:
[instructions effectuées si expression s’évalue en False et expr s’évalue en True]
else:
[instructions effectuées si expression et autre_expression s’évaluent en False]
Les expressions utilisées sont des expressions booléennes, leur évaluation doit produire un booléen : True ou
False.
De telles expressions sont par exemple x>=28, ou bien not c==0 and d<-8.
Dans une telle structure conditionnelle, les expressions booléennes sont évaluées les unes après les autres,
de haut en bas, jusqu’à ce que l’une d’entre elles s’évalue en True. Le bloc d’instructions correspondant (et
uniquement celui-ci) est alors exécuté, puis on sort de la structure conditionnelle. Le bloc correspondant au
else est exécuté seulement si toutes les expressions conditionnelles situées au dessus sont évaluées en False. Il
est possible de mettre plusieurs elif.
Voici un exemple où la variable note est supposée contenir un flottant entre 0 et 20.
if note>=16:
print("Mention Trés bien")
elif note>=14:
print("Mention Bien")
elif note>=12:
print("Mention Assez bien")
elif note>=10:
print("Sans Mention")
else:
print("Raté")
Si note contient un flottant supérieur à 16, on n’affichera à l’écran (effet de la fonction print) qu’une seule
ligne : "Mention très bien", même si la condition note>= 14 est également réalisée.
Les blocs elif et else peuvent tous les deux être omis. Dans une suite d’instructions, au plus une (et
exactement une si else est présent) est exécutée : la première telle que l’expression booléenne associée s’évalue
en True. Par exemple, dans la séquence suivante, x est incrémenté de 1 s’il est supérieur ou égal à 2, et divisé
par 2 s’il est strictement inférieur à 0.
if x<0:
x=x/2
elif x>=2:
x+=1
Si x appartient à l’intervalle [0, 2], il est inchangé. Il est inutile d’écrire quelque chose comme x=x dans un
bloc else.
Exemple 3.2. Écrire un programme qui résout, dans R, l’équation polynomiale de degré 2 : ax2 + bx + c = 0,
en supposant que les variables a, b et c contiennent des flottants, avec a non nul. On aura vraisemblablement
besoin de la fonction sqrt (racine carrée) du module math.

Lycée Jules Ferry - Versailles 6/19 I1

PT/PT* - 2023/2024 Informatique - cours

3 C) Boucle conditionnelle while (tant que)

La boucle while permet de réaliser une suite d’instructions tant qu’une certaine condition est vraie. La
structure est la suivante :
while expression:
[instructions]
On évalue expression. Si le résultat est True, on effectue toutes les instructions du bloc indenté, puis on
recommence l’évaluation de expression. Sinon, on passe aux instructions situées après la boucle.
Par exemple, la séquence :
k=0
while k<10:
print(k)
k+=1
print("fini")
affiche à l’écran tous les entiers entre 0 et 9 puis « fini ». En effet, lorsque k atteint 9, on affiche à l’écran k puis
on l’incrémente. On réévalue ensuite la condition, mais 10<10 s’évalue en False, donc on sort de la boucle et
on affiche « fini » qui est une expression en dehors du corps de la boucle.
Il est possible qu’à la première évaluation de l’expression, celle-ci soit False. Dans ce cas on n’effectue jamais
le corps de la boucle :
u=-20
while u>=20
print("Cette phrase ne sera pas affichée")
Attention, si l’expression de la boucle while s’évalue toujours en True, on crée un morceau de code qui
boucle sans fin :
while True :
print("Ceci s’affichera éternellement")

3 D) Boucle inconditionnelle for (pour)

La structure d’une boucle for est la suivante :
for elements in iterable :
[instructions]
Le terme iterable désigne quelque chose que l’on peut itérer : cela fournit une séquence de valeurs. La
syntaxe for elements in iterable signifie que la variable element doit prendre successivement toutes les
valeurs que fournit l’itérable. Pour chacune des ces valeurs, on exécute les instructions du corps de la boucle.
On utilisera souvent le constructeur range qui fournit des suites (finies) d’entiers. La syntaxe est la suivante
(avec m, n et p des entiers) :
— pour n ≥ 0, range(n) fournit tous les entiers de 0 inclus à n exclu ;
— pour m ≤ n, range(m,n) fournit tous les entiers de m inclus à n exclu.
A l’aide d’un troisième paramètre, on peut faire varier le pas :
— si p > 0, range(m,n,p) fournit successivement les entiers m, m + p, m + 2p, . . . strictement inférieurs à n ;
— si p < 0, range(m,n,p) fournit successivement les entiers m, m + p, m + 2p, . . . strictement supérieurs à n.
Par exemple, la boucle
for i in range(0,m,2):
print(i)
affiche à l’écran successivement tous les entiers pairs entre 0 et m − 1 (en excluant la borne m). La boucle
suivante affiche tous les entiers de n − 1 à 0 (dans l’ordre décroissant) :
for i in range(n-1,-1,-1):
print(i)

Lycée Jules Ferry - Versailles 7/19 I1

PT/PT* - 2023/2024 Informatique - cours

Exemple 3.3. Écrire des lignes de codes renvoyant 10! en utilisant une boucle conditionnelle puis en utilisant
une boucle inconditionnelle.

3 E) Assertion
L’instruction assert de Python est une aide au débogage qui teste une condition. Si la condition est vraie,
votre programme continue à s’exécuter. Mais si la condition d’assertion est fausse, elle lève une exception
AssertionError avec un message d’erreur. L’utilisation appropriée des assertions est d’informer l’auteur du code
d’erreurs irrécupérables dans un programme. Par exemple,
def conversion_masse_poids(M):
assert M>0
g = 9.81
return(M*g)
renverra une erreur lorsque M est négatif ou nul.

4 Fonctions
On appelle fonction tout programme qui, à partir d’un ou plusieurs paramètre(s) appelés entrée(s), calcule
une valeur dépendant de ces paramètres appelée sortie.

4 A) Notions et syntaxe de base

Deux points de vue, souvent complémentaires, permettent de préciser ce qu’est une fonction.
— c’est une séquence d’instructions qui permet de réaliser un calcul précis, que l’ont peut utiliser plusieurs
fois ;
— c’est une brique de base d’un problème plus complexe.
La structure générale d’une déclaration de fonction en Python se fait avec le mot-clef def de la façon
suivante :
def nom_fonction(a_1,a_2,..,a_k):
""" Description de l’action de la fonction """
instruction 1
instruction 2
...
instruction p
#hors de la définition de la fonction

— La première ligne def nom_fonction(a_1,a_2,...,a_k) est l’en-tête de la fonction (ceci permet de

définir le nom de la fonction). Les éléments a_1,a_2,...,a_k sont des identificateurs appelés arguments
formels de la fonction et nom_fonction est le nom de la fonction. Pour une fonction ne prenant pas
d’arguments, on écrit simplement def fonction():, les parenthèses étant indispensables. Le nom de la
fonction est un identificateur qui suit les mêmes règles que les identificateurs de variables.
— La deuxième ligne (qui est facultative et peut être sur plusieurs lignes) est une chaîne de caractères appelée
chaîne de documentation décrivant la fonction : ce que doivent respecter les paramètres passés en entrée,
l’action effectuée et la nature du résultat retournée.
— La suite d’instructions est le corps de la fonction.
— Le retour à une indentation au même niveau que def marque la fin de la fonction, tout ce qui est à ce
niveau ne fait plus partie de la fonction.

Lycée Jules Ferry - Versailles 8/19 I1

PT/PT* - 2023/2024 Informatique - cours

Le rôle d’une définition de fonction n’est pas d’exécuter les instructions qui en composent le corps, mais
uniquement de mémoriser ces instructions en vue d’une exécution ultérieure (facultative), provoquée par une
expression faisant appel à la fonction.

4 A) a) Appel d’une fonction

L’appel de la fonction nom_fonction présentée ci-dessus se fait par : nom_fonction(e_1,...e_k) où
e_1,...e_k sont des expressions. Elles forment les arguments effectifs de l’appel à la fonction : lors de l’appel
e_1 (respectivement e_2,...,e_k) est évaluée, puis le résultat est affecté à a_1 (respectivement a_2,...a_k)
juste avant l’exécution du corps de la fonction. Tout se passe comme si l’exécution de la fonction commençait
par la suite d’instructions d’affectation
a_1=e_1
a_2=e_2
...
a_k=e_k
et se poursuivait avec
instruction 1
instruction 2
...
instruction p

4 A) b) L’instruction return
Le corps de la fonction comprend bien souvent une ou plusieurs instructions de la forme return resultat,
où resultat est une expression. Lors du déroulement du corps de la fonction, si une telle instruction est
rencontrée, alors l’expression resultat est évaluée, l’exécution de la fonction est interrompue et la valeur de
resultat prend la place de nom_fonction(e_1,e_2,...,e_k) là où la fonction a été appelée.
Considérons un exemple :
def incremente(x)
return(x+1)
Si on exécute a=incremente(6-2)+9, alors :
— 6-2 s’évalue en 4.
— x prend la valeur 4 dans la fonction.
— x+1 s’évalue en 5, qui est retourné par la fonction.
— incremente(6-2) est donc remplacé par 5.
— incremente(6-2)+9 s’évalue donc en 14, qui est ensuite affecté à la variable a.

4 A) c) Le type « rien »
Si la fonction ne comprend pas de return ou qu’aucun return n’est rencontré lors de l’exécution, la fonc-
tion ne renvoie rien. On dit parfois qu’elle fonctionne uniquement par effets de bord et c’est là une différence
fondamentale avec les mathématiques. Il y a un type pour ça, NoneType, qui comporte une unique valeur, None.
La fonction suivante ne prend aucun paramètre en entrée, se contente d’afficher 4 à l’écran, et ne renvoie rien :
elle agit par effet de bord.
def affiche4():
print(4)
Lors de l’évaluation de a=affiche4(), 4 est affiché à l’écran, on sort de la fonction (car on est arrivé en bas)
et a prend la valeur None. Notez que return seul (sans rien derrière) est souvent fort utile pour interrompre
une fonction. La fonction en question renvoie alors None.

Lycée Jules Ferry - Versailles 9/19 I1

PT/PT* - 2023/2024 Informatique - cours

4 A) d) Différence entre print et return

Une erreur classique est de confondre print et return. L’instruction return est permet la sortie de fonction
tandis que print est une fonction Python, qui affiche l’argument passé en entrée à l’écran et qui ne renvoie
rien. Lorsqu’on teste une fonction dans la console, on ne voit vraiment pas la différence mais elle est pourtant
significative : une fonction sans return ne renvoie rien.
Prenons l’exemple de la fonction suivante, qui calcule un PGCD.
def PGCD(a,b):
"""Avec a et b>0, renvoie le PGCD de a et b."""
while b!=0
a,b=b,a%b
return a
Exécuté dans la console, on ne verrait pas de grande différence entre cette fonction et la même avec print
à la place de return. Si maintenant, on veut utiliser cette fonction pour calculer un PPCM, on définit alors la
fonction suivante :
def PPCM(a,b):
"""Avec b>0, renvoie le PPCM de a et b."""
return a*b//PGCD(a,b)
L’appel PPCM(6,4) produit bien 12. Avec print a au lieu de return a dans la fonction PGCD, l’expression
PGCD(6,4) est remplacée par None, et l’évaluation a*b//PGCD(a,b) produit une erreur.

4 A) e) Chaîne de documentation
La chaîne de documentation, ainsi que l’en-tête, sont accessibles lorsqu’on tape help(nom_fonction) :
>>>help(PPCM)
Help on function PPCM in module __main__:

PPCM(a,b)
Avec b>0, renvoie le PPCM de a et b.
Cela fonctionne également avec les fonctions Python.

4 B) Variables locales et globales

Dans les fonctions PGCD et PPCM de la section précédente, les variables a et b ont été utilisées à peu près
partout, comme paramètres d’appel des deux fonctions mais également comme variables pour calculer le PGCD
puisque par exemple la valeur de retour de PGCD est a. Pourtant, Python produit le résultat auquel on s’attend,
parce que a et b dans les fonctions sont des variables locales.
Si elle n’est pas explicitement déclarée globale, toute variable apparaissant dans une fonction comme membre
gauche d’une affectation est locale à cette fonction. Cela signifie que sa portée est réduite à la fonction, qu’elle
est créée à chaque fois que la fonction est appelée et « détruite » à la fin de chaque exécution. Par exemple,
supposons que la variable a n’ait pas été affectée mais la fonction PGCD précédente déclarée :
>>> PGCD(8,3);
1
>>> a
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
NameError: name ’a’ is not defined
On voit bien que a est inconnu en dehors de la fonction PGCD. Les paramètres des fonctions se comportent
comme des variables locales, on peut les modifier mais cette modification est interne à la fonction :
>>> a=5 ; b=7
>>> p=PGCD(a,b)
>>> print(a)
5

Lycée Jules Ferry - Versailles 10/19 I1

PT/PT* - 2023/2024 Informatique - cours

On parle de passage par valeurs : lors de l’appel à PGCD, les valeurs de a et b sont recopiées et les variables
a et b de la fonction ne sont pas les mêmes que les variables a et b qu’on a définies en dehors de la fonction.
A l’inverse, les variables globales sont des variables créées à l’extérieur de toute fonction. Elles existent depuis
le moment de leur création, jusqu’à la fin de l’exécution du programme. Une variable globale peut être utilisée à
l’intérieur d’une fonction si elle n’est pas le membre de gauche d’une affectation ou le nom d’un paramètre. Par
exemple, la fonction suivante ajoute le contenu de la variable (globale) n au paramètre x et renvoie le résultat
de l’addition.
def ajoute_n(x):
return x+n

Si n n’est pas défini au moment de l’appel à ajoute_n, on obtient une erreur.

Pour pouvoir affecter à une variable globale dans une fonction, cette variable doit faire l’objet d’une décla-
ration explicite comme variable globale de la forme global variable_globale :
n=0
def ajoute(x):
n+=x
Ici l’appel à la fonction ajoute renvoie une erreur car n n’est pas déclaré comme une variable globale :
>>> ajoute(1)
Traceback (most recent call last):
File "<console>", line 1, in <module>
File "<tmp 1>", line 3, in ajoute
n+=x
UnboundLocalError: local variable ’n’ referenced before assignment
Au contraire, si l’on corrige le programme :
n=0
def ajoute(x):
global n
n+=x
Le programme fonctionne et modifie correctement la variable globale n :
>>> ajoute(1)

>>> n
1

p
X 1 1 1 1 1
Exercice 4.1. Dans cet exercice, on cherche à calculer up = = + + + ··· + où, pour tout
n=0
n! 0! 1! 2! p!
0! = 1 et, pour tout n ∈ N∗ , n! = 1 × 2 × · · · × n.
1. Écrire la fonction factorielle, c’est-à-dire la fonction qui prend en entrée un entier n puis renvoie le produit des
entiers inférieurs à n, soit n × (n − 1) × · · · 2 × 1. On prendra encore la convention suivante : factorielle(0) = 1.
2. Donner un programme Somme convenant, en réutilisant la fonction implémentée dans la question précédente.
3. Lors de l’appel de Somme(p), pouvez-vous compter combien d’opérations arithmétiques effectue la machine ?
Pouvez-vous trouver un programme qui effectue le calcul de up en effectuant moins d’opérations ?

Lycée Jules Ferry - Versailles 11/19 I1

PT/PT* - 2023/2024 Informatique - cours

5 Récursivité
5 A) Définition et premiers exemples
Définition 5.1. Un algorithme récursif est un algorithme qui résout un problème en calculant des solutions
d’instances plus petites du même problème.
Remarque 5.2. Une fonction écrite récursivement « s’appelle elle-même ».
En Python, la structure générale est donc la suivante :
def fonction_recursive(parametres):
if ... : #critere d’arret
return ...
else :
return ... #instructions contenant un appel á la fonction récursive

Définition 5.3. Les fonctions non récursives seront appelées fonctions itératives : on parle d’approche impé-
rative.
Un exemple classique est celui de la fonction factorielle. On peut implémenter cette fonction de manière
itérative, en utilisant une boucle for :
def factorielle(n):
x=1
for k in range(1,n+1):
x=x*k
return x
En utilisant la relation de récurrence n! = n × (n − 1)!, on peut aussi utiliser une programmation récursive :
def Factorielle(n):
if n ==0 or n ==1:
return 1
else:
return n*Factorielle(n-1)

Lycée Jules Ferry - Versailles 12/19 I1

PT/PT* - 2023/2024 Informatique - cours

L’exemple précédent illustre les trois grands principes que doivent vérifier une fonction récursive :
— une fonction récursive doit comporter un critère d’arrêt qui consiste en la donnée d’un ou plusieurs cas de
base ;
— une fonction récursive doit appeler le critère d’arrêt au bout d’un nombre fini d’étapes (ce qui assure la
terminaison de l’algorithme) ;
— une fonction récursive s’appelle elle-même, mais avec différentes valeurs de (ou des) l’argument(s).
Les appels successifs d’une fonction récursive sont stockés dans une pile : c’est la phase de descente. Une
fois que la close d’arrêt est demandée, les appels sont ensuite dépilés jusqu’à arriver à l’appel initial : c’est la
phase de remontée. Voici la pile d’appel dans l’exemple du calcul de 6! :

Descente Remontée

n = 6 n * 120 = 720

n = 5 n * 24 = 120

n = 4 n * 6 = 24

n = 3 n * 2 = 6

n = 2 n * 2 = 2

n = 1 n = 1

Condition de sortie n == 1

Remarque 5.4. Par défaut, Python limite à 1000 le nombre d’appels récursifs. Tout dépassement provoquera
une erreur RuntimeError: maximum recursion depth exceeded. On peut augmenter la taille de la pile en
utilisant le module sys. Par exemple, pour une pile de taille 2000 :
import sys
sys.setrecursionlimit(2000)

On peut également définir des fonctions mutuellement récursives en prenant soin de les placer l’une après
l’autre dans le script. Dans l’exemple suivant, on placera donc pair avant impair dans le script.

Exemple 5.5.
def pair(n): def impair(n):
if n ==0: if n ==0:
return True return False
else: else:
return impair(n-1) return pair(n-1)

5 B) Exponentiation rapide
Dans cette partie, on s’interdit d’utiliser ** pour calculer une puissance afin de comparer des stratégies pour
pouvoir calculer xn où x est un flottant et n un entier. Pour calculer xn , on peut naïvement écrire que

xn = x × x × · · · × x.

Dans ce cas, la fonction naïve s’écrit sous la forme

def expo_naive(x,n):
u=1
for k in range(0,n):
u*=x
return(u)

Lycée Jules Ferry - Versailles 13/19 I1

PT/PT* - 2023/2024 Informatique - cours

Ainsi, la méthode précédente demande huit multiplications pour calculer 29 . On peut également écrire :

2
29 = 2 × (22 )2

ce qui ne nécessite, en comptant chaque carré comme une seule multiplication, que quatre multiplications. De
façon générale, on peut s’appuyer sur les considérations suivantes :
(
k
x2k = x2

k
x2k+1 = x × x2

Exemple 5.6. Écrivons une fonction expo_rapide(x,n), écrite récursivement qui est plus efficace que la
méthode naïve :

Avec le package time, l’exécution des lignes

import time
x=2
n=1000000
T1=time.time()
expo_naive(x,n)
T2=time.time()
t_naif=T2-T1
T1=time.time()
expo_rapide(x,n)
T2=time.time()
t_rapide=T2-T1
print(’temps avec la methode naive : ’+str(t_naif))
print(’temps avec la methode rapide : ’+str(t_rapide))
donne
temps avec la methode naive : 11.840978860855103
temps avec la methode rapide : 6.67572021484375e-06
On constate que l’exponentiation rapide est plus rapide que la méthode naïve.
Remarque 5.7. Il est aussi possible d’écrire une version itérative de la méthode précédente :
def expo_rapide2(x,n):
P=1
u=x
m=n
while m>0:
if m%2==1:
P=P*u
u=u*u
m=m//2
return(P)

Lycée Jules Ferry - Versailles 14/19 I1

PT/PT* - 2023/2024 Informatique - cours

Exercice 5.8. Une conjecture classique est que la suite, définie de la manière suivante :
(
un
u0 = N et ∀n ∈ N, un+1 = 3u 2 si un est pair
n +1
2 sinon

atteint toujours 1 en un nombre fini d’étapes (qu’on appelle temps de vol) pour tout entier N ∈ N∗ fixé.
Néanmoins cette conjecture n’est toujours pas démontrée à ce jour. Cette suite est généralement appelée suite
de Syracuse (compressée).
Écrire, de façon itérative, une fonction Syracuse(N), avec une boucle while, qui prend comme argument un
entier N et qui renvoie le plus petit entier n tel que un vaut 1. Refaire ensuite cet exercice sous forme récursive.

5 C) Complexité
Pour traiter un même problème, il existe souvent plusieurs algorithmes. Quand on doit choisir, l’un des critères
est celui du temps d’exécution, qu’on appelle aussi parfois coût de l’algorithme. En effet, le temps d’exécution
conditionne les ressources utilisées (machine sur laquelle on exécutera l’algorithme, consommation électrique...).
Pour un logiciel interactif, par exemple, un temps de réponse court est un élément essentiel du confort de
l’utilisateur. De même, certains programmes industriels doivent être utilisés un grand nombre de fois dans un
délai très court et même un programme qui n’est exécuté qu’une seule fois, par exemple un programme de
simulation écrit pour tester une hypothèse de recherche, est inutilisable s’il demande des mois ou des années de
calcul.
Il existe plusieurs manières de définir la complexité temporelle et celle-ci est liée à la classe d’algorithmes
qu’on analyse.
Chacune des opérations élémentaires suivantes a une certaine durée de traitement :
— l’affectation ;
— les comparaisons ;
— les opérations sur des données numériques ;

Définition 5.9. On appelle modèle à coût constant le fait de supposer que chaque opération élémentaire a une
durée de coût 1.
Dans ce chapitre, on se place dans le cadre d’un modèle à coût constant et on adopte donc la définition
suivante :

Définition 5.10. La complexité d’un algorithme en temps est la somme de tous les temps d’exécution des
différentes opérations effectuées lors de l’exécution.
En général, on cherche à déterminer comment le temps d’exécution d’un algorithme varie en fonction d’un
paramètre qu’on appelle la taille du problème. Le paramètre à considérer dépend du problème considéré. Dans
l’exemple précédent, le temps de recherche des diviseurs d’un entier n dépend de n ; on prendra donc naturelle-
ment cet entier n comme taille du problème. Voici un tableau montrant différents choix possibles de paramètre,
suivant le type d’entrée considéré.

Lycée Jules Ferry - Versailles 15/19 I1

PT/PT* - 2023/2024 Informatique - cours

Type de l’entrée Paramètre

Entier Cet entier
Liste Nombre d’éléments de la liste
Tableau Nombre d’éléments du tableau
Matrice Nombre d’éléments de la matrice
ou dimension de la matrice
Chaîne de caractères Nombre de caractères
Fichier texte Nombre de caractères ou
nombre de lignes...
Autre Espace mémoire de la donnée

Lorsqu’aucun autre paramètre pertinent n’est disponible, on peut toujours considérer la taille de la représenta-
tion des données passées en entrée comme paramètre.
L’évaluation précise de la complexité d’un algorithme peut s’avérer délicate. Un ordre de grandeur en fonction
des paramètres d’entrée est suffisante pour comparer des algorithmes. On s’appuie sur des notions mathématiques
qu’on rappelle ici.

Définition 5.11.
Soit (un ), (vn ) deux suites réelles non nulles à partir d’un certain rang. On note
1. un = O(vn ) lorsque
∃M > 0, ∃N ∈ N, ∀n > N, |un | 6 M |vn | .
2. un = Θ(vn ) lorsque
∃m, M > 0, ∃N ∈ N, ∀n > N, mvn 6 un 6 M vn .

Considérons un algorithme dépendant d’un paramètre n et notons C(n) le nombre d’opérations effectuées.
On appelle C une fonction de complexité. Vu que seul le terme dominant dans le temps d’exécution est
important pour avoir une idée de l’efficacité de l’algorithme, il est inutile de faire un inventaire précis du nombre
d’opérations effectuées par l’algorithme. On sera ainsi parfois amené à ne compter qu’un type d’opération : celles
qui sont les plus coûteuses. Par exemple, si un algorithme consiste à effectuer essentiellement des multiplications
et des additions, on pourra ne compter que les multiplications, puisqu’on peut imaginer qu’une multiplication
est beaucoup plus coûteuse qu’une addition. On utilisera O () lorsque qu’on voudra seulement une majoration
et Θ pour une évaluation plus précise.
La complexité est donc une mesure d’efficacité d’un algorithme, du coût de l’algorithme en termes de
ressources de l’ordinateur, et on cherchera seulement à avoir une estimation de la fonction de complexité de la
forme suivante qui utilise la notation Θ :

Relation Nom Temps pour n = 106

C(n) = Θ(1) Coût constant 1 ns
C(n) = Θ(ln n) Coût logarithmique 10 ns
C(n) = Θ(n) Coût linéaire 10 ms
C(n) = Θ(n2 ) Coût quadratique 15 mn
C(n) = Θ(nk ), k > 0 Coût polynomial 30 ans pour k = 3
C(n) = Θ(xn ), x > 1 Coût exponentiel plus que l’âge de l’univers

Exercice 5.12. On donne la fonction :

def expo_rapide(x,n):
if n==0:
return 1
elif n%2==0:
return(expo_rapide(x*x,n//2))
else:
return(x*expo_rapide(x*x,(n-1)//2))
Déterminer les complexités spatiale et temporelle de la fonction précédente.

Lycée Jules Ferry - Versailles 16/19 I1

PT/PT* - 2023/2024 Informatique - cours

Stocker systématiquement l’état d’une fonction avant chaque appel récursif dans la pile d’appels n’est pas
gratuit, en temps comme en mémoire.

5 D) Un exemple d’utilisation de la récursivité : les tours de Hanoï

Il n’existe pas de réponse définitive à la question de savoir si un algorithme récursif est préférable à un
algorithme itératif ou le contraire. On peut prouver que ces deux paradigmes de programmation sont équiva-
lents ; autrement dit, tout algorithme itératif possède une version récursive, et réciproquement. Un algorithme
récursif est aussi performant qu’un algorithme itératif lorsque le compilateur ou l’interprète de commande gère
convenablement la récursivité.
On considère des cylindres plats troués placés sur un axe comme sur la figure suivante :

L’idée est de déplacer tous les disques de la première tour sur la troisième tour en respectant les règles suivantes :
— Un seul disque peut être déplacé à la fois,
— Un disque peut uniquement être posé sur un disque de rayon supérieur ou sur un emplacement vide.
Maintenant, raisonnons par récurrence : pour pouvoir déplacer le dernier disque, il est nécessaire de déplacer
les n − 1 disques qui le couvrent sur la tige centrale. Une fois ces déplacements effectués, nous pouvons déplacer
le dernier disque sur la troisième tige. Il reste alors à déplacer les n − 1 autres disques vers la troisième tige.

On peut maintenant en conclure que pour pouvoir déplacer n disques de la tige 1 vers la tige 3 il suffit de
savoir déplacer n − 1 disques de la tige 1 vers la tige 2 puis de la tige 2 vers la tige 3. Autrement dit, il suffit de
généraliser le problème de manière à décrire le déplacement de n disques de la tige i à la tige k en utilisant la
tige j comme pivot. Cela mène à la procédure suivante :
def hanoi(n,i,j,k):
if n==0:
return None
hanoi(n-1,i,k,j)
print(’Deplacer le disque ’+str(n)+’ de la tige ’+str(i)+’ vers la tige ’+str(k))
hanoi(n-1,j,i,k)
En exécutant hanoi(4, 1, 2, 3) on obtient
Deplacer le disque 1 de la tige 1 vers la tige 2
Deplacer le disque 2 de la tige 1 vers la tige 3
Deplacer le disque 1 de la tige 2 vers la tige 3
Deplacer le disque 3 de la tige 1 vers la tige 2
Deplacer le disque 1 de la tige 3 vers la tige 1
Deplacer le disque 2 de la tige 3 vers la tige 2
Deplacer le disque 1 de la tige 1 vers la tige 2
Deplacer le disque 4 de la tige 1 vers la tige 3
Deplacer le disque 1 de la tige 2 vers la tige 3
Deplacer le disque 2 de la tige 2 vers la tige 1
Deplacer le disque 1 de la tige 3 vers la tige 1
Deplacer le disque 3 de la tige 2 vers la tige 3
Deplacer le disque 1 de la tige 1 vers la tige 2
Deplacer le disque 2 de la tige 1 vers la tige 3
Deplacer le disque 1 de la tige 2 vers la tige 3

Lycée Jules Ferry - Versailles 17/19 I1

PT/PT* - 2023/2024 Informatique - cours

Si une solution itérative est très compliquée à trouver, la solution récursive s’écrit de manière très simple.
D’une manière générale, il est souvent difficile de trouver une version itérative des algorithmes récursifs où
plusieurs appels récursifs sont nécessaires.

6 Exercices
Exercice 6.1 (Nombre d’occurences). Le nombre d’occurences d’un élément a d’une liste L est le nombre de
fois que cet élément a apparaît dans la liste.
1. Écrire une fonction occurence(a,L) prenant en argument un élément a et une liste L donnant le nombre
d’occurences dd l’élément a dans la liste L.
2. Écrire à nouveau la fonction précédente sous forme récursive. On réfléchira au cas critère d’arrêt et on pourra
utiliser le fait que pour une liste L, L[1:] est la liste L où le premier élément a été supprimé.
Exercice 6.2 (Manipulation de fichiers). Le but de l’exercice est d’analyser un tableau donnant les températures
en Île-de-France depuis 2016. Pour cela, on fournit, sur le site, le fichier temperatures_IDF.csv qui est extrait
des données publiques du site : https://www.data.gouv.fr.
Ce fichier texte représente un tableau comportant quatre colonnes (et plus de 2000 lignes) qui sont séparées
par des virgules. On a, dans l’ordre, une colonne avec la date (au format aaaa-mm-jj puis les températures
minimale, maximale et moyenne sur la journée).
On va ouvrir puis utiliser les données du fichier pour obtenir un graphique.
On ne modifiera pas le fichier texte (c’est-à-dire le tableau) dans cet exercice.
1. Téléchargez le fichier des températures puis placez-vous dans le dossier qui contient ce téléchargement avec
le module os. Exécutez ensuite les lignes suivantes :
fichier = open("temperatures_IDF.csv", ’r’)
lignes = fichier.readlines()
for ligne in lignes:
print(ligne)

2. Écrire une fonction temperature(jour) où jour est une chaîne de caractère de la forme aaaa-mm-jj qui
renvoie la température moyenne du jour. On pourra utiliser split ainsi que la fonction int qui convertit un
entier en chaîne de caractère.
3. Écrire une fonction moyenne(annee) où annee est une chaîne de caractères de la forme aaaa et qui renvoie
la température moyenne du sur l’année. On pourra utiliser split.
4. Tracer un graphique avec en abscisse l’année et en ordonnée la température moyenne annuelle. On obtiendra
le graphe suivant :

5. Avec un jeu de couleur, ajouter sur le graphique précédent les températures minimale et maximale.

Lycée Jules Ferry - Versailles 18/19 I1