Comprendre la récursivité
La récursivité
La récursivité est un concept en programmation où une méthode s’appelle elle-même pour résoudre un problème. C’est une approche très utile pour résoudre des problèmes qui peuvent être décomposés en problèmes plus petits de la même nature.
La récursivité peut être utilisée dans de nombreux cas pour résoudre des problèmes complexes de manière élégante et concise. Elle s’impose souvent lorsqu’un problème peut être divisé en sous-problèmes plus petits et similaires, qui peuvent être résolus de manière récursive jusqu’à ce qu’un cas de base soit atteint.
Voici quelques exemples de situations où la récursivité peut être utile :
-
Structures de données récursives : La récursivité est souvent utilisée pour parcourir des structures de données récursives telles que les arbres et les graphes. Par exemple, pour parcourir un arbre binaire, on peut utiliser une fonction récursive qui visite le nœud actuel, puis appelle récursivement la fonction sur les sous-arbres gauche et droit.
-
Algorithmes de recherche et de tri : De nombreux algorithmes de recherche et de tri peuvent être implémentés de manière récursive. Par exemple, la recherche binaire utilise la récursivité pour diviser l’espace de recherche en deux à chaque étape jusqu’à ce que l’élément recherché soit trouvé ou que l’espace de recherche soit vide. De même, le tri rapide utilise la récursivité pour diviser le tableau en deux parties plus petites, trier chaque partie récursivement, puis fusionner les résultats.
-
Problèmes combinatoires : La récursivité peut également être utilisée pour résoudre des problèmes combinatoires tels que la génération de permutations, de combinaisons et de sous-ensembles. Dans ces cas, une fonction récursive peut être utilisée pour générer toutes les solutions possibles en explorant toutes les options à chaque étape.
En général, la récursivité peut être un outil puissant pour résoudre des problèmes complexes, mais il est important de l’utiliser judicieusement et de veiller à définir correctement les cas de base pour éviter les boucles infinies et les débordements de pile.
Exemple 01
Voici un exemple simple de récursivité, une fonction pour calculer le factoriel d’un nombre :
public int factoriel(int n) {
if (n == 0) {
return 1;
} else {
return n * factoriel(n - 1);
}
}
Dans cet exemple, la méthode factoriel s’appelle elle-même pour calculer le factoriel. La condition if (n == 0) est la condition d’arrêt qui empêche la récursion de continuer indéfiniment.
Il est important de toujours avoir une condition d’arrêt dans une méthode récursive, sinon elle continuera à s’appeler elle-même indéfiniment, ce qui entraînera une erreur de débordement de pile.
La récursivité peut être une technique puissante, mais elle peut aussi être plus difficile à comprendre et à déboguer que les boucles itératives. De plus, la récursivité peut être plus coûteuse en termes de performances et d’utilisation de la mémoire, car chaque appel récursif ajoute une nouvelle couche à la pile d’appels.
Exemple 02
Voici une fonction récursive simple qui encode une chaîne en décalant chaque caractère d’une position vers le haut dans l’alphabet. Cette méthode est parfois appelée “chiffrement de César” avec un décalage de 1.
public class Main {
public static void main(String[] args) {
String maChaine = "Bonjour";
String chaineEncodee = encoder(maChaine);
System.out.println(chaineEncodee); // Affiche : "Cpobokps"
}
public static String encoder(String chaine) {
if (chaine.isEmpty()) {
return chaine;
} else {
char premierCaractere = chaine.charAt(0);
char premierCaractereEncode = (char) (premierCaractere + 1);
return premierCaractereEncode + encoder(chaine.substring(1));
}
}
}
Dans cet exemple, la méthode encoder s’appelle elle-même récursivement pour encoder chaque caractère de la chaîne. La condition if (chaine.isEmpty()) est la condition d’arrêt qui empêche la récursion de continuer indéfiniment. Notez que cette méthode simple ne gère pas les cas où le décalage d’un caractère le fait sortir de l’alphabet (par exemple, décaler ‘z’ d’une position).
Exemple 03
Voici un exemple de fonction récursive complexe en Java. Cette fonction calcule les nombres de Fibonacci, qui sont une série de nombres dans laquelle chaque nombre est la somme des deux précédents. C’est une fonction récursive car elle s’appelle elle-même pour calculer les nombres de Fibonacci.
public class Main {
public static void main(String[] args) {
int n = 10;
System.out.println("Le " + n + "ème nombre de Fibonacci est : " + fibonacci(n));
}
public static int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
}
Dans cet exemple, la méthode fibonacci s’appelle elle-même récursivement pour calculer le nème nombre de Fibonacci. La condition if (n <= 1) est la condition d’arrêt qui empêche la récursion de continuer indéfiniment.
Il est important de noter que cette méthode a une complexité temporelle exponentielle, car elle effectue un grand nombre d’appels récursifs redondants. Pour des valeurs plus grandes de n, cette méthode peut être très lente. Une solution à ce problème serait d’utiliser la programmation dynamique pour stocker et réutiliser les résultats des appels récursifs précédents.
Exemple 04
Voici un exemple de fonction récursive de recherche avec un objet en Java. Cette fonction recherche une clé spécifique dans un objet JSON de manière récursive.
import org.json.JSONObject;
public class Main {
public static void main(String[] args) {
JSONObject obj = new JSONObject();
obj.put("nom", "Dupont");
obj.put("age", 30);
obj.put("ville", "Paris");
String cleRecherchee = "ville";
String resultat = chercherCle(obj, cleRecherchee);
if (resultat != null) {
System.out.println("La clé " + cleRecherchee + " a été trouvée avec la valeur: " + resultat);
} else {
System.out.println("La clé " + cleRecherchee + " n'a pas été trouvée.");
}
}
public static String chercherCle(JSONObject obj, String cleRecherchee) {
if (obj.has(cleRecherchee)) {
return obj.getString(cleRecherchee);
}
for (String cle : obj.keySet()) {
Object sousObj = obj.get(cle);
if (sousObj instanceof JSONObject) {
String resultat = chercherCle((JSONObject) sousObj, cleRecherchee);
if (resultat != null) {
return resultat;
}
}
}
return null;
}
}
Cette fonction chercherCle prend en entrée un objet JSONObject et une clé sous forme de chaîne de caractères. Elle vérifie d’abord si l’objet contient la clé recherchée. Si c’est le cas, elle renvoie la valeur associée à cette clé. Sinon, elle parcourt toutes les clés de l’objet et effectue une recherche récursive sur les sous-objets jusqu’à ce qu’elle trouve la clé recherchée ou qu’elle ait parcouru tout l’objet.
Example 05
Un exemple de méthode récursive intéressante qui n'existe pas en Java est la fonction print_r du PHP.
Si un tableau est fourni à print_r(tableau), les valeurs seront affichées dans un format permettant de lire l'intégralité du contenu du tableau.
Comme chaque tableau peut contenir de 0 à X tableaux, une méthode récursive s'impose !
// Importation de la classe Arrays pour utiliser ses utilitaires, comme deepToString
import java.util.Arrays;
// Définition de la classe principale Main
public class Main {
// Méthode principale qui sera exécutée lors de l'exécution du programme
public static void main(String[] args) {
// Définition d'un tableau d'objets. Il contient des chaînes de caractères et des tableaux imbriqués.
Object[] tableau = {
"élément 1",
new Object[]{ // Un tableau imbriqué à l'intérieur du tableau principal
"sous-élément 1",
"sous-élément 2",
new Object[]{ // Un tableau imbriqué à l'intérieur du tableau précédent
"sous-sous-élément 1",
"sous-sous-élément 2",
new Object[]{ // Encore un tableau imbriqué
"sous-sous-sous-élément 1",
"sous-sous-sous-élément 2"
}
}
},
"élément 2"
};
// Affichage du tableau à l'aide de la méthode deepToString d'Arrays, qui donne une représentation en chaîne du tableau
System.out.println(Arrays.deepToString(tableau));
// Utilisation de la méthode print_r de la classe ArrayPrinter pour afficher le tableau de manière formatée
ArrayPrinter.print_r(tableau, 0);
}
}
// Définition de la classe ArrayPrinter
public class ArrayPrinter {
// Méthode statique pour imprimer le contenu d'un tableau, avec un niveau d'indentation spécifié
public static void print_r(Object[] tableau, int indentation) {
// Si le tableau est null, la fonction retourne immédiatement sans rien faire
if (tableau == null) return;
// Pour chaque élément du tableau
for (Object o : tableau) {
// Boucle pour gérer l'indentation : pour chaque niveau d'indentation, deux espaces sont imprimés
for (int i = 0; i < indentation; i++) {
System.out.print(" "); // Imprime deux espaces pour l'indentation
}
// Si l'élément actuel est lui-même un tableau
if (o instanceof Object[]) {
System.out.println("["); // Imprime un crochet ouvrant pour indiquer le début du tableau imbriqué
// Appelle récursivement la fonction print_r pour imprimer le tableau imbriqué avec un niveau d'indentation supplémentaire
print_r((Object[]) o, indentation + 1);
// Après avoir imprimé le tableau imbriqué, on imprime l'indentation pour aligner le crochet fermant
for (int i = 0; i < indentation; i++) {
System.out.print(" "); // Imprime à nouveau les espaces pour l'indentation
}
System.out.println("]"); // Imprime un crochet fermant pour indiquer la fin du tableau imbriqué
} else {
// Si l'élément n'est pas un tableau, il est simplement imprimé
System.out.println(o);
}
}
}
}
Exercices
Créer une fonction récursive qui stocke chaque caractère d'une string dans un arraylist de char !