/** * Deux versions récursives de l'algorithme du palindrome * * La récurrence est la suivante: * Une chaîne s est un palindrome si: * - elle ne contient qu'un seul caractère (ou aucun) * - le 1er et le dernier caractères sont egaux ET * la chaîne privée du 1er et dernier caractères est un palindrome * * @author felipe * @version IFT1010 6/4/2002 */ public class Palindrome { // premiere version: application directe de la récurrence énoncée plus haut static boolean palindrome1(String s) { if (s.length() <= 1) return true; // cas de base return (s.charAt(0) == s.charAt(s.length()-1)) && (palindrome1(s.substring(1,s.length()-1))); } // une deuxième version moins couteuse en mémoire static boolean palindrome2(String s, int d, int f) { if (d >= f) return true; // cas de base return (s.charAt(d) == s.charAt(f)) && palindrome2(s,d+1,f-1); } public static void main(String [] args) { String s; if (args.length == 1) s = args[0]; else s = "laval"; System.out.println(s + " est un palindrome ? " + ((palindrome1(s))? "oui": "non")); System.out.println(s + " est un palindrome ? " + ((palindrome2(s,0,s.length()-1))? "oui": "non")); } }