Récursions sur les chaînes
Exercice · informatique (tronc commun des prépas scientifiques), chapitre 6 — Fonctions récursives
Énoncé
Écrire en récursif les fonctions renverse(s) (miroir d'une chaîne) et est_palindrome(s), en identifiant le cas de base, le variant et les grandes lignes de la preuve.
Corrigé
def renverse(s: str) -> str:
if len(s) <= 1:
return s
return renverse(s[1:]) + s[0]
def est_palindrome(s: str) -> bool:
if len(s) <= 1:
return True
return s[0] == s[-1] and est_palindrome(s[1:-1])Le variant commun est len(s), qui décroît à chaque appel récursif. La correction se prouve par récurrence sur la longueur de la chaîne. Pour est_palindrome, le comportement de and en court-circuit interrompt la récursion dès qu'une différence est constatée entre le premier et le dernier caractère, ce qui est optimal.
Les autres exercices de ce chapitre Le cours du chapitre
Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.