Un palindrome est une séquence qui est indépendante du sens de lecture, c'est-à-dire une séquence qui est identique qu'elle soit lue de gauche à droite ou de droite à gauche. Par exemple, les mots radar et kayak sont des palindromes, le mot bonbon n'en est pas un.

Vous êtes chargés d'implémenter les fonctions is_palindrome_rec et is_palindrome étant donné les propriétés suivantes :

• Une séquence contenant aucun caractère peut être considérée comme un palindrome.
• Une séquence contenant exactement un caractère est un palindrome.
• Une séquence est un palindrome si le premier et dernier caractère sont identiques, que le deuxième et avant-dernier caractère sont identiques, ...

Vous noterez que les chaînes de caractères Python (str) peuvent être vues comme des tableaux immuables. Cela signifie :

• que vous pouvez utiliser les str comme des tableaux (list) mais que, comme les tuples en Python, vous ne pouvez pas modifier leur contenu

• supposons que s = "hello" alors s[:2] renvoie "he", s[1] renvoie "e" et s[2:] renvoie "llo"

• lorsque, comme ci-dessus, on extrait une sous-chaîne d'une chaîne s de longueur $n$, cette extraction se réalise en réalité en recopiant les caractères concernés dans une nouvelle chaîne.

  Par conséquent,

  • accéder à s[:2] s'exécute en temps constant $\Theta(1)$ car on n'a qu'un nombre constant de caractères (ici les 2 premiers) à recopier, quelle que soit la longueur totale $n$ de la chaîne s.
  • accéder à s[2:] s'exécute en $O(n)$ car on doit recopier $n - 2$ caractères de la chaîne s, donc tous sauf les 2 premiers.