Récursivité

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 Chaînes de caractères et Tableaux) 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, il peut être utile de définir la fonction récursive suivante :

  1. 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