.. _controle-flux: ******************* Le contrôle de flux ******************* La question fondamentale qui se pose lorsqu'on construit un programme informatique est *Comment un programme décide-t-il de la prochaine instruction à exécuter ?* La réponse à cette question est apportée par le contrôle de flux. Le contrôle de flux est essentiellement la manière dont l'exécution se déplace d'une instruction à une autre. Il existe plusieurs mécanismes de contrôle de flux, tels que les conditions, les boucles, les fonctions, etc., qui permettent au programme de choisir entre différentes options, de répéter des actions, d'appeler d'autres morceaux de code, etc. L'exécution linéaire ==================== La forme la plus simple de contrôle de flux est la séquence linéaire : les instructions s'exécutent séquentiellement, dans l'ordre où elles apparaissent. .. code-block:: python :linenos: print('A') print('B') print('C') Le programme s'exécute séquentiellement : il commence par exécuter la première instruction, puis la deuxième, puis la troisième. C'est le contrôle de flux le plus simple. .. mermaid:: :name: width100-1 graph TD A["print('A')"] B["print('B')"] C["print('C')"] A --> B B --> C On peut introduire l'idée que par défaut, un programme avance ligne après ligne. Mais intuitivement, on se rend vite compte que cela ne suffit pas pour faire des programmes intéressants. La question suivante est alors *Comment faire pour ne pas toujours avancer tout droit ?* .. quiz:: quiz-execution-lineaire :title: Exécution linéaire - :quiz:`{"type":"TF","answer":"T"}` Dans une exécution linéaire, les instructions s'exécutent dans l'ordre. - :quiz:`{"type":"TF","answer":"F"}` Une exécution linéaire est suffisante pour tous les programmes. - L'exécution linéaire suit un ordre :quiz:`{"type":"FB","answer":"séquentiel","flags":"fuzzy"}` - Le type d'exécution le plus simple est le type :quiz:`{"type":"SC","values":"séquentiel,conditionnel,aléatoire","answer":"séquentiel"}` Le chemin d'exécution ===================== Les actions essentielles d'un programme sont : - choisir ; - répéter ; - interrompre ; - appeler ; - revenir. Le choix -------- Voici une situation simple de choix. .. mermaid:: graph TD; initialisation-->test; test--V-->action1; test--F-->action2; Le programme doit choisir entre deux actions (action1 et action2) en fonction d'une condition (test). La répétition ------------- Il est des situations où il faut faire la même chose plusieurs fois, soit un nombre de fois connu à l'avance, soit jusqu'à ce qu'une condition soit remplie (ou ne soit plus remplie). C'est la répétition d'instructions. C'est là que les boucles entrent en jeu. .. mermaid:: flowchart TD Init["Initialisation"] Test{"Condition ?"} Corps["Corps de la boucle"] Fin([Fin]) Init --> Test Test -- V --> Corps Corps --> Test Test -- F --> Fin Le choix et la répétition sont les deux mécanismes de contrôle de flux les plus fondamentaux, et ils sont à la base de la plupart des programmes informatiques. Ils permettent de créer des programmes qui peuvent prendre des décisions et répéter des actions, ce qui est essentiel pour résoudre une grande variété de problèmes. Mais il se pose rapidement la question de la composition : comment faire pour structurer un programme permettant de gérer la complexité ? C'est là que les fonctions entrent en jeu. .. quiz:: quiz-chemins-execution :title: Chemins d'exécution - :quiz:`{"type":"TF","answer":"T"}` Le choix est un mécanisme fondamental de contrôle de flux. - La :quiz:`{"type":"FB","answer":"répétition","flags":"fuzzy"}` d'instructions est nécessaire pour faire la même chose plusieurs fois. - :quiz:`{"type":"TF","answer":"T"}` Les fonctions permettent de structurer un programme complexe. - Le mécanisme des :quiz:`{"type":"SC","values":"boucles,conditions,appels,sauts","answer":"appels"}` permet de transférer le contrôle à un autre morceau de code L'appel de fonction ------------------- L'appel de fonction est un mécanisme de contrôle du flux qui permet de structurer le programme en unités logiques, de réutiliser du code, et de gérer la complexité. Lorsque le programme appelle une fonction, il suspend l'exécution courante, transfère le contrôle à un autre morceau de code (le corps de la fonction), puis revient à l'exécution courante une fois la fonction terminée. .. mermaid:: flowchart LR subgraph Main["Programme principal"] A["Instruction 1"] B["Appel f()"] C["Instruction 2"] A --> B end subgraph Func["Fonction f"] F1["Début"] F2["Traitement"] F3["Retour"] F1 --> F2 --> F3 end B -.-> F1 F3 -.-> C Finalement, implémenter un contrôle de flux c'est répondre à trois questions fondamentales : +----------------------+----------------------------+ | Question | Structure associée | +======================+============================+ | Faut-il choisir ? | condition | +----------------------+----------------------------+ | Faut-il recommencer? | boucle | +----------------------+----------------------------+ | Où aller ensuite ? | appel de fonction / retour | +----------------------+----------------------------+ Une machine à états ------------------- On peut également représenter le contrôle de flux d'un programme par une machine à états, où les noeuds représentent les états du programme (ou les points d'exécution), et les arcs représentent les transitions entre ces états (ou les instructions qui modifient le flux d'exécution). Cette représentation permet de visualiser clairement les différentes possibilités d'exécution du programme, et de comprendre comment les différentes structures de contrôle (conditions, boucles, fonctions) interagissent pour déterminer le chemin d'exécution. On utilise ici l'exemple du problème de Syracuse (ou conjecture de Collatz) pour illustrer cette idée. Le programme prend un nombre entier n, et applique les règles suivantes : .. mermaid:: stateDiagram-v2 [*] --> Test Test --> Fin : n = 1 Test --> Pair : n pair Test --> Impair : n impair Pair : n ← n / 2 Impair : n ← 3n + 1 Pair --> Test Impair --> Test Fin --> [*] Pour n=5, le chemin d'exécution serait : .. mermaid:: stateDiagram-v2 [*] --> Test Test --> Fin : n = 1 Pair : n ← n / 2 Impair : n ← 3n + 1 Fin --> [*] %% Chemin d'exécution pour n=5 Test --> Impair : 5 Impair --> Test : 16 Test --> Pair : 16 Pair --> Test : 8 Test --> Pair : 8 Pair --> Test : 4 Test --> Pair : 4 Pair --> Test : 2 Test --> Pair : 2 Pair --> Test : 1 En pratique, la machine à états d'un programme peut être beaucoup plus complexe que cet exemple simple, avec de nombreux états et transitions. Cependant, cette représentation permet de comprendre que le programme n'est pas simplement une liste d'instructions, mais un réseau de chemins possibles d'exécution, déterminé par les différentes structures de contrôle utilisées dans le programme et modifiant les structures de données manipulées par le programme. .. quiz:: quiz-machines-etats :title: Machines à états - :quiz:`{"type":"TF","answer":"T"}` Une machine à états représente les différents chemins d'exécution d'un programme. - Les :quiz:`{"type":"FB","answer":"noeuds","flags":"fuzzy"}` d'une machine à états représentent les états du programme. - Les :quiz:`{"type":"FB","answer":"arcs","flags":"fuzzy"}` représentent les transitions entre états. - :quiz:`{"type":"TF","answer":"T"}` Le problème de Syracuse illustre bien ce qu'est une machine à états. Le lien avec l'architecture machine =================================== Le compilateur/interpréteur traduit les instructions de haut niveau (le langage informatique) en séquences d'instructions pour le processeur. Pour le contrôle de flux (choisir la prochaine instruction), un processeur connaît essentiellement : - avancer (NEXT) ; - comparer (COMPARE) pour produire une décision ; - sauter (JUMP) pour modifier le flux d'exécution ; - revenir (RETURN) pour restaurer le flux précédent. Prenons l'exemple simple d'une séquence d'instructions destinées à rechercher le maximum de deux nombres. .. code-block:: text IF a > b THEN c := a ELSE c := b Après traduction en assembleur, cela pourrait ressembler à ceci : +---------+------------------------+ | Adresse | Instruction | +=========+========================+ | 2 | LOAD a | +---------+------------------------+ | 4 | LOAD b | +---------+------------------------+ | 6 | COMPARE > | +---------+------------------------+ | 10 | POP_JUMP_IF_FALSE 20 | +---------+------------------------+ | 12 | LOAD a | +---------+------------------------+ | 14 | STORE c | +---------+------------------------+ | 16 | LOAD c | +---------+------------------------+ | 18 | RETURN | +---------+------------------------+ | 20 | LOAD b | +---------+------------------------+ | 22 | STORE c | +---------+------------------------+ | 24 | LOAD c | +---------+------------------------+ | 26 | RETURN | +---------+------------------------+ A l'exécution (avec a=5 et b=3) : +---------+----------------------+-----------------+--------------------+ | Adresse | Instruction | Etat de la pile | Etat de la mémoire | +=========+======================+=================+====================+ | 2 | LOAD a | [5] | a=5, b=3, c=? | +---------+----------------------+-----------------+--------------------+ | 4 | LOAD b | [5, 3] | a=5, b=3, c=? | +---------+----------------------+-----------------+--------------------+ | 6 | COMPARE > | [True] | a=5, b=3, c=? | +---------+----------------------+-----------------+--------------------+ | 10 | POP_JUMP_IF_FALSE 20 | [] | a=5, b=3, c=? | +---------+----------------------+-----------------+--------------------+ | 12 | LOAD a | [5] | a=5, b=3, c=? | +---------+----------------------+-----------------+--------------------+ | 14 | STORE c | [] | a=5, b=3, c=5 | +---------+----------------------+-----------------+--------------------+ | 16 | LOAD c | [5] | a=5, b=3, c=5 | +---------+----------------------+-----------------+--------------------+ | 18 | RETURN | [] | a=5, b=3, c=5 | +---------+----------------------+-----------------+--------------------+ | 20 | LOAD b | [] | | +---------+----------------------+-----------------+--------------------+ | 22 | STORE c | [] | | +---------+----------------------+-----------------+--------------------+ | 24 | LOAD c | [] | | +---------+----------------------+-----------------+--------------------+ | 26 | RETURN | [] | | +---------+----------------------+-----------------+--------------------+ A l'exécution (avec a=4 et b=6) : +---------+----------------------+-----------------+--------------------+ | Adresse | Instruction | Etat de la pile | Etat de la mémoire | +=========+======================+=================+====================+ | 2 | LOAD a | [4] | a=4, b=6, c=? | +---------+----------------------+-----------------+--------------------+ | 4 | LOAD b | [4, 6] | a=4, b=6, c=? | +---------+----------------------+-----------------+--------------------+ | 6 | COMPARE > | [False] | a=4, b=6, c=? | +---------+----------------------+-----------------+--------------------+ | 10 | POP_JUMP_IF_FALSE 20 | [] | a=4, b=6, c=? | +---------+----------------------+-----------------+--------------------+ | 12 | LOAD a | [] | | +---------+----------------------+-----------------+--------------------+ | 14 | STORE c | [] | | +---------+----------------------+-----------------+--------------------+ | 16 | LOAD c | [] | | +---------+----------------------+-----------------+--------------------+ | 18 | RETURN | [] | | +---------+----------------------+-----------------+--------------------+ | 20 | LOAD b | [6] | a=4, b=6, c=? | +---------+----------------------+-----------------+--------------------+ | 22 | STORE c | [] | a=4, b=6, c=6 | +---------+----------------------+-----------------+--------------------+ | 24 | LOAD c | [6] | a=4, b=6, c=6 | +---------+----------------------+-----------------+--------------------+ | 26 | RETURN | [] | a=4, b=6, c=6 | +---------+----------------------+-----------------+--------------------+ .. tip:: Le processeur avance normalement d'instruction en instruction. On peut voir le contrôle de flux comme le mécanisme qui consiste à l'empêcher d'avancer normalement. La répétition d'instructions est également traduite en sauts conditionnels. Par exemple, une boucle ``WHILE`` est traduite pour le processeur en une séquence d'instructions qui vérifie la condition, exécute le corps de la boucle, puis saute de nouveau à la vérification de la condition. Il en est de même pour les fonctions : l'appel d'une fonction est traduit en une instruction de saut vers le code de la fonction, et le retour d'une fonction est traduit en une instruction de saut vers l'instruction suivante après l'appel. .. important:: Cela signifie que toutes les structures de contrôle (y compris les fonctions) sont compilées/interprétées en sauts. .. quiz:: quiz-architecture-machine :title: Lien avec l'architecture machine - :quiz:`{"type":"TF","answer":"T"}` Un processeur connaît essentiellement 4 opérations de base pour le contrôle de flux. - Le ``JUMP`` permet de :quiz:`{"type":"FB","answer":"modifier","flags":"fuzzy"}` le flux d'exécution. - Le :quiz:`{"type":"FB","answer":"RETURN","size":6}` restaure le flux précédent d'exécution. - :quiz:`{"type":"TF","answer":"T"}` Toutes les structures de contrôle sont compilées en sauts. - L'opération :quiz:`{"type":"SC","values":"NEXT,COMPARE,JUMP,RETURN","answer":"COMPARE"}` produit une décision .. _repetition-instructions: Répétition d'instructions ========================= La répétition d'instructions est un concept fondamental en programmation, permettant d'exécuter un bloc de code plusieurs fois. Il s'inscrit dans la famille des structures de contrôle de flux, aux côtés des sélections (if/else) et des fonctions. Les langages de programmation proposent des variantes syntaxiques différentes, mais les **structures de boucle fondamentales** sont peu nombreuses. On peut les classer en trois grandes catégories : 1. **Boucles conditionnelles** : la répétition est contrôlée par une condition qui est évaluée avant ou après l'exécution du bloc de code (while, do-while, repeat-until). 2. **Boucles de comptage** : la répétition est contrôlée par une variable qui évolue automatiquement (for). 3. **Boucles de parcours** : la répétition est contrôlée par la traversée d'une collection d'éléments (for-each). D'un point de vue théorique, presque toutes les boucles se réduisent à : 1. un état ; 2. une condition ; 3. une transition. Autrement dit :: tant que l'invariant est conservé transformer l'état fin C'est pourquoi on peut enseigner les boucles indépendamment du langage, puis montrer ensuite les réalisations syntaxiques en Python, C, Java, etc. Les boucles conditionnelles --------------------------- On peut classer les boucles conditionnelles selon la manière dont la répétition est contrôlée. Ce contrôle peut avoir lieu avant l'exécution du bloc de code (pré-test), après l'exécution du bloc de code (post-test). Bien que ces deux formes soient interchangeables, elles ont des caractéristiques différentes qui les rendent plus adaptées à certains types de problèmes. Ainsi on choisira une boucle post-test uniquement lorsque le bloc de code doit s'exécuter au moins une fois pour établir la condition de répétition. Ces boucles nécessitent **un prédicat** qui est évalué à chaque itération pour déterminer à travers **une condition** si la boucle doit continuer ou s'arrêter. Le prédicat est une expression booléenne qui dépend de l'état du programme. .. important:: La distinction entre un prédicat et une condition est subtile mais importante. Un **prédicat** est une expression logique qui peut être vraie ou fausse selon les valeurs de ses variables. Un prédicat décrit une propriété des données. Le prédicat lui-même ne provoque aucune action. Une **condition** est un prédicat utilisé pour décider du prochain état du programme. Pour résumer : ============= =============================================== Notion Rôle ============= =============================================== Prédicat Décrit une propriété vraie ou fausse Condition Utilise un prédicat pour choisir une transition Précondition Prédicat devant être vrai avant une opération Postcondition Prédicat devant être vrai après une opération Invariant Prédicat devant rester vrai pendant l'exécution ============= =============================================== On pourrait dire qu'en programmation structurée : * les **données** sont décrites par des valeurs, * les **propriétés des données** sont décrites par des prédicats, * les **changements de contrôle** sont gouvernés par des conditions, * les **changements d'état** sont réalisés par des instructions. Boucle conditionnelle en pré-test ................................. La condition est testée **avant** l'exécution du corps :: tant que condition faire instructions fin .. code-block:: python while condition: instructions .. code-block:: c while (condition) { instructions; } les caractéristiques de ce type de boucle sont les suivantes : * elle peut ne jamais s'exécuter ; * sa forme est adaptée quand on ne connaît pas à l'avance le nombre d'itérations. .. quiz:: quiz-pretest :title: Boucle en pré-test - La condition est testée :quiz:`{"type":"FB","answer":"avant","size":5}` l'exécution du corps. - :quiz:`{"type":"TF","answer":"T"}` Une boucle pré-test peut ne jamais s'exécuter. - En Python, on utilise le mot-clé :quiz:`{"type":"FB","answer":"while","size":5}` pour une boucle pré-test. - :quiz:`{"type":"TF","answer":"T"}` La boucle pré-test est adaptée quand on ne connaît pas le nombre d'itérations. Boucle conditionnelle en post-test .................................. La condition est testée **après** l'exécution du corps :: répéter instructions tant que condition ou :: répéter instructions jusqu'à condition Le corps est exécuté au moins une fois, puis la condition est testée. Python n'implémente pas directement ce type de boucle, mais on peut le simuler avec une boucle `while` et un `break` en établissant un prédicat vrai au début du bloc de code, puis en le mettant à jour à la fin du bloc de code. Par exemple : .. code-block:: python predicat = True while predicat: instructions En langage C, on peut utiliser la structure `do-while` qui est une boucle post-test. .. code-block:: c do { instructions; } while (condition); Les caractéristiques de ce type de boucle sont les suivantes : * une exécution minimale garantie ; * adaptée quand on ne connaît pas à l'avance le nombre d'itérations, mais on sait que le bloc doit s'exécuter au moins une fois. .. image:: images/prog-e3-17-controle-flux-bipbip-coyote.jpg :width: 40 % :alt: Le processus de compilation :align: center .. quiz:: quiz-posttest :title: Boucle en post-test - La condition est testée :quiz:`{"type":"FB","answer":"après","size":5}` l'exécution du corps. - :quiz:`{"type":"TF","answer":"T"}` Une boucle post-test s'exécute au moins une fois. - En Python, on peut simuler une boucle post-test avec :quiz:`{"type":"FB","answer":"while True","flags":"fuzzy"}` et un break. - :quiz:`{"type":"TF","answer":"T"}` En C, la structure `do-while` est une boucle post-test. .. exercice:: Pré test et post test (Python) (sans IA) Il est nécessaire que VS Code soit démarré sur la machine hôte, pointe vers le répertoire ``e3-programmation-labs-student`` et que le container Docker soit lancé. Créer un fichier :file:`exercices/boucles.py` qui contient - une fonction secondaire :file:`boucle_pre_test()` - qui prend en argument un entier ``n`` ; - et qui retourne la somme des nombres de 1 à ``n`` implémentée avec une boucle pré-test. - une fonction secondaire :file:`boucle_post_test()` - qui prend en argument un entier ``n`` ; - et qui retourne la somme des nombres de 1 à ``n`` implémentée avec une boucle post-test. - une fonction principale :file:`main()` qui appelle les deux fonctions précédentes avec ``n=100`` et affiche les résultats. Une fois l'exercice terminé, effectuer une :ref:`revue de code `, ajouter la :ref:`documentation `, et s'assurer que les repos local et distant soient correctement :ref:`synchronisés `. .. exercice:: Pré test et post test (C) (sans IA) Il est nécessaire que VS Code soit démarré sur la machine hôte, pointe vers le répertoire ``e3-programmation-labs-student`` et que le container Docker soit lancé. Créer un fichier :file:`exercices/boucles.c` qui contient - une fonction secondaire :file:`bouclepretest()` - qui prend en argument un entier ``n`` ; - et qui retourne la somme des nombres de 1 à ``n`` implémentée avec une boucle pré-test. - une fonction secondaire :file:`boucleposttest()` - qui prend en argument un entier ``n`` ; - et qui retourne la somme des nombres de 1 à ``n`` implémentée avec une boucle post-test. - une fonction principale :file:`main()` qui appelle les deux fonctions précédentes avec ``n=100`` et affiche les résultats Une fois l'exercice terminé, effectuer une :ref:`revue de code `, ajouter la :ref:`documentation `, et s'assurer que les repos local et distant soient correctement :ref:`synchronisés `. .. # Python pré-test n = 100 somme = 0 i = 1 while i <= n: somme += i i += 1 print(f"La somme des nombres de 1 à {n} est {somme}") # Python post-test n = 100 somme = 0 i = 1 while True: somme += i i += 1 if i > 100: break # C pré test int main() { int n = 100; int somme = 0; int i = 1; while (i <= n) { somme += i; i++; } printf("La somme des nombres de 1 à %d est %d\n", n, somme); return 0; } # C post test int main() { int n = 100; int somme = 0; int i = 1; do { somme += i; i++; } while (i <= n); printf("La somme des nombres de 1 à %d est %d\n", n, somme); return 0; } Boucle de comptage ------------------ Une variable évolue automatiquement au cours de la boucle, généralement de manière linéaire. La condition de répétition est souvent liée à cette variable :: pour variable allant de début à fin faire instructions fin .. code-block:: python for i in range(debut, fin, pas): instructions .. code-block:: c for (int i = debut; i < fin; i+=pas) { instructions; } Les caractéristiques de ce type de boucle sont les suivantes : * nombre d'itérations connu a priori ; * mauvaise pratique pour le parcours de collection en Python, on lui préfère les boucles de parcours ; * très utilisée pour parcourir les tableaux en C. .. quiz:: quiz-boucle-comptage :title: Boucle de comptage - La boucle de comptage contrôle la répétition avec une :quiz:`{"type":"FB","answer":"variable","flags":"fuzzy"}` qui évolue automatiquement. - :quiz:`{"type":"TF","answer":"T"}` Le nombre d'itérations est connu a priori dans une boucle de comptage. - En Python, on utilise :quiz:`{"type":"FB","answer":"for,range","flags":"sequence,ordered","size":5}` pour créer une boucle de comptage. - :quiz:`{"type":"TF","answer":"F"}` C'est une bonne pratique d'utiliser une boucle de comptage pour parcourir les collections en Python. Boucle de parcours ------------------ La boucle parcourt directement les éléments d'une collection :: pour chaque élément dans collection faire instructions fin .. code-block:: python for element in collection: instructions Les caractéristiques de ce type de boucle sont les suivantes : * masque les indices, mais il est possible d'y accéder avec des fonctions comme `enumerate` ; * plus déclarative ; * très fréquente dans les langages modernes ; * n'existe pas en C, mais peut être simulée avec des pointeurs ou des indices. .. quiz:: quiz-boucle-parcours :title: Boucle de parcours - La boucle de parcours itère directement sur les :quiz:`{"type":"FB","answer":"éléments","flags":"fuzzy"}}` d'une collection. - :quiz:`{"type":"TF","answer":"T"}` Une boucle de parcours masque les indices. - En Python, on utilise :quiz:`{"type":"FB","answer":"for","size":3}` pour parcourir une collection. - La fonction :quiz:`{"type":"SC","values":"enumerate,range,sorted","answer":"enumerate"}}` permet d'accéder aux indices dans une boucle de parcours Boucle infinie -------------- Comme son nom l'indique, la boucle s'exécute indéfiniment. Elle peut être utilisée pour des serveurs, des interfaces graphiques, ou des programmes qui doivent rester actifs jusqu'à une interruption externe. Il n'y a pas de condition d'arrêt intrinsèque :: répéter indéfiniment instructions fin .. code-block:: python while True: instructions .. code-block:: c for (;;) { instructions; } La caractéristique de cette boucle est que l'arrêt dépend d'un `break`, d'un événement, ou d'une interruption externe. .. quiz:: quiz-boucle-infinie :title: Boucle infinie - :quiz:`{"type":"TF","answer":"F"}` Une boucle infinie s'exécute toujours indéfiniment. - En Python, on crée une boucle infinie avec :quiz:`{"type":"FB","answer":"while True","flags":"fuzzy"}` - En C, on crée une boucle infinie avec :quiz:`{"type":"FB","answer":"for(;;)","flags":"fuzzy"}` - Généralement on arrête une boucle infinie avec :quiz:`{"type":"SC","values":"break,condition,compteur","answer":"break"}` Correspondance boucle / récursion --------------------------------- Toute boucle peut être remplacée par une fonction récursive et inversement. Par exemple, la boucle suivante : .. code-block:: python def main(): n = 10 while n > 0 n = n-1 if __name__ == "__main__": main() .. code-block:: c #include int main() { int n = 10; while (n > 0) { n = n - 1; } return 0; } peut être remplacée par la fonction récursive suivante : .. code-block:: python def f(n): if n <= 0: return f(n - 1) def main(): f(10) if __name__ == "__main__": main() .. code-block:: c #include void f(int n) { if (n <= 0) { return; } f(n - 1); } int main() { f(10); return 0; } La différence entre les deux versions est que la première utilise une structure de contrôle de type boucle, tandis que la seconde utilise une fonction récursive. Cependant, les deux versions accomplissent la même tâche : décrémenter n jusqu'à ce qu'il atteigne 0. La réciproque est vraie : toute fonction récursive peut être transformée en une boucle. On considère la version récursive de la fonction de Fibonacci (naïve): .. code-block:: python def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2) def main(): print(fib(10)) if __name__ == "__main__": main() .. #include int fib(int n) { if (n <= 1) { return n; } return fib(n - 1) + fib(n - 2); } int main() { printf("%d\n", fib(10)); return 0; } Cette fonction récursive peut être transformée en une version itérative : .. code-block:: python def fib(n): if n <= 1: return n a, b = 0, 1 for _ in range(2, n + 1): a, b = b, a + b return b def main(): print(fib(10)) if __name__ == "__main__": main() .. #include int fib(int n) { if (n <= 1) { return n; } int a = 0, b = 1; for (int i = 2; i <= n; i++) { int temp = a; a = b; b = temp + b; } return b; } int main() { printf("%d\n", fib(10)); return 0; } .. exercice:: Fonction de Fibonacci (C) (sans IA) Il est nécessaire que VS Code soit démarré sur la machine hôte, pointe vers le répertoire ``e3-programmation-labs-student`` et que le container Docker soit lancé. Créer un fichier :file:`exercices/fibonacci.c`, et écrivez les fonctions secondaires :func:`fibr` et :func:`fibi` les fonctions de Fibonacci récursive et itérative. Vérifier le bon fonctionnement du programme. Une fois l'exercice terminé, effectuer une :ref:`revue de code `, ajouter la :ref:`documentation `, et s'assurer que les repos local et distant soient correctement :ref:`synchronisés `. La différence entre les deux versions est que la première utilise la récursion pour gérer la répétition, tandis que la seconde utilise une boucle. Cependant, les deux versions accomplissent la même tâche : calculer le n-ième nombre de Fibonacci. .. important:: La fonction est explicitement un mécanisme de répétition. Dans certains langages fonctionnels, les fonctions remplacent presque toutes les structures de contrôle. Dans d'autres, les fonctions sont utilisées principalement pour la composition, tandis que la sélection et la répétition sont utilisées pour le contrôle de flux (Python, C). .. quiz:: quiz-boucle-recursion :title: Boucle et récursion - :quiz:`{"type":"TF","answer":"T"}` Toute boucle peut être remplacée par une fonction récursive. - :quiz:`{"type":"TF","answer":"F"}` Toutes les fonctions récursives ne peuvent pas être transformées en boucle. Boucles génératives / paresseuses --------------------------------- La production des valeurs se fait progressivement ce qui permet de traiter des flux de données potentiellement infinis ou de grande taille sans les charger entièrement en mémoire. .. code-block:: python for x in generateur(): instructions Cette boucle est utilisée dans les flux, pipelines, données infinies... Boucles événementielles ----------------------- La répétition est pilotée par des événements externes. Elle est courante dans les interfaces graphiques, les serveurs, ou les systèmes réactifs. Voilà un exemple simple de boucle évènementielle en Python avec la bibliothèque `tkinter` qui permet de créer des interfaces graphiques. .. code-block:: python :linenos: import tkinter as tk # Fonction appelée quand on clique sur le bouton def on_button_click(): print("Bouton cliqué !") # Création de la fenêtre principale root = tk.Tk() root.title("Exemple de boucle événementielle avec Tkinter") # Ajout d'un bouton button = tk.Button(root, text="Cliquez-moi !", command=on_button_click) button.pack(pady=20, padx=20) # Lance la boucle événementielle de Tkinter root.mainloop() La ligne 12 définit un bouton qui, lorsqu'il est cliqué, appelle la fonction `on_button_click` définie à la ligne 4. La ligne 16 lance la boucle événementielle de Tkinter qui attend les événements et réagit en conséquence. La boucle est ici interne et ne se distingue pas dans le code par une structure classique. Synthèse -------- Toutes ces formes de boucles peuvent être ramenées à quelques idées fondamentales : .. list-table:: Concepts et questions associées :header-rows: 1 :widths: 50 50 * - Concept - Question * - Répétition conditionnelle - « Continue-t-on ? » * - Parcours - « Quel élément traiter ? » * - Comptage - « Combien de fois ? » * - Génération - « Quelle prochaine valeur ? » * - Réaction - « Quel événement attendre ? » * - Récursion - « Quel sous-problème reste-t-il ? » Le test conditionnel ==================== Le test conditionnel est le mécanisme de contrôle de flux le plus fondamental. Il est utilisé pour implémenter toutes les formes de boucles. Fondamentalement, un test conditionnel consiste à évaluer un prédicat et à choisir entre deux chemins d'exécution en fonction de la valeur de ce prédicat. Si le prédicat est vrai, le programme suit un chemin ; s'il est faux, il suit un autre chemin. On peut éventuellement avoir plusieurs chemins en utilisant des tests conditionnels imbriqués ou des structures de sélection multiples. Test simple ----------- Par test simple, on entend un test qui ne comporte qu'une seule condition, et donc une seule alternative. Parfois cette alternative est implicite, c'est-à-dire qu'il n'y a pas d'action à effectuer si la condition est fausse. Dans ce cas, le programme continue simplement avec l'instruction suivante après le test. En langage C, cela se traduit par l'utilisation de l'instruction ``if`` assortie éventuellement d'une instruction ``else`` pour gérer l'alternative. .. code-block:: c if (condition) { bloc_instructions; } if (condition) { bloc_instructions_1; } else { bloc_instructions_2; } En Python, on utilise également l'instruction :keyword:`if`, mais la syntaxe est légèrement différente. .. code-block:: python if condition: bloc_instructions if condition: bloc_instructions_1 else: bloc_instructions_2 .. quiz:: quiz-test-simple :title: Test simple - :quiz:`{"type":"TF","answer":"T"}` Un test simple comporte une seule condition. - :quiz:`{"type":"TF","answer":"T"}` L'alternative ``else`` est optionnelle dans un test simple. - Un test simple sans ``else`` signifie que l'alternative est :quiz:`{"type":"FB","answer":"implicite","flags":"fuzzy"}` - :quiz:`{"type":"SC","values":"if,else,elif,switch","answer":"if"}` introduit un test simple en C et Python. Test multiple ------------- Il existe des situations où il faut choisir entre plusieurs alternatives. Cela se fait en utilisant des tests conditionnels imbriqués ou des structures de sélection multiples. En langage C, cela se traduit par l'utilisation de l'instruction ``if`` avec plusieurs ``else if`` pour gérer les différentes alternatives. .. code-block:: c if (condition1) { bloc_instructions_1; } else if (condition2) { bloc_instructions_2; } else { bloc_instructions_3; } Il est important de comprendre que chaque condition est évaluée dans l'ordre, et que dès qu'une condition est vraie, le bloc d'instructions correspondant est exécuté, et le programme continue à la première instruction qui suit le test. Les conditions suivantes ne sont pas évaluées. Le corollaire est que l'ordre des conditions peut affecter le comportement du programme. En Python, cela se traduit par l'utilisation des instructions :keyword:`if`, :keyword:`elif` et :keyword:`else`. .. code-block:: python if condition1: bloc_instructions_1 elif condition2: bloc_instructions_2 else: bloc_instructions_3 .. quiz:: quiz-test-multiple :title: Test multiple - :quiz:`{"type":"TF","answer":"T"}` Dans un test multiple, les conditions sont évaluées dans l'ordre. - :quiz:`{"type":"TF","answer":"F"}` Toutes les conditions d'un test multiple sont toujours évaluées. - En Python, le mot-clé :quiz:`{"type":"FB","answer":"elif","size":4}` permet de tester une condition additionnelle. - :quiz:`{"type":"TF","answer":"T"}` L'ordre des conditions peut affecter le comportement du programme. - :quiz:`{"type":"TF","answer":"F"}` Une fois qu'une condition est vraie, les conditions suivantes sont parfois évaluées Sélection multiple ------------------- La sélection multiple est une structure de contrôle qui permet de choisir entre plusieurs alternatives en fonction de la valeur d'une expression. En C, cela se fait avec l'instruction ``switch`` .. code-block:: c switch (expression) { case value1: bloc_instructions_1; break; case value2: bloc_instructions_2; break; default: bloc_instructions_default; break; } Ici l'instruction ``break`` est utilisée pour sortir de la structure ``switch`` après l'exécution du bloc d'instructions correspondant à la valeur de l'expression. Si l'instruction ``break`` est omise, l'exécution continue dans le bloc suivant, ce qui peut entraîner des comportements inattendus. Si aucune des valeurs ne correspond, le bloc d'instructions par défaut est exécuté. En Python, on utilise généralement le mot-clé :keyword:`match` ou un dictionnaire pour un comportement similaire. :keyword:`match` est plus puissant car il permet de faire du pattern matching. .. code-block:: python match expression: case value1: bloc_instructions_1 case value2: bloc_instructions_2 case _: bloc_instructions_default .. quiz:: quiz-selection-multiple :title: Sélection multiple - :quiz:`{"type":"TF","answer":"T"}` L'instruction ``break`` dans un ``switch`` permet de sortir de la structure. - :quiz:`{"type":"TF","answer":"T"}` Si ``break`` est omis dans un ``switch``, l'exécution continue au bloc suivant. - En C, l'instruction :quiz:`{"type":"FB","answer":"switch","size":6}}` permet de choisir entre plusieurs alternatives. - En Python, le mot-clé :quiz:`{"type":"FB","answer":"match","size":5}}` permet le pattern matching. - :quiz:`{"type":"TF","answer":"T"}`La clause ``case _`` dans une sélection multiple Python représente tous les autres cas. - Quelles structures peuvent être utilisées pour une sélection multiple ? :quiz:`{"type":"SC","values":"if-elif-else,switch-case,match-case,toutes","answer":"toutes"}}` Labs ==== .. _exercice-coffre-fort: .. exercice:: Contrôle d'un coffre-fort (C) (sans IA) Il est nécessaire que VS Code soit démarré sur la machine hôte, pointe vers le répertoire ``e3-programmation-labs-student`` et que le container Docker soit lancé. Le répertoire concerné est ``lab_c_coffrefort``. Lisez attentivement le fichier :file:`README.md` pour comprendre la consigne. Il est efficace d'y accéder depuis le dépôt distant pour profiter du formatage. Une fois l'exercice terminé, effectuer une :ref:`revue de code `, ajouter la :ref:`documentation `, et s'assurer que les repos local et distant soient correctement :ref:`synchronisés `. .. _exercice-test-primalite: .. exercice:: Nombres premiers (Python) (sans IA) Il est nécessaire que VS Code soit démarré sur la machine hôte, pointe vers le répertoire ``e3-programmation-labs-student`` et que le container Docker soit lancé. Le lab concerné est ``lab_python_primes``. Lisez attentivement le fichier :file:`README.md` pour comprendre la consigne. Il est efficace d'y accéder depuis le dépôt distant pour profiter du formatage. Une fois l'exercice terminé, effectuer une :ref:`revue de code `, ajouter la :ref:`documentation `, et s'assurer que les repos local et distant soient correctement :ref:`synchronisés `. .. _exercice-comptage-nombres-premiers: .. exercice:: Nombres premiers (C) (sans IA) Il est nécessaire que VS Code soit démarré sur la machine hôte, pointe vers le répertoire ``e3-programmation-labs-student`` et que le container Docker soit lancé. Le lab concerné est ``lab_c_primes``. Lisez attentivement le fichier :file:`README.md` pour comprendre la consigne. Il est efficace d'y accéder depuis le dépôt distant pour profiter du formatage. Une fois l'exercice terminé, effectuer une :ref:`revue de code `, ajouter la :ref:`documentation `, et s'assurer que les repos local et distant soient correctement :ref:`synchronisés `.