Enchaînements d'instructions ============================ Dans ce chapitre, nous abordons l'écriture d'un algorithme à proprement parler. Après avoir présenté sa structure générale, nous présenterons les différents enchaînements d'instructions qui permettent de le définir. .. index:: ! fonction single: def single: return Fonction ++++++++ En Python, le code décrivant un algorithme s'appelle une **fonction**. La structure générale d'une fonction est décrite ci-dessous. Notons que toutes les lignes à l'exception de la première doivent commencer par quatre espaces [#espaces]_. * première ligne : - le mot-clé ``def``, - le nom de la fonction, - la liste, entre parenthèses, des noms des paramètres d'entrée, séparés par des virgules, - le caractère *deux points* (``:``). * rappel de la spécification du problème : - précédée et suivie par des triples guillemets(``"""``). * enchaînement d'instructions décrivant l'algorithme à proprement parler : - décrit plus en détail dans la suite de ce chapitre. * dernière ligne : - le mot-clé ``return`` [#retourner]_, - la liste des noms des paramètres de sortie, séparés par des virgules. Par exemple, la fonction encadrant la racine carrée d'un nombre réel `x` aura la structure suivante :: def encadre_racine_carrée(n): """ :entrée x: réel :pré-cond: x ≥ 0 :sortie inf: entier :sortie sup: entier :post-cond: inf ≤ √x < sup :post-cond: |sup - inf| ≤ 1 """ # (...) enchaînement d'instructions return inf, sup La fonction calculant le nombre de bonbons restant à Alice aura la structure suivante :: def bonbons_restants(n, p): """ :entrée n: entier :entrée p: entier :pré-cond: 0 ≤ p ≤ n :sortie r: entier :post-cond: r + p = n """ # (...) enchaînement d'instructions return r Rappelons que le rappel de la spécification ne joue aucun rôle pour l'ordinateur. Il n'est là que pour *documenter* la fonction, en rappelant au programmeur le problème qu'elle doit résoudre. Pour cette raison, il est donc recommandé de ne pas négliger cet aspect, même s'il n'a pas d'incidence directe sur l'exécution de la fonction par l'ordinateur. .. _def-procédure: .. index:: ! procédure single: paramètre d'entrée-sortie single: print Procédure --------- Une **procédure** est une fonction qui n'a pas d'instruction ``return``, où dont l'instruction ``return`` n'est suivie d'aucune variable. Cela peut sembler contradictoire avec la manière dont nous avons défini la spécification d'un problème et l'écriture d'une fonction, et mérite donc une explication. La première utilisation des procédures concerne les problèmes dont la « solution » est en dehors de la mémoire de l'ordinateur. Un exemple typique est d'afficher un texte à l'écran. Le problème est décrit par un paramètre d'entrée (une chaîne de caractères). En revanche la solution ne peut pas être décrite par une valeur (ou un ensemble de valeurs), mais par un *effet* sur le monde extérieur. Notons que, pour cet exemple précis, Python fournit la procédure ``print``. La deuxième utilisation des procédures concerne les fonction n'ayant aucun paramètre de sortie strict, mais des `paramètres d'entrée-sortie `:ref: (cette notion sera vue au chapitre `tableaux`:doc:). .. index:: variable intermédiaire single: paramètre d'entrée single: paramètre de sortie .. todo: cette différenciation de procédure/fonction de procédure est discutable; elle se base sur la présence ou non de valeur de retour, alors qu'elle pourrait se baser sur la présence d'effets de bords. Selon cette définition, un algo ayant un effet de bord *et* une valeur de retour serait une fonction. Selon l'autre définition, ce serait une procédure. Dans l'absolu, je préférerai l'autre définition, mais pédagogiquement, il me semble plus facile d'introduire les choses ainsi. Étant donné que cela ne fait une différence que dans le cas limite, je pense que c'est une concession acceptable. Variables au sein d'une fonction -------------------------------- On a présenté au `chapitre précédent `:doc: la notion de variable. Il convient de décrire ici les différentes catégories de variables utilisées dans une fonction. Elles sont au nombre de trois : * les variables correspondant aux paramètres d'entrée ; * les variables correspondant aux paramètres de sortie ; * les *variables intermédiaires*. Les variables correspondant aux paramètres d'entrée ont une particularité : elles ont déjà une valeur au début de la fonction (on verra dans la section `Appel de fonction`_ d'où vient cette valeur). Elles n'ont donc pas besoin d'être affectées, et on évitera en général de changer leur valeur [#changement-entrées]_. Les variables correspondant aux paramètres de sortie, quant à elles, doivent absolument être affectées dans la fonction, puisque c'est le rôle de cette dernière de déterminer leur valeur (rappelons que les paramètres de sortie décrivent la solution au problème que l'on cherche à résoudre). Ces valeurs sont transmises à l'appelant par l'instruction ``return`` à la fin de la fonction. Les variables intermédiaires, enfin, sont toutes les autres variables qui peuvent être nécessaires au calcul des paramètres de sortie. Par définition, elles n'ont pas de valeur initialement (elle doivent donc être affectées avant d'être utilisées), et leur valeur est « oubliée » à la fin de la fonction (puisqu'elles ne sont pas données à l'instruction ``return``). Si l'on voit la fonction comme une boîte noire dont le rôle est d'effectuer une opération précise, alors : * les paramètres d'entrée contiennent les valeurs passées à la boîte noire ; * les paramètres de sortie contiennent les valeurs retournées par la boîte noire ; * les variables intermédiaires sont invisibles en dehors de la boîte noire. Imaginons que le rôle de notre boîte noire soit de déterminer quelles sont la plus petite et la plus grande valeur d'une liste de valeurs, ainsi que la moyenne des éléments de la liste. La liste de valeur est notre paramètre d'entrée, le minimum, le maximum et la moyenne sont les paramètres de sortie, et on imagine aisément que d'autres variables temporaires sont utilisées à l'intérieur de la fonction pour effectuer les calculs intermédiaires (par exemple, la somme des valeurs et le nombre de valeurs, nécessaires au calcul de la moyenne). Séquence ++++++++ La forme la plus simple d'enchaînement d'instructions composant une fonction est la `séquence`:index:. Les instructions sont écrites l'une après l'autre, séparées par un saut de ligne. Pour Python, il est important qu'elles soient toutes au même niveau d'indentation (c'est-à-dire précédées du même nombre d'espaces). Plus généralement, l'indentation est un aspect important de l'écriture d'algorithmes. En effet, un algorithme bien présenté et bien indenté facilite grandement sa lecture et sa compréhension. Elles sont toutes exécutées, dans l'ordre ou elles sont écrites. Considérons par exemple l'algorithme suivant, calculant les trois premières puissances d'un nombre :: def puissances(x): """ :entrée x: réel :pré-cond: Ø :sortie p2: réel :sortie p3: réel :sortie p4: réel :post-cond: p2 = x², p3 = x³, p4 = x⁴ """ p2 = x*x p3 = p2*x p4 = p3*x return p2, p3, p4 On peut représenter l'enchaînement des instructions de cet algorithme par le diagramme ci-dessous : .. graphviz:: digraph sequence { rankdir=LR; splines=ortho node [ shape=box ] i1 [ label="p2 = x*x" ] i2 [ label="p3 = p2*x" ] i3 [ label="p4 = p3*x" ] i4 [ label="return p2, p3, p4"] i1 -> i2 -> i3 -> i4 } Condition +++++++++ Dans certains cas, il est nécessaire d'exécuter des instructions différentes selon qu'une condition est remplie ou non. Dans ce cas, on utilisera un *enchaînement conditionnel*. Celui-ci est composé ainsi : * première ligne : - le mot-clé ``if``, - l'expression booléenne représentant la condition, - le caractère ``:``. * enchaînement d'insructions à exécuter si la condition est vraie - toutes précédées de quatre espaces de plus que la première ligne. * le mot-clé ``else:`` - précédé du même nombre d'espaces que la première ligne. * enchaînement d'instructions à exécuter si la condition est fausse - toutes précédées de quatre espaces de plus que la première ligne. NB : la clause ``else`` et les points suivants sont facultatifs. Les enchaînements suivant le ``if`` et le ``else`` ne sont bien sûr pas limités à des enchaînements séquentiels. Il peuvent comporter d'autres enchaînements conditionnels, ou des enchaînements répétitifs (cf. ci-dessous). La première instruction précédée du *même* nombre d'espaces (ou moins) que la première ligne (la ligne du ``if``) sera reconnue comme ne faisant pas partie de l'enchaînement conditionnel. Elle sera donc exécutée que la condition soit vraie ou non. Considérons par exemple l'algorithme suivant, qui calcule pour un nombre donné sa valeur absolue et son signe (représenté par le nombre 1 ou -1) :: def valabs_et_signe(x): """ :entrée x: réel :pré-cond: Ø :sortie signe: entier :sortie valabs: réel :post-cond: signe = 1 si x ≥ 0, -1 sinon :post-cond: valabs = |x| """ if x >= 0: signe = 1 valabs = x else: signe = -1 valabs = -x return signe, valabs On peut représenter l'enchaînement des instructions de cet algorithme par le diagramme ci-dessous : .. graphviz:: digraph condition { rankdir=LR; splines=ortho node [ shape=box ] t1 [ label="x >= 0", shape=diamond ] i1 [ label="signe = 1" ] i2 [ label="valabs = x" ] i3 [ label="signe = -1" ] i4 [ label="valabs = -x" ] j1 [ label="", shape=none, width=0, height=0 ] i5 [ label="return signe, valabs" ] t1 -> i1 [ taillabel="oui" ] i1 -> i2; i2 -> j1 [ arrowhead=none ] t1 -> i3 [ taillabel="non" ] i3 -> i4; i4 -> j1 [ arrowhead=none ] j1 -> i5 } Conditions multiples -------------------- Afin d'éviter d'imbriquer les ``if`` et les ``else`` les uns dans les autres, Python propose l'instruction ``elif`` (contraction de else if) qui se traduit en langage courant par "sinon si". Le ``elif`` doit être utilisé avec précaution et parcimonie, uniquement lorsque l'on est certain que toutes les conditions sont exclusives. En effet, les conditions sont vérifiées les unes après les autres jusqu'à ce qu'une condition soit vraie. Si une condition est vérifiée, les suivantes dans la liste ne sont pas examinées. Une suite de ``elif`` peut se terminer par un ``else`` qui sera donc traité si aucune condition n'a été vérifiée jusque là. Voici un exemple d'utilisation du ``elif`` :: def mention(note): """ :entrée note: réel :pré-cond: 0 <= note <= 20 :sortie: chaîne de caractères :post-cond: affiche "recalé" si la note est inférieure à 10, très bien si elle est supérieure à 16 et bien le reste du temps """ if note <= 10: print("recalé") elif note <=16 print("bien") else print("très bien") Répétition ++++++++++ Python supporte deux types d'enchaînements répétitifs, également appelés « enchaînements itératifs » ou « boucles » : la boucle ``while`` et la boucle ``for``. .. index:: boucle; while La boucle ``while`` ------------------- Dans certains cas, il est nécessaire d'exécuter les mêmes instructions un nombre de fois variable selon les valeurs d'entrées de l'algorithme. Plus précisément, on répétera ces instructions tant qu'une condition est remplie. Dans ce cas, on utilisera une boucle ``while``, qui est composée ainsi : * première ligne : - le mot-clé ``while``, - l'expression booléenne représentant la condition, - le caractère ``:``. * enchaînement d'instructions à exécuter tant que la condition est vraie - toutes précédées de quatre espaces de plus que la première ligne. Ici encore, l'enchaînement d'instructions suivant le ``while`` peut comporter tous types d'enchaînements (séquentiel, conditionnel, répétitif). La première instruction précédée du *même* nombre d'espaces (ou moins) que la première ligne (la ligne du ``while``) sera reconnue comme ne faisant pas partie de la boucle. Elle sera donc exécutée dès que la condition devient fausse. .. _fonc-nb-chiffres: Considérons par exemple l'algorithme suivant qui calcule le nombre de chiffres (en base 10) nécessaires à l'écriture d'un entier positif :: def nb_chiffres(n): """ :entrée n: entier :pré-cond: n > 0 :sortie c: entier :post-cond: n s'écrit en base 10 avec c chiffres """ c = 1 while n > 10: c = c+1 n = n//10 return c On peut représenter l'enchaînement des instructions de cet algorithme par le diagramme ci-dessous : .. graphviz:: digraph boucle_while { rankdir=LR; splines=ortho node [ shape=box ] i1 [ label="c = 1" ] t1 [ label="n > 10", shape=diamond ] i2 [ label="c = c+1" ] i3 [ label="n = n//10" ] i4 [ label="return c" ] i1 -> t1 t1 -> i2 [ taillabel="oui" ] i2 -> i3 i3 -> i4 [ style=invis ] i3 -> t1 [ constraint=false ] t1 -> i4 [ taillabel="non"; constraint=false ] } Il est intéressant de remarquer que, selon les valeurs en entrée, les instructions de la boucle peuvent être exécutée plusieurs fois, une seule fois, voire pas du tout. .. index:: boucle; for single: ! itérable La boucle ``for`` ----------------- Certaines valeurs manipulées par un algorithme peuvent être vues comme « contenant » d'autres valeurs ; par exemple, une chaîne de caractères peut être vue comme une liste d'éléments plus simples que sont chacun de ses caractères. Ces valeurs sont qualifiées d'**itérables** en Python (c'est-à-dire que l'on peut **itérer** dessus, autrement dit, les parcourir une par une dans l'ordre, et appliquer le même ensemble d'actions sur chacune d'entre elles), et peuvent être utilisées avec la boucle ``for``, qui est composée ainsi : * première ligne : - le mot-clé ``for``, - un nom de variable - le mot-clé ``in``, - l'itérable sur lequel on veut boucler - le caractère ``:``. * enchaînement d'instructions à exécuter pour chaque élément de l'itérable - toutes précédées de quatre espaces de plus que la première ligne. La première instruction précédée du *même* nombre d'espaces (ou moins) que la première ligne (la ligne du ``for``) sera reconnue comme ne faisant pas partie de la boucle. La variable nommée après le ``for`` prendra successivement pour valeur chacun des éléments de l'itérable; et pour chacun d'entre eux, les instructions de la boucle seront exécutées. Considérons par exemple l'algorithme suivant qui retourne la chaîne de caractères « miroir » de la chaîne passée en entrée :: def miroir(s): """ :entrée s: chaîne de caractères :pré-cond: Ø :sortie r: chaîne de caractères :post-cond: r est la chaîne miroir de s """ r = "" for c in s: r = c+r return r .. index:: range Il existe un cas particulier de boucle extrêmement fréquent : une boucle itérant sur des entiers successifs. Pour répondre à ce besoin, Python fournit la fonction ``range``, qui fournit un itérable contenant une séquence d'entier. Plus précisément : * ``range(i)`` itère sur l'intervalle [0,i[ * ``range(i, j)`` itère sur l'intervalle [i,j[ .. note:: Notez à nouveau l'interprétation des bornes en Python. La borne inférieure est toujours inclue, la borne supérieure est toujours exclue. Considérons par exemple l'algorithme suivant qui retourne la factorielle de l'entier n :: def factorielle(n): """ :entrée n: entier :pré-cond: n ≥ 0 :sortie f: entier :post-cond: f = n! = 1×2×3×...×(n-1)×n """ f = 1 for i in range(1, n+1): f = f*i return f .. note:: Il est toujours possible de remplacer une boucle ``for`` par une boucle ``while``. Cependant, dans de nombreux cas, la boucle ``for`` est plus lisible. .. index:: single: fonction; appel Appel de fonction +++++++++++++++++ Une fois que l'on a totalement défini une fonction, cette dernière fait alors partie des « capacités » de l'ordinateur. Pour indiquer à l'ordinateur qu'il doit *appeler* (ou utiliser) une fonction, on écrira une affectation dont : * la partie gauche comportera autant de variables que la fonction comporte de paramètres de sorties ; * la partie droite est constituée du nom de la fonction, suivi par la liste des valeurs des paramètres d'entrée, entre parenthèses et séparées, le cas échéant, par une virgule. Par exemple :: >>> i, j, k = puissances(8) >>> k = bonbons_restants(2*j, i-1) Dans les exemples ci-dessus, on voit que les valeurs passées aux paramètres d'entrée peuvent être des expressions complexes. On constate aussi que les variables recevant les valeurs des paramètres de sortie ne sont pas tenues d'avoir le même nom que ces paramètres ; c'est l'*ordre* des variables qui détermine leur correspondance avec les paramètres de sortie. Enfin, notons que, dans le cas particulier des fonctions n'ayant qu'un seul paramètre de sortie, l'appel à la fonction peut être utilisé directement dans une expression. Par exemple, au lieu d'écrire :: >>> i = bonbons_restants(10,3) >>> j = 2 * i on peut écrire directement :: >>> j = 2 * bonbons_restants(10, 3) .. index:: procédure Dans le cas d'une `procédure `:ref:, qui ne retourne aucune valeur, l'appel se limitera au nom de la procédure suivi de ses paramètres : >>> print("bonjour le monde") .. index:: portée single: variable; portée Portée des variables -------------------- Les variables utilisées dans une fonction sont *propres* à cette fonction. Elles ne sont ni visibles, ni utilisables depuis d'autres fonctions, même si ces dernière définissent une variable ayant le même nom. On dit que la *portée* de la variable est limitée à la fonction qui la définit [#portées]_. Considérons l'exemple ci-dessous : .. code-block:: python :linenos: def total_chiffres_fact(n): """ :entrée n: entier :pré-cond: n > 0 :sortie c: entier :post-cond: c et le nombre total de chiffre nécessaire pour écrire les factorielles de tous les entiers entre 1 et n """ f = 1 c = 0 for i in range(1, n+1): f = f*i c = c+nb_chiffres(f) return c Cette fonction appelle la fonction ``nb_chiffres`` définie `plus haut `:ref:. On remarquera que ces deux fonctions utilisent les mêmes noms de variable (`n`, `c`). Cependant, il n'y a aucune interaction entre la valeur de `n` (respectivement de `c`) dans ``nb_chiffres`` et la valeur de `n` (respectivement de `c`) dans ``total_chiffres_fact``. Il faut imaginer que, lorsque l'ordinateur exécute ``total_chiffres_fact``, il stocke les valeurs de `n`, `c` et `f` dans un emplacement E1 de sa mémoire, emplacement dédié aux variables "internes" à ``total_chiffres_fact\\. Lorsqu'à la ligne 13, on lui demande d'exécuter la fonction ``nb_chiffres``, il laisse de coté l'emplacement E1 et commence à travailler sur un emplacement E2, dédié aux variables internes de ``nb_chiffres`` dans lequel il va stocker les valeurs de `n` et `c` de la fonction ``nb_chiffres``. Lorsque cette dernière se termine, l'emplacement E2 est supprimé, et l'ordinateur travaille à nouveau sur l'emplacement E1 pour terminer l'exécution de ``total_chiffres_fact``. .. image:: ../_static/porteeVariables.png Vous pouvez faire la simulation sur Pythontutor pour mieux comprendre comment sont gérés les espaces mémoires (http://pythontutor.com). Il est cependant important de détailler ce qui se passe aux moments du passage de E1 à E2, et du retour de E2 à E1 : * au moment de passer de la fonction appelante (E1) à la fonction appelée (E2), les expressions passées aux paramètres d'entrée (entre les parenthèses) sont calculées avec les variables de E1, et leurs valeurs sont affectées aux variables correspondantes dans E2 ; * au moment de revenir de la fonction appelée à la fonction appelante, les valeurs des paramètres de sortie sont affectées aux variables correspondantes dans E1, ou substituées à l'appel de fonction si celui-ci est utilisé directement dans une expression [#return]_. Considérons l'exemple ci-dessus, où on aurait appelé la fonction ``total_chiffres_fact`` avec `n`\=5. Au premier passage à la ligne 13, les variables de ``total_chiffres_fact`` ont les valeurs suivantes : `n`\=5, `c`\=0, `i`\=1 et `f`\=1. À ce moment, l'ordinateur calcule les valeurs à passer aux paramètres d'entrée de ``nb_chiffres``, en l'occurrence un seul paramètre, dont la valeur est 1 (valeur de `f`). L'emplacement mémoire qui contiendra les variables de ``nb_chiffres`` est donc initialisé avec `n`\=1. À la fin de l'exécution de ``nb_chiffres``, ses variables ont pour valeur `n`\=1 et `c`\=1. Comme ``nb_chiffres`` est utilisée directement dans une expression, la valeur de paramètre de sortie `c` est substituée à l'appel de fonction, donc la ligne 13 de ``total_chiffres_fact`` revient ici à calculer :: c = c+1 dans l'emplacement mémoire de ``total_chiffres_fact``, donc avec `c`\=0. Notons aussi que la valeur de `n` dans ``total_chiffres_fact`` est toujours 5, et n'a pas été influencée par le fait que ``nb_chiffres`` utilisait une variable du même nom avec une valeur différente. .. index:: modularité L'apparente complexité de ce processus est en fait une simplification : elle permet au programmeur d'une fonction `f` de *ne pas se soucier* des noms de variables utilisés dans les autres fonctions (celles appelées par `f` comme celles qui appellent `f`). Il favorise donc la *modularité* du code. .. rubric:: Notes de bas de page .. [#espaces] En fait, peu importe le nombre d'espaces, mais toutes les lignes suivant la première doivent être *indentées* de la même manière, pour marquer leur appartenance à la définition de l'algorithme. La première ligne non-indentée sera considérée comme ne faisant plus partie de cette définition. On verra dans la suite du chapitre que toute la structure des algorithmes est ainsi définie par l'indentation. .. [#retourner] On dit d'ailleurs couramment qu'une fonction *retourne* ses paramètres de sortie. .. [#changement-entrées] Ceci n'est en rien une contrainte technique, mais plutôt une règle de bonne pratique (cf. `bonnes_pratiques`:doc:). Et même cette règle peut, dans certains cas, souffrir des exceptions. .. [#portées] Il est possible, en Python et d'en d'autres langages, de définir des variables avec une portée plus petite ou plus grande, mais nous ne traiterons pas de cela dans ce cours. .. [#return] En fait, c'est l'expression passée à ``return`` qui est systématiquement substituée à l'appel de la fonction. Python autorise une utilisation beaucoup plus souple de l'instruction ``return`` que celle préconisée dans ce cours.