Voici un algorithme qui reconnait les palindromes. En entrée, on a une liste.
def palindrome(L):
return (T[0]==T[−1]) and palindrome(L[1:−1])
La relation de récurrence sur le nombre d'opérations est : t(n)=1+t(n−2), cet algorithme est donc en O(n).