Implémentez une version récursive de l'algorithme itératif étudié dans l'exercice précédent. Votre implémentation récursive doit garder la même complexité que l'algorithme itératif.

On vous demande d'implémenter un algorithme avec récursion. Avant d'élaborer votre algorithme, détaillez :

1. le cas de base,
2. comment traiter le cas de base,
3. comment construire la solution actuelle (taille n) si je connais une solution pour un problème plus petit (par exemple de taille n-1).

Rappel du problème :

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 vous ne pouvez pas modifier leur contenu
• si s = "hello" alors s[0:2] renvoie "he" et s[2:] renvoie "llo" en \(O(1)\)
• s[i] renvoie le caractère à l'indice i du str s : s[1] renvoie e en \(O(1)\)