Récursivité et programmation dynamique

Exercices corrigés

1. Qu'appelle-t-on mémoïsation ?

   • A.Le fait d'apprendre par cœur les valeurs d'une suite avant de coder
   • B.Une technique pour réduire la mémoire utilisée par un programme
   • C.Le remplacement de tous les appels récursifs par des boucles
   • D.Le stockage des résultats déjà calculés pour les réutiliser au lieu de les recalculerBonne réponse

   Réponse : D — Le stockage des résultats déjà calculés pour les réutiliser au lieu de les recalculer

   Mémoïser, c'est garder dans un dictionnaire (ou un tableau) le résultat de chaque sous-problème déjà résolu. Avant tout calcul, la fonction consulte ce cache : si la valeur y est, elle la renvoie directement. Attention au contresens de la deuxième option : la mémoïsation fait exactement l'inverse, elle consomme davantage de mémoire pour gagner énormément de temps. Et transformer la récursion en boucles, c'est l'approche ascendante, qui est une autre façon de faire de la programmation dynamique.

2. On définit fact(n) = 1 si n vaut 0, et n × fact(n − 1) sinon. Que vaut fact(5) ?

   • A.15
   • B.120Bonne réponse
   • C.24
   • D.720

   Réponse : B — 120

   Déroulons les appels : fact(5) = 5 × fact(4) = 5 × 4 × fact(3) = 5 × 4 × 3 × fact(2) = 5 × 4 × 3 × 2 × fact(1) = 5 × 4 × 3 × 2 × 1 × fact(0), et fact(0) vaut 1. Le produit fait 5 × 24 = 120. Répondre 15 revient à faire la somme 5 + 4 + 3 + 2 + 1 au lieu du produit ; 24 est fact(4) et 720 est fact(6) : deux erreurs de décalage d'un cran.

3. Dans une grille de 3 lignes et 3 colonnes de cases, on part de la case en haut à gauche et on ne peut se déplacer que d'une case vers la droite ou vers le bas. Combien de chemins mènent à la case en bas à droite ?

   • A.3
   • B.4
   • C.9
   • D.6Bonne réponse

   Réponse : D — 6

   On remplit la grille de proche en proche : le nombre de chemins menant à une case est la somme du nombre de chemins menant à la case du dessus et à celle de gauche. Toute la première ligne et toute la première colonne valent 1, puisqu'on ne peut y arriver qu'en ligne droite. Ligne 1 : 1, 1, 1. Ligne 2 : 1, 2, 3. Ligne 3 : 1, 3, 6. La case en bas à droite vaut donc 6. Répondre 9 reviendrait à compter le nombre de cases, ce qui n'a rien à voir.

4. Avec le système de pièces 1, 3 et 4, quel est le nombre MINIMAL de pièces nécessaires pour rendre la somme 6 ?

   • A.6
   • B.4
   • C.3
   • D.2Bonne réponse

   Réponse : D — 2

   La bonne solution est 3 + 3, soit 2 pièces seulement. On peut la trouver par programmation dynamique en remplissant le tableau des sommes croissantes : T[0] = 0, T[1] = 1, T[2] = 2, T[3] = 1, T[4] = 1, T[5] = 1 + min(T[4], T[2], T[1]) = 1 + 1 = 2, et T[6] = 1 + min(T[5], T[3], T[2]) = 1 + 1 = 2. La réponse 3 est celle que donne l'algorithme glouton, qui prend 4 puis se retrouve avec 2 à rendre, donc 1 + 1 : trois pièces au total. C'est exactement le contre-exemple qui montre que le glouton n'est pas toujours optimal.

5. Dans une fonction récursive, à quoi sert le cas de base ?

   • A.À accélérer les appels récursifs
   • B.À vérifier que les arguments sont bien du bon type
   • C.À fournir une réponse directe, sans nouvel appel récursif, ce qui garantit l'arrêtBonne réponse
   • D.À initialiser le dictionnaire de mémoïsation

   Réponse : C — À fournir une réponse directe, sans nouvel appel récursif, ce qui garantit l'arrêt

   Le cas de base est la valeur pour laquelle la fonction sait répondre immédiatement, sans se rappeler elle-même : fact(0) = 1, F(0) = 0 et F(1) = 1. C'est lui qui met fin à la chaîne d'appels. Sans cas de base, ou s'il n'est jamais atteint, la récursion se poursuit indéfiniment jusqu'à saturation de la pile d'appels. Il ne joue aucun rôle de vérification de type et n'a rien à voir avec la mémoïsation, qui est une optimisation ajoutée par-dessus.

6. La suite de Fibonacci est définie par F(0) = 0, F(1) = 1 et F(n) = F(n − 1) + F(n − 2). Que vaut F(6) ?

   • A.8Bonne réponse
   • B.13
   • C.6
   • D.21

   Réponse : A — 8

   Déroulons la suite terme à terme : F(0) = 0, F(1) = 1, F(2) = 1 + 0 = 1, F(3) = 1 + 1 = 2, F(4) = 2 + 1 = 3, F(5) = 3 + 2 = 5, F(6) = 5 + 3 = 8. Répondre 13 revient à donner F(7) : c'est l'erreur classique, due au fait que la suite commence à l'indice 0 et non à l'indice 1. Répondre 21 donnerait F(8).

7. Que se passe-t-il si une fonction récursive n'a pas de cas de base atteignable ?

   • A.Elle renvoie automatiquement la valeur None
   • B.Les appels s'empilent jusqu'à saturation de la pile, ce qui provoque une erreur de dépassement de récursionBonne réponse
   • C.Elle s'exécute normalement mais très lentement
   • D.Python la transforme automatiquement en boucle

   Réponse : B — Les appels s'empilent jusqu'à saturation de la pile, ce qui provoque une erreur de dépassement de récursion

   Chaque appel de fonction en attente occupe une place dans la pile d'appels, avec ses variables locales. Si aucun cas de base n'arrête la chaîne, les appels s'accumulent sans jamais se refermer : la pile déborde et Python lève une RecursionError (sa limite par défaut est de l'ordre de 1000 appels imbriqués). Le programme ne renvoie donc rien du tout, et il ne s'agit pas d'une simple lenteur : c'est un plantage. Python ne convertit jamais tout seul une récursion en boucle.

8. Le nombre minimal de déplacements pour résoudre les tours de Hanoï à n disques vaut 2 puissance n, moins 1. Combien de déplacements faut-il pour 4 disques ?

   • A.8
   • B.7
   • C.15Bonne réponse
   • D.16

   Réponse : C — 15

   On applique la formule : 2⁴ − 1 = 16 − 1 = 15 déplacements. On peut aussi la retrouver de proche en proche avec H(1) = 1 et H(n) = 2 × H(n − 1) + 1 : H(2) = 3, H(3) = 7, H(4) = 15. Répondre 16 revient à oublier de soustraire 1, et répondre 7 à donner le résultat pour 3 disques. La croissance est exponentielle : chaque disque supplémentaire double (à peu près) le travail.

9. Quel est le principe général de la programmation dynamique ?

   • A.Résoudre chaque sous-problème une seule fois et mémoriser son résultat pour le réutiliserBonne réponse
   • B.Modifier le programme pendant son exécution
   • C.Couper le problème en deux moitiés indépendantes que l'on traite séparément
   • D.Choisir à chaque étape la solution qui paraît localement la meilleure

   Réponse : A — Résoudre chaque sous-problème une seule fois et mémoriser son résultat pour le réutiliser

   La programmation dynamique s'applique quand les sous-problèmes se chevauchent : les mêmes calculs reviendraient plusieurs fois dans l'arbre d'appels. On les résout donc une seule fois et on garde leur résultat sous la main. Attention aux pièges de vocabulaire : couper en deux moitiés indépendantes, c'est « diviser pour régner » (le tri fusion), et prendre à chaque étape le meilleur choix local, c'est un algorithme glouton. Quant au nom « dynamique », il est purement historique et ne renvoie à aucune modification du code en cours d'exécution.

10. Quelle est la complexité en temps du calcul de F(n) par une fonction récursive mémoïsée ?

    • A.Exponentielle, la mémoïsation ne change pas la complexité
    • B.O(n²)
    • C.O(log n)
    • D.O(n)Bonne réponse

    Réponse : D — O(n)

    Avec la mémoïsation, chacune des valeurs F(0), F(1), …, F(n) n'est réellement calculée qu'une seule fois : tous les appels suivants sur le même indice se contentent de lire le cache, ce qui coûte un temps constant. Il y a donc de l'ordre de n calculs effectifs, d'où une complexité en O(n). C'est tout l'intérêt de la technique : on passe d'un coût exponentiel (15 appels rien que pour F(5), et des milliards pour F(50)) à un coût linéaire.

11. Quelle différence y a-t-il entre l'approche descendante et l'approche ascendante en programmation dynamique ?

    • A.La descendante part du problème initial et mémoïse une fonction récursive, l'ascendante remplit un tableau avec des boucles en partant des plus petits sous-problèmesBonne réponse
    • B.La descendante est toujours plus rapide que l'ascendante
    • C.La descendante donne un résultat approché, l'ascendante donne le résultat exact
    • D.L'ascendante n'utilise aucune mémoire supplémentaire

    Réponse : A — La descendante part du problème initial et mémoïse une fonction récursive, l'ascendante remplit un tableau avec des boucles en partant des plus petits sous-problèmes

    Ce sont deux mises en œuvre de la même idée. La version descendante garde le code récursif naturel et lui ajoute un cache : elle ne calcule que les sous-problèmes réellement utiles. La version ascendante abandonne la récursivité et remplit un tableau dans un ordre soigneusement choisi, des plus petits cas jusqu'au but. Elles donnent toutes deux le résultat exact et ont la même complexité en temps ; l'ascendante a simplement l'avantage de ne pas solliciter la pile d'appels, mais elle utilise bien de la mémoire pour son tableau.

12. Avec le système de pièces 1, 2 et 5, combien de pièces l'algorithme glouton utilise-t-il pour rendre 11 ?

    • A.2
    • B.5
    • C.3Bonne réponse
    • D.11

    Réponse : C — 3

    L'algorithme glouton prend à chaque étape la plus grosse pièce possible. Il prend 5, il reste 6. Il reprend 5, il reste 1. Il prend 1, il reste 0. Bilan : 5 + 5 + 1, soit 3 pièces. Et c'est bien l'optimum ici, car deux pièces ne peuvent pas dépasser 5 + 5 = 10. Répondre 11 correspondrait à ne rendre que des pièces de 1, ce qui est valide mais très loin d'être minimal.