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)$.