Récursions sur les chaînes

Fonctions récursives · niveau 1 (application)

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

Énoncé

Corrigé

Exercices semblables