Récursivité
===========

.. include:: common.rst.inc

Tout algorithme impliquant une répétition peut s'écrire de deux manière:
avec une boucle, ou comme une fonction récursive.

Il n'y a donc pas d'exercice spécifique dans ce chapitre,
vous pouvez reprendre tous les exercices du manuel
(notamment des chapitres `chaines`:doc: et `tableaux`:doc:)
en vous *interdisant l'usage des boucles*,
ce qui vous conduira, au besoin, à l'écrire de manière récursive.

Notez que, dans certains cas,
la fonction demandée pour un exercice ne se prête pas directement à une écriture récursive,
mais suppose l'écriture d'une *fonction intermédiaire*,
acceptant plus de paramètres que l'originale.
Par exemple, pour écrire la fonction `compte_car <compte_car>`:ref:,
il peut être utile de définir la fonction récursive suivante :

#. .. _compte_car_depuis:

   |exo| Calculer le nombre d'occurrences d'un caractère ::

    def compte_car_depuis(s: str, c: str, pos: int) -> int:
        """
        :entrée s: str
        :entrée c: str
        :entrée pos: int
        :pré-cond: len(c) == 1
        :sortie n: int
        :post-cond: n est le nombre de valeurs i >= pos telles que s[i] == c
        """

   Exemple ::

     compte_car_depuis("hello", "l", 0) # retourne 2
     compte_car_depuis("hello", "l", 2) # retourne 2
     compte_car_depuis("hello", "l", 3) # retourne 1
     compte_car_depuis("hello", "l", 4) # retourne 0
     compte_car_depuis("hello", "z", 0) # retourne 0

   .. raw:: html

      <script type="text/x-autoeval">
      [
        (("hello",'h',0), (1,)),
        (("hello",'h',1), (0,)),
        (("hello",'l',0), (2,)),
        (("hello",'l',2), (2,)),
        (("hello",'l',3), (1,)),
        (("hello",'l',4), (0,)),
        (("hello",'l',9), (0,)),
        (("hello",'H',0), (0,)),
        (("",     'a',0), (0,)),
        (("",     'a',9), (0,)),
      ]
      </script>