Designing Modular Algorithms

# Designing Modular Algorithms ## Objectifs et prérequis Ce chapitre vise à développer la capacité des élèves à concevoir, analyser et implémenter des algorithmes modulaires en utilisant les sous-programmes (subroutines) et la récursion, tout en comprenant leurs limites en termes de complexité et de ressources. Les élèves apprendront à décomposer un problème en sous-tâches réutilisables, à modéliser des processus récursifs, à évaluer leur efficacité et à intégrer ces concepts dans une activité de synthèse. **Prérequis :** - Maîtrise des concepts de base de la programmation (variables, boucles, conditions, tableaux). - Compréhension des fonctions/procédures dans un langage de programmation (ex. : Python, Pascal ou pseudocode). - Notions élémentaires de complexité en temps (O-notation) et d’espace. - Familiarité avec la lecture et l’écriture de pseudocode structuré. --- ## I. Processing Subroutine Calls ### Définition et propriétés Un **sous-programme** (ou subroutine) est une séquence d’instructions nommée qui effectue une tâche spécifique et peut être appelée depuis différentes parties d’un programme. Il permet la modularité, la réutilisation du code et une meilleure lisibilité. > **À retenir :** Un sous-programme encapsule une logique indépendante, réduit la redondance et facilite le débogage et la maintenance. Lorsqu’un sous-programme est appelé, le processus suivant se produit : 1. **Sauvegarde de l’état** : l’adresse de retour (où reprendre après l’appel) est enregistrée (souvent sur la pile d’appels). 2. **Passage des paramètres** : les valeurs réelles sont copiées dans les paramètres formels (par valeur ou par référence, selon le langage). 3. **Exécution du corps** : les instructions du sous-programme sont exécutées. 4. **Retour** : la valeur de retour (si fonction) est passée, puis l’exécution reprend à l’adresse de retour sauvegardée. ### Exemple résolu : Calcul du factoriel avec sous-programme Considérons un sous-programme `factorial(n)` qui retourne $n!$ : ```pseudocode FUNCTION factorial(n : INTEGER) : INTEGER IF n <= 1 THEN RETURN 1 ELSE RETURN n * factorial(n - 1) END IF END FUNCTION ``` **Appel :** `factorial(4)` **Étapes d’exécution :** 1. Appel `factorial(4)` → sauvegarde adresse retour, passe `n=4` 2. `4 > 1` → appelle `factorial(3)` 3. Appel `factorial(3)` → sauvegarde adresse retour, passe `n=3` 4. `3 > 1` → appelle `factorial(2)` 5. Appel `factorial(2)` → sauvegarde adresse retour, passe `n=2` 6. `2 > 1` → appelle `factorial(1)` 7. Appel `factorial(1)` → sauvegarde adresse retour, passe `n=1` 8. `1 <= 1` → retourne `1` 9. Retour à `factorial(2)` : retourne `2 * 1 = 2` 10. Retour à `factorial(3)` : retourne `3 * 2 = 6` 11. Retour à `factorial(4)` : retourne `4 * 6 = 24` 12. Résultat final : `24` ### Exercices d’application corrigés **Exercice 1 :** Écrire un sous-programme `gcd(a, b)` qui retourne le plus grand commun diviseur de deux entiers positifs par l’algorithme d’Euclide. Tracer l’exécution pour `gcd(48, 18)`. **Correction :** ```pseudocode FUNCTION gcd(a, b : INTEGER) : INTEGER WHILE b ≠ 0 DO temp ← b b ← a MOD b a ← temp END WHILE RETURN a END FUNCTION ``` **Trace pour `gcd(48, 18)` :** | Étape | a | b | a MOD b | Nouvelle a | Nouvelle b | |-------|-----|-----|---------|------------|------------| | 1 | 48 | 18 | 48 mod 18 = 12 | 18 | 12 | | 2 | 18 | 12 | 18 mod 12 = 6 | 12 | 6 | | 3 | 12 | 6 | 12 mod 6 = 0 | 6 | 0 | | 4 | 6 | 0 | b=0 → arrêt | | | Résultat : `6` **Exercice 2 :** Quel est l’effet d’un appel de sous-programme sur la pile d’appels ? Illustrer avec l’appel `factorial(3)` dans le langage pseudocode ci-dessus. **Correction :** À chaque appel, l’adresse de retour et la valeur locale de `n` sont empilées. Pour `factorial(3)` : - Appel initial : pile vide → empile (retour à main, n=3) - Appel `factorial(2)` → empile (retour à factorial(3), n=2) - Appel `factorial(1)` → empile (retour à factorial(2), n=1) - Retour `factorial(1)` : dépile → reprend à factorial(2) avec n=1 - Retour `factorial(2)` : dépile → reprend à factorial(3) avec n=2 - Retour `factorial(3)` : dépile → reprend à main La pile atteint une profondeur de 3 appels imbriqués. --- ## II. Recursion ### Définition et propriétés La **récursion** est une technique de programmation où un sous-programme s’appelle lui-même pour résoudre un problème en le décomposant en sous-instances plus petites du même problème. Elle repose sur deux éléments essentiels : - Un **cas de base** (ou cas trivial) qui arrête la récursion. - Un **cas récursif** qui réduit le problème vers le cas de base. > **À retenir :** Toute définition récursive doit avoir un cas de base bien défini et une progression garantie vers ce cas pour éviter l’infini. ### Exemple résolu : Somme des éléments d’un tableau Calculer la somme des éléments d’un tableau `A[0..n-1]` de manière récursive. ```pseudocode FUNCTION sumArray(A : ARRAY OF INTEGER, n : INTEGER) : INTEGER IF n == 0 THEN RETURN 0 ELSE RETURN A[n-1] + sumArray(A, n-1) END IF END FUNCTION ``` **Appel :** `sumArray([2, 4, 6], 3)` **Étapes :** 1. `sumArray([2,4,6], 3)` → `6 + sumArray([2,4,6], 2)` 2. `sumArray([2,4,6], 2)` → `4 + sumArray([2,4,6], 1)` 3. `sumArray([2,4,6], 1)` → `2 + sumArray([2,4,6], 0)` 4. `sumArray([2,4,6], 0)` → `0` (cas de base) 5. Retour : `2 + 0 = 2` 6. Retour : `4 + 2 = 6` 7. Retour : `6 + 6 = 12` Résultat : `12` ### Exemple résolu : Parcours en profondeur d’un arbre binaire (affichage préfixe) ```pseudocode PROCEDURE preorder(node : TreeNode) IF node ≠ NULL THEN PRINT node.value preorder(node.left) preorder(node.right) END IF END PROCEDURE ``` Pour un arbre : ``` 1 / \ 2 3 / \ 4 5 ``` Appel : `preorder(racine)` → affichage : `1, 2, 4, 5, 3` ### Exercices d’application corrigés **Exercice 1 :** Écrire une fonction récursive `power(x, n)` qui calcule $x^n$ pour un entier $n \geq 0$. Tracer l’exécution pour `power(2, 5)`. **Correction :** ```pseudocode FUNCTION power(x : REAL, n : INTEGER) : REAL IF n == 0 THEN RETURN 1 ELSE RETURN x * power(x, n-1) END IF END FUNCTION ``` **Trace pour `power(2,5)` :** - `power(2,5)` → `2 * power(2,4)` - `power(2,4)` → `2 * power(2,3)` - `power(2,3)` → `2 * power(2,2)` - `power(2,2)` → `2 * power(2,1)` - `power(2,1)` → `2 * power(2,0)` - `power(2,0)` → `1` - Retour : `2 * 1 = 2` - Retour : `2 * 2 = 4` - Retour : `2 * 4 = 8` - Retour : `2 * 8 = 16` - Retour : `2 * 16 = 32` Résultat : $2^5 = 32$ **Exercice 2 :** Pourquoi la fonction suivante ne termine-t-elle pas ? ```pseudocode FUNCTION badRecurse(n : INTEGER) : INTEGER RETURN badRecurse(n + 1) END FUNCTION ``` **Correction :** Elle manque un cas de base. Chaque appel augmente `n`, s’éloignant davantage de toute condition d’arrêt. Il n’y a pas de progression vers un cas terminal → récursion infinie → débordement de pile. --- ## III. Recursion Limitations and Complexity ### Limitations de la récursion Malgré son élégance, la récursion présente des inconvénients pratiques : - **Consommation de mémoire** : chaque appel ajoute un cadre sur la pile d’appels (espace mémoire). Une récursion profonde peut provoquer un **débordement de pile** (stack overflow). - **Overhead de fonction** : chaque appel implique un coût en temps (sauvegarde/restoration de l’état, passage de paramètres). - **Difficulté de débogage** : suivre l’exécution récursive peut être complexe en raison de l’imbrication des appels. > **À retenir :** La récursion est élégante mais coûteuse en espace et en temps ; elle doit être utilisée avec discernement, surtout pour des profondeurs importantes. ### Analyse de complexité en temps et en espace Nous analysons la complexité en utilisant la notation asymptotique $O()$. #### Exemple 1 : Factoriel récursif ```pseudocode FUNCTION factorial(n) IF n <= 1 THEN RETURN 1 ELSE RETURN n * factorial(n-1) ``` - **Appels récursifs** : $n$ appels (de `n` down to `1`) - **Travail par appel** : $O(1)$ (multiplication et comparaison) - **Complexité en temps** : $T(n) = T(n-1) + O(1)$ → $T(n) = O(n)$ - **Complexité en espace** : chaque appel laisse un cadre sur la pile → $O(n)$ espace #### Exemple 2 : Recherche dichotomique récursive ```pseudocode FUNCTION binarySearch(A, low, high, key) IF low > high THEN RETURN -1 mid ← (low + high) // 2 IF A[mid] == key THEN RETURN mid ELSE IF A[mid] > key THEN RETURN binarySearch(A, low, mid-1, key) ELSE RETURN binarySearch(A, mid+1, high, key) ``` - **Appels récursifs** : chaque appel réduit l’intervalle de moitié → profondeur $O(\log n)$ - **Travail par appel** : $O(1)$ - **Complexité en temps** : $T(n) = T(n/2) + O(1)$ → $T(n) = O(\log n)$ - **Complexité en espace** : $O(\log n)$ (profondeur de la pile) #### Exemple 3 : Suite de Fibonacci naïve ```pseudocode FUNCTION fib(n) IF n <= 1 THEN RETURN n ELSE RETURN fib(n-1) + fib(n-2) ``` - **Arbre d’appels** : chaque appel `fib(n)` génère deux sous-appels → arbre binaire de hauteur $n$ - **Nombre d’appels** : approximativement $2^n$ (en fait, proportionnel au $n$-ième nombre de Fibonacci lui-même) - **Complexité en temps** : $O(2^n)$ (exponentielle) - **Complexité en espace** : $O(n)$ (profondeur maximale de la pile, pas le nombre total d’appels) > **À retenir :** La récursion naïve de Fibonacci est exponentielle en temps car elle recompute les mêmes valeurs plusieurs fois. Cela illustre l’importance de la programmation dynamique ou de la mémoisation. ### Tableau comparatif : Complexité des algorithmes récursifs | Algorithme | Cas de base | Appels récursifs | Travail par appel | Complexité en temps | Complexité en espace | |-------------------------|----------------------|------------------------|-------------------|---------------------|----------------------| | Factoriel | $n \leq 1$ | 1 appel : $n-1$ | $O(1)$ | $O(n)$ | $O(n)$ | | Somme de tableau | $n = 0$ | 1 appel : $n-1$ | $O(1)$ | $O(n)$ | $O(n)$ | | Recherche dichotomique | $low > high$ | 1 appel : moitié | $O(1)$ | $O(\log n)$ | $O(\log n)$ | | Fibonacci naïve | $n \leq 1$ | 2 appels : $n-1, n-2$ | $O(1)$ | $O(2^n)$ | $O(n)$ | | Hanoï (tours) | $n = 0$ | 2 appels : $n-1$ | $O(1)$ | $O(2^n)$ | $O(n)$ | > **À retenir :** La complexité en espace d’un algorithme récursif correspond généralement à la profondeur maximale de la pile d’appels, pas au nombre total d’appels. ### Exercices d’application corrigés **Exercice 1 :** Déterminer la complexité en temps et en espace de l’algorithme récursif suivant qui calcule la somme des premiers $n$ entiers : ```pseudocode FUNCTION sumN(n) IF n == 0 THEN RETURN 0 ELSE RETURN n + sumN(n-1) ``` **Correction :** - Appels : $n+1$ (de `n` à `0`) - Travail par appel : $O(1)$ - Temps : $T(n) = T(n-1) + O(1)$ → $O(n)$ - Espace : pile de profondeur $n+1$ → $O(n)$ **Exercice 2 :** Pourquoi l’algorithme de recherche dichotomique récursive est-il préférable en espace à une version qui copie des sous-tableaux à chaque appel ? **Correction :** Si on passait des sous-tableaux copiés (ex. : `A[low..mid-1]`), chaque appel nécessiterait $O(n)$ espace pour la copie, et avec $O(\log n)$ appels, l’espace total serait $O(n \log n)$. En passant uniquement les indices `low` et `high`, on évite la copie : chaque cadre de pile utilise $O(1)$ espace, donc espace total $O(\log n)$. **Exercice 3 :** Un élève propose une fonction récursive pour trouver le maximum d’un tableau : ```pseudocode FUNCTION maxArray(A, n) IF n == 1 THEN RETURN A[0] ELSE RETURN max(A[n-1], maxArray(A, n-1)) ``` Quelle est sa complexité en temps et en espace ? Est-elle optimale ? **Correction :** - Appels : $n$ appels (de `n` à `1`) - Travail par appel : $O(1)$ (comparaison et appel) - Temps : $O(n)$ - Espace : $O(n)$ (pile de profondeur $n$) Elle est asymptotiquement optimale en temps ($\Omega(n)$ nécessaire pour lire tous les éléments), mais pas en espace : une version itérative utiliserait $O(1)$ espace. La récursion ici apporte de la lisibilité mais pas d’efficacité spatiale. --- ## IV. Integration Activity ### Contexte de l’activité Les élèves doivent concevoir un programme qui résout un problème réel en combinant sous-programmes modulaires et récursion, puis analyser sa complexité. L’activité vise à intégrer les notions vues : décomposition en sous-tâches, appel de sous-programmes, conception récursive, évaluation des limites. ### Énoncé du problème Écrire un programme qui, donné un arbre binaire de recherche (BST), : 1. Vérifie s’il est bien formé (pour tout nœud, toutes les valeurs dans le sous-arbre gauche sont $<$ nœud, et toutes celles dans le sous-arbre droit sont $>$ nœud). 2. Retourne la hauteur de l’arbre. 3. Compte le nombre de feuilles (nœuds sans enfants). Le programme doit utiliser : - Au moins deux sous-programmes distincts (en dehors du `main`). - La récursion pour au moins une des tâches. - Une analyse de complexité en temps et en espace pour chaque sous-programme. ### Solution proposée (pseudocode) ```pseudocode TYPE TreeNode value : INTEGER left, right : TreeNode END TYPE FUNCTION isBST(node : TreeNode, min : INTEGER, max : INTEGER) : BOOLEAN IF node == NULL THEN RETURN TRUE END IF IF node.value < min OR node.value > max THEN RETURN FALSE END IF RETURN isBST(node.left, min, node.value - 1) AND isBST(node.right, node.value + 1, max) END FUNCTION FUNCTION height(node : TreeNode) : INTEGER IF node == NULL THEN RETURN -1 // hauteur d’un arbre vide = -1 (ou 0 si on compte les nœuds) END IF RETURN 1 + MAX(height(node.left), height(node.right)) END FUNCTION FUNCTION countLeaves(node : TreeNode) : INTEGER IF node == NULL THEN RETURN 0 END IF IF node.left == NULL AND node.right == NULL THEN RETURN 1 END IF RETURN countLeaves(node.left) + countLeaves(node.right) END FUNCTION PROCEDURE main() // Construction d’un arbre exemple : 4 / \ 2 6 / \ / \ 1 3 5 7 root ← new TreeNode(4) root.left ← new TreeNode(2) root.right ← new TreeNode(6) root.left.left ← new TreeNode(1) root.left.right ← new TreeNode(3) root.right.left ← new TreeNode(5) root.right.right ← new TreeNode(7) IF isBST(root, -∞, +∞) THEN PRINT "L'arbre est un BST valide." ELSE PRINT "L'arbre n'est pas un BST." END IF PRINT "Hauteur : ", height(root) PRINT "Nombre de feuilles : ", countLeaves(root) END PROCEDURE ``` ### Analyse de complexité #### 1. `isBST(node, min, max)` - Chaque nœud est visité exactement une fois. - Travail par nœud : $O(1)$ (comparaisons et appels récursifs) - **Temps** : $O(n)$ où $n$ est le nombre de nœuds - **Espace** : profondeur de la pile = hauteur de l’arbre - Dans le pire cas (arbre dégénéré) : $O(n)$ - Dans le meilleur cas (arbre équilibré) : $O(\log n)$ - Donc : $O(h)$ où $h$ est la hauteur #### 2. `height(node)` - Chaque nœud visité une fois. - Travail par nœud : $O(1)$ - **Temps** : $O(n)$ - **Espace** : $O(h)$ (profondeur de la pile) #### 3. `countLeaves(node)` - Chaque nœud visité une fois. - Travail par nœud : $O(1)$ - **Temps** : $O(n)$ - **Espace** : $O(h)$ ### Exercices d’application corrigés (activité intégrée) **Exercice 1 :** Pour l’arbre suivant : ``` 5 / \ 3 8 / \ \ 2 4 9 ``` Tracer l’exécution de `isBST(root, -∞, +∞)` et confirmer qu’il retourne `TRUE`. **Correction :** - Appel `isBST(5, -∞, +∞)` : $5 \in [-∞, +∞]$ → OK - Appel gauche : `isBST(3, -∞, 4)` → $3 \in [-∞, 4]$ → OK - Gauche-gauche : `isBST(2, -∞, 2)` → $2 \in [-∞, 2]$ → OK - Les deux enfants NULL → retourne `TRUE` - Gauche-droite : `isBST(4, 3, 4)` → $4 \in [3, 4]$ → OK - Retourne `TRUE` - Retour gauche : `TRUE AND TRUE = TRUE` - Appel droit : `isBST(8, 6, +∞)` → $8 \in [6, +∞]$ → OK - Droit-gauche : `isBST(NULL, 6, 7)` → `TRUE` - Droit-droite : `isBST(9, 9, +∞)` → $9 \in [9, +∞]$ → OK - Retourne `TRUE` - Retour droit : `TRUE AND TRUE = TRUE` - Retour racine : `TRUE AND TRUE = TRUE` **Exercice 2 :** Quelle est la hauteur de l’arbre ci-dessus ? Combien de feuilles contient-il ? **Correction :** - Chemins depuis la racine : - 5 → 3 → 2 : longueur 2 - 5 → 3 → 4 : longueur 2 - 5 → 8 → 9 : longueur 2 - Hauteur = nombre d’arêtes sur le plus long chemin = `2` - Feuilles : nœuds sans enfants → `2`, `4`, `9` → `3` feuilles **Exercice 3 :** Si l’arbre était dégénéré (ex. : 1 → 2 → 3 → 4 → 5, tous à droite), quelle serait la complexité en espace de `isBST` ? **Correction :** Dans un arbre dégénéré vers la droite, chaque appel récursif va à droite uniquement. La pile d’appels contiendra un cadre pour chaque nœud : 5 appels imbriqués pour 5 nœuds → profondeur $n$. → Complexité en espace : $O(n)$ **Exercice 4 :** Proposer une version itérative de `height` qui utilise $O(1)$ espace. Pourquoi n’est-ce pas possible pour `isBST` sans pile ou file explicite ? **Correction :** Une version itérative de `height` peut utiliser un parcours en niveau (BFS) avec une file, mais cela utilise $O(n)$ espace en pire cas. Pour une vraie $O(1)$ espace, il faudrait un arbre avec des pointeurs vers le parent (threaded tree) ou utiliser l’algorithme de Morris (modification temporaire), ce qui dépasse le cadre. Pour `isBST`, une vérification itérative nécessite de suivre les contraintes de min/max pour chaque nœud, ce qui implique naturellement une pile ou une file pour revenir en arrière → on ne peut pas le faire en $O(1)$ espace sans modifier l’arbre ou utiliser une structure auxiliaire. > **À retenir :** Certaines propriétés intrinsèquement récursives (comme la validation de BST) nécessitent une mémoire auxiliaire proportionnelle à la hauteur, même en itératif, sauf si l’arbre est modifié. --- ## Synthèse du chapitre - Les sous-programmes permettent la modularité, la réutilisation et une meilleure organisation du code via l’encapsulation de tâches spécifiques. - L’appel d’un sous-programme implique la sauvegarde de l’état (adresse de retour, paramètres) sur la pile d’appels, suivie de l’exécution et du retour. - La récursion est une technique où une fonction s’appelle elle-même pour résoudre un problème en le réduisant à des instances plus petites, nécessitant un cas de base et un pas récursif. - Toute définition récursive doit garantir une progression vers le cas de base pour éviter l’infini. - La récursion peut entraîner un débordement de pile et un overhead en temps et en espace ; sa complexité en espace correspond généralement à la profondeur maximale de la pile d’appels. - L’analyse de complexité des algorithmes récursifs se fait souvent par récurrence (ex. : $T(n) = T(n-1) + O(1)$ → $O(n)$). - Certains algorithmes récursifs naïfs (comme Fibonacci) ont une complexité exponentielle en temps dû à des recalculs répétés, illustrant le besoin d’optimisation (mémoisation, programmation dynamique). - L’activité d’intégration permet de combiner sous-programmes et récursion pour résoudre un problème concret (validation de BST, hauteur, comptage de feuilles), tout en analysant leur efficacité. - Le choix entre récursion et itération doit tenir compte de la lisibilité, de l’efficacité en espace et en temps, et des contraintes du problème. --- ## Glossaire - **Sous-programme (Subroutine)** : Une séquence d’instructions nommée qui effectue une tâche spécifique et peut être appelée depuis différentes parties d’un programme. - **Pile d’appels (Call Stack)** : Une structure de données LIFO qui stocke les informations d’état (adresse de retour, variables locales) lors des appels de sous-programmes. - **Cas de base (Base Case)** : La condition dans une définition récursive qui arrête la récursion et retourne une valeur directement. - **Cas récursif (Recursive Case)** : La partie d’une définition récursive qui réduit le problème vers le cas de base par un ou plusieurs appels récursifs. - **Débordement de pile (Stack Overflow)** : Une erreur qui se produit lorsque la pile d’appels dépasse sa capacité mémoire, généralement due à une récursion trop profonde ou infinie. - **Complexité en temps** : La quantité de temps qu’un algorithme prend en fonction de la taille de l’entrée, exprimée en notation asymptotique (ex. : $O(n)$). - **Complexité en espace** : La quantité de mémoire qu’un algorithme utilise en fonction de la taille de l’entrée, incluant la pile d’appels pour les algorithmes récursifs. - **Récursion linéaire (Linear Recursion)** : Une récursion où chaque appel génère au maximum un appel récursif (ex. : factoriel, somme de tableau). - **Récursion binaire (Binary Recursion)** : Une récursion où chaque appel génère deux appels récursifs (ex. : Fibonacci naïve, recherche dans un arbre binaire). - **Mémoisation (Memoization)** : Une technique d’optimisation qui stocke les résultats des appels de fonction coûteux pour éviter des recalculs répétés. - **Arbre binaire de recherche (BST)** : Un arbre binaire où pour chaque nœud, toutes les valeurs dans le sous-arbre gauche sont strictement inférieures et celles dans le sous-arbre droit sont strictement supérieures à la valeur du nœud. - **Hauteur d’un arbre** : Le nombre d’arêtes sur le plus long chemin depuis la racine jusqu’à une feuille. Par convention, la hauteur d’un arbre vide est $-1$.