====== Exemples de récurrences ======

===== Triangle de Sierpinski ======

Il s'agit d'une figure construite récursivement. On peut définir ''S(n,c)'' ainsi :
  * ''n'' est le niveau de détails souhaité,
  * ''c'' est la taille du côté

{{ :nsi:terminales:recursivite:sierpinski.png?direct |}}


La construction nous indique que :
  * pour ''n = 0'' on a un simple triangle plein
  * pour ''n = 1'', ''S(1, c)'' est constitué de 3 triangles inférieurs : ''S(0, c/2)''
  * pour ''n = 2'', ''S(2, c)'' est constitué de 3 triangles inférieurs : ''S(1, c/2)''
  * on comprend que pour ''n > 1'', ''S(n,c)'' est constitué de 3 figures ''S(n-1, c/2)''.

On peut faire le tracer en utilisant le module ''turtle'' :

<code python linenums:1>
from turtle import *
speed(100)
pensize(1)    # taille du tracé
setheading(0) # orientation vers l'est

# votre programme ici


# fin du programme
exitonclick()
</code>

Quelques commandes dans ce [[nsi:tds:tortue|TD]]. Vous pouvez aussi utiliser la [[https://docs.python.org/fr/3/library/turtle.html|documentation du module turtle]].

<WRAP box>Écrivez la fonction ''S(n,c)'' faisant le tracé du triangle de Sierpinski. Faites l'essai par exemple avec ''S(5,200)''.</WRAP>

<WRAP tip>Sur le même principe, [[https://fr.wikipedia.org/wiki/Flocon_de_Koch|flocon de Koch]]</WRAP>

===== Tours de Hanoï =====

Dans [[:nsi:tds:hanoi|ce TD]], on vous décrit le problème des tours de Hanoï.

Un solution très simple de ce problème passe par une fonction récursive.

On veut déplacer une pile de N cylindres de la position A à la position B. Pour cela, il faut :
  * déplacer N-1 cylindres de A à C,
  * déplacer le cylindre N de A à B,
  * déplacer N-1 cylindres de C à B,

<WRAP box>Implémentez cette solution.</WRAP>

===== Mesures d'un arbre =====

Dans cet [[nsi:sujets:21-nsij2me2:exercice_3|exercice]] nous avons vu des exemples de fonctions récursives permettant de calculer la hauteur ou la taille d'un arbre.

<WRAP tip>Une liste chaînée peut être vue comme un arbre spécial -- un nœud n'a qu'un enfant -- et on pourrait donc appliquer la même méthode pour obtenir la longueur d'une liste.</WRAP>

===== Sac à dos =====

==== Rappel ====

Ce problème a été vu en première dans le cadre de l'[[nsi:premiere:glouton:glouton|algorithme glouton]]. Rappelons-en le principe.
  * On dispose d'un sac de capacité C,
  * d'un assortiment d'objets ayant tous un poids et une valeur.
  * On cherche à placer des objets dans le sac en respectant la contrainte de capacité et en maximisant la valeur totale du contenu du sac.

**Exemple :** On dispose d'un sac d'une capacité de C = 15 kg et de la liste d'objets suivants :

^ nom   ^ Valeur ^ Poids ^
| A     | 80     | 8     |
| B     | 32     | 2     |
| C     | 20     | 5     |
| D     | 126    | 14    |
| E     | 5      | 1     |
| F     | 18     | 6     |

Quel objet doit-on prendre pour maximiser la valeur contenue dans le sac ?

==== Solution récursive ====

Supposons que j'écrive une fonction ''meilleur_sac(C, objets)'' où ''objets'' est le tableau précédent. Pour résumer, on pourra noter ''[ABCDEF]'' le tableau complet et ''[CDEF]'' le même tableau duquel on 
aurait enlevé les lignes A et B.

Supposons que je calcule ''meilleur_sac(15, [ABCDEF])''. Voici le raisonnement récursif que l'on va tenir :
  * Soit on ne prend pas A. Dans ce cas le meilleur sac possible est obtenu avec ''meilleur_sac(15, [BCDEF])''.
  * Soit on prend A. Dans ce cas, on occupe 8 kg de la capacité du sac. Il reste 7 kg de capacité. On peut se demander comment occuper au mieux ces 7 kg en demandant ''meilleur_sac(7, [BCDEF])''.
  * Les deux options précédentes nous donne 2 choix de sac. Il faut sélectionner le meilleur des deux.

<WRAP box>Implémentez la fonction ''meilleur_sac'' et donnez la solution du problème.</WRAP>

<code lang-none>
FONCTION meilleur_sac
ENTRÉES:
   c : capacité restante
   items: liste des items que l'on peut choisir
SORTIE: le sac formé d'un choix dans la liste items,
   qui forme le meilleur sac possible avec la capacité c
DÉBUT
   SI items vide ou c < = 0 ALORS
       dans ce cas, on ne peut rien mettre dans le sac donc
       RENVOYER sac vide
   FIN SI
   soit A le premier item parmi les items à choisir
   (A existe forcément puisque si items vide, on aurait déjà fini)
   soient items_sans_A la liste des items dont on a ôté A
   
   on forme un premier essai de sac, appelé sac1. Dans ce sac on place A
   il reste donc c - poids(A) de capacité que l'on peut remplir avec items_sans_A
   en résumé, sac1 = A + meilleur_sac(c - poids(A), items_sans_A)
   à noter : il se pourrait que ce sac ne soit pas valide. En effet, il se peut
   que poids(A) > c.
   
   on forme un autre sac, sac2, qui ne contient pas A. On dispose donc de la totalité
   de la capacité pour former un sac au mieux avec les autres items.
   donc sac2 = meilleur_sac(c, items_sans_A)
   à noter : ce sac est forcément valide.
   
   maintenant il faut choisir le meilleur sac entre sac1 et sac2 :
   SI le sac1 est valide et qu'il a une valeur plus grande que sac2 ALORS
       RENVOYER sac1
   SINON
       RENVOYER sac2
   FIN
FIN
</code>




<WRAP tip>Cette façon de faire est élégante. Le code est simple, facile à écrire et à comprendre. On a par contre un peu de mal à savoir si cela occasionnera beaucoup de calculs. Il se pourrait que l'on fasse plusieurs fois les mêmes calculs et que l'on perde du temps. Cet aspect est abordé avec la [[nsi:terminales:dynamique:programmation_dynamique|programmation dynamique]].</WRAP>