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 :
- le cas de base,
- comment traiter le cas de base,
- 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, comme les tuples en Python, vous ne pouvez pas modifier leur contenusupposons que
s = "hello"
alorss[:2]
renvoie"he"
,s[1]
renvoie"e"
ets[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 Θ(1) car on n'a qu'un nombre constant de caractères (ici les2
premiers) à recopier, quelle que soit la longueur totale n de la chaînes
. - accéder à
s[2:]
s'exécute en O(n) car on doit recopier n−2 caractères de la chaînes
, donc tous sauf les2
premiers.
- accéder à