Fibonacci : Résolution récursive en Java
La suite de Fibonacci est une séquence mathématique où chaque nombre est la somme des deux nombres précédents. En programmation, il existe plusieurs façons de calculer la suite de Fibonacci. Dans cet article, nous allons nous concentrer sur une approche récursive pour résoudre ce problème en Java.
Comprendre la récursivité
La récursivité est un concept en programmation où une fonction se rappelle elle-même pour résoudre un problème plus petit. Pour résoudre la suite de Fibonacci de manière récursive, nous devons diviser le problème en sous-problèmes plus petits et résoudre ces sous-problèmes jusqu’à atteindre le cas de base.
Algorithme récursif de Fibonacci
Voici l’algorithme récursif pour calculer le n-ème nombre de Fibonacci :
- Si n est égal à 0, retourner 0.
- Si n est égal à 1, retourner 1.
- Sinon, retourner la somme des deux nombres de Fibonacci précédents.
Voici une implémentation de cet algorithme en Java :
public class Fibonacci {
public static int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
public static void main(String[] args) {
int n = 10; // Exemple : Trouver le 10e nombre de Fibonacci
System.out.println("Le " + n + "e nombre de Fibonacci est : " + fibonacci(n));
}
}Dans cet exemple, la méthode fibonacci() prend un entier n en entrée et retourne le n-ème nombre de Fibonacci. Si n est inférieur ou égal à 1, la méthode retourne simplement n. Sinon, elle appelle récursivement la méthode fibonacci() pour n-1 et n-2, puis retourne la somme des résultats.
Exemple d’utilisation
Supposons que nous voulions trouver le 10e nombre de Fibonacci. En exécutant le programme Java, nous obtiendrons :
Le 10e nombre de Fibonacci est : 55Synthèse 😉
La résolution récursive de la suite de Fibonacci en Java est une approche simple et élégante pour ce problème classique en informatique. Cependant, cette méthode peut devenir inefficace pour des valeurs de n élevées en raison de la répétition des calculs. Dans de tels cas, d’autres techniques comme la programmation dynamique peuvent être utilisées pour améliorer les performances.
Voici une série d’exercices corrigés sur le thème de la récursivité en Java :
Exercice 1 : Calcul de la Factorielle
Écrivez une méthode récursive pour calculer la factorielle d’un nombre.
public class Factorielle {
public static int calculFactorielle(int n) {
if (n == 0) {
return 1;
} else {
return n * calculFactorielle(n - 1);
}
}
public static void main(String[] args) {
int n = 5;
System.out.println("Factorielle de " + n + " : " + calculFactorielle(n));
}
}Exercice 2 : Calcul de la Somme des Chiffres
Écrivez une méthode récursive pour calculer la somme des chiffres d’un nombre.
public class SommeDesChiffres {
public static int sommeChiffres(int n) {
if (n == 0) {
return 0;
} else {
return n % 10 + sommeChiffres(n / 10);
}
}
public static void main(String[] args) {
int n = 12345;
System.out.println("Somme des chiffres de " + n + " : " + sommeChiffres(n));
}
}Exercice 3 : Vérification de Palindrome
Écrivez une méthode récursive pour vérifier si une chaîne de caractères est un palindrome.
public class Palindrome {
public static boolean estPalindrome(String str) {
if (str.length() <= 1) {
return true;
} else if (str.charAt(0) != str.charAt(str.length() - 1)) {
return false;
} else {
return estPalindrome(str.substring(1, str.length() - 1));
}
}
public static void main(String[] args) {
String mot = "radar";
System.out.println(mot + " est un palindrome ? " + estPalindrome(mot));
}
}Exercice 4 : Séquence de Fibonacci
Écrivez une méthode récursive pour calculer le n-ème nombre de la séquence de Fibonacci.
public class Fibonacci {
public static int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
public static void main(String[] args) {
int n = 10;
System.out.println("Le " + n + "e nombre de Fibonacci est : " + fibonacci(n));
}
}Ces exercices vous donneront une bonne pratique pour comprendre et utiliser la récursivité en Java.
Voici quelques exercices avancés sur la récursivité en Java :
Exercice 1 : Génération de Tous les Sous-Ensembles
Écrivez une méthode récursive pour générer tous les sous-ensembles d’un ensemble donné.
Exercice 2 : Trouver Tous les Chemins d’un Graphique
Écrivez une méthode récursive pour trouver tous les chemins possibles d’un sommet de départ à un sommet d’arrivée dans un graphe.
Exercice 3 : Calculer la Combinaison
Écrivez une méthode récursive pour calculer le coefficient binomial (ou combinaison) “n parmi k”.
Exercice 4 : Résolution du Problème des Tours de Hanoi
Écrivez une méthode récursive pour résoudre le problème des tours de Hanoï, qui consiste à déplacer une pile de disques d’un piquet à un autre en suivant certaines règles.
Exercice 5 : Triez une Liste Utilisant la Récursivité
Écrivez une méthode récursive pour trier une liste d’entiers en utilisant un algorithme de tri récursif, comme le tri rapide (quicksort) ou le tri fusion (merge sort).
Exercice 6 : Génération de Parenthèses Validées
Écrivez une méthode récursive pour générer toutes les combinaisons de parenthèses valides pour un nombre donné de paires de parenthèses.
Exercice 7 : Recherche d’un Mot dans une Grille de Mots Croisés
Écrivez une méthode récursive pour rechercher un mot donné dans une grille de mots croisés.
Exercice 8 : Calcul du Plus Court Chemin dans un Graphique Pondéré
Écrivez une méthode récursive pour trouver le plus court chemin d’un sommet de départ à un sommet d’arrivée dans un graphe pondéré.
Exercice 9 : Génération de Tous les Arbres Binaires Possibles
Écrivez une méthode récursive pour générer tous les arbres binaires possibles avec un nombre donné de nœuds.
Exercice 10 : Sudoku Solver
Écrivez une méthode récursive pour résoudre un puzzle Sudoku en remplissant les cases vides avec les chiffres de 1 à 9 de manière à ce que chaque ligne, chaque colonne et chaque région de 3×3 contienne tous les chiffres de 1 à 9.
Ces exercices avancés vous permettront de mettre en pratique des concepts de récursivité plus complexes et de développer vos compétences en résolution de problèmes.
Voici les solutions aux exercices avancés avec du code Java :
Exercice 1 : Génération de Tous les Sous-Ensembles
import java.util.*;
public class Subsets {
public static List<List<Integer>> generateSubsets(int[] nums) {
List<List<Integer>> subsets = new ArrayList<>();
generate(nums, 0, new ArrayList<>(), subsets);
return subsets;
}
private static void generate(int[] nums, int index, List<Integer> current, List<List<Integer>> subsets) {
subsets.add(new ArrayList<>(current));
for (int i = index; i < nums.length; i++) {
current.add(nums[i]);
generate(nums, i + 1, current, subsets);
current.remove(current.size() - 1);
}
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
List<List<Integer>> subsets = generateSubsets(nums);
for (List<Integer> subset : subsets) {
System.out.println(subset);
}
}
}Exercice 2 : Trouver Tous les Chemins d’un Graphique
import java.util.*;
public class AllPathsInGraph {
public static List<List<Integer>> allPaths(int[][] graph, int start, int end) {
List<List<Integer>> paths = new ArrayList<>();
List<Integer> currentPath = new ArrayList<>();
currentPath.add(start);
findPaths(graph, start, end, currentPath, paths);
return paths;
}
private static void findPaths(int[][] graph, int current, int end, List<Integer> currentPath, List<List<Integer>> paths) {
if (current == end) {
paths.add(new ArrayList<>(currentPath));
return;
}
for (int neighbor : graph[current]) {
currentPath.add(neighbor);
findPaths(graph, neighbor, end, currentPath, paths);
currentPath.remove(currentPath.size() - 1);
}
}
public static void main(String[] args) {
int[][] graph = {{1, 2}, {3}, {3}, {}};
int start = 0, end = 3;
List<List<Integer>> paths = allPaths(graph, start, end);
for (List<Integer> path : paths) {
System.out.println(path);
}
}
}Exercice 3 : Calculer la Combinaison
public class Combination {
public static int calculateCombination(int n, int k) {
if (k == 0 || k == n) {
return 1;
} else {
return calculateCombination(n - 1, k - 1) + calculateCombination(n - 1, k);
}
}
public static void main(String[] args) {
int n = 5, k = 2;
System.out.println("Combinaison de " + n + " parmi " + k + " : " + calculateCombination(n, k));
}
}Exercice 4 : Résolution du Problème des Tours de Hanoi
public class TowersOfHanoi {
public static void solveHanoi(int n, char source, char aux, char destination) {
if (n == 1) {
System.out.println("Déplacer le disque 1 de " + source + " à " + destination);
return;
}
solveHanoi(n - 1, source, destination, aux);
System.out.println("Déplacer le disque " + n + " de " + source + " à " + destination);
solveHanoi(n - 1, aux, source, destination);
}
public static void main(String[] args) {
int n = 3;
solveHanoi(n, 'A', 'B', 'C');
}
}Exercice 5 : Triez une Liste Utilisant la Récursivité
import java.util.*;
public class RecursiveSorting {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] arr = {5, 3, 7, 2, 8, 1, 4};
System.out.println("Avant le tri : " + Arrays.toString(arr));
quickSort(arr, 0, arr.length - 1);
System.out.println("Après le tri : " + Arrays.toString(arr));
}
}Exercice 6 : Génération de Parenthèses Validées
import java.util.*;
public class ValidParentheses {
public static List<String> generateValidParentheses(int n) {
List<String> result = new ArrayList<>();
generate(n, n, "", result);
return result;
}
private static void generate(int left, int right, String current, List<String> result) {
if (left == 0 && right == 0) {
result.add(current);
return;
}
if (left > 0) {
generate(left - 1, right, current + "(", result);
}
if (right > left) {
generate(left, right - 1, current + ")", result);
}
}
public static void main(String[] args) {
int n = 3;
List<String> validParentheses = generateValidParentheses(n);
for (String parentheses : validParentheses) {
System.out.println(parentheses);
}
}
}Exercice 7 : Recherche d’un Mot dans une Grille de Mots Croisés
public class WordSearch {
public static boolean exist(char[][] board, String word) {
int rows = board.length;
int cols = board[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (search(board, word, i, j, 0)) {
return true;
}
}
}
return false;
}
private static boolean search(char[][] board, String word, int i, int j, int index) {
if (index == word.length()) {
return true;
}
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index)) {
return false;
}
char temp = board[i][j];
board[i][j] = '#';
boolean found = search(board, word, i + 1, j, index + 1) ||
search(board, word, i - 1, j, index + 1) ||
search(board, word, i, j + 1, index + 1) ||
search(board, word, i, j - 1, index + 1);
board[i][j] = temp;
return found;
}
public static void main(String[] args) {
char[][] board = {
{'A', 'B', 'C', 'E'},
{'S', 'F', 'C', 'S'},
{'A', 'D', 'E', 'E'}
};
String word = "ABCCED";
System.out.println("Le mot existe dans la grille ? " + exist(board, word));
}
}Exercice 8 : Calcul du Plus Court Chemin dans un Graphique Pondéré
import java.util.*;
public class ShortestPath {
public static int shortestPath(int[][] graph, int start, int end) {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[graph.length];
int[] distance = new int[graph.length];
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
int current = queue.poll();
if (current == end) {
return distance[current];
}
for (int i = 0; i < graph[current].length; i++) {
if (graph[current][i] != 0 && !visited[i]) {
queue.add(i);
visited[i] = true;
distance[i] = distance[current] + graph[current][i];
}
}
}
return -1; // Pas de chemin trouvé
}
public static void main(String[] args) {
int[][] graph = {
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
int start = 0, end = 4;
System.out.println("Plus court chemin de " + start + " à " + end + " : " + shortestPath(graph, start, end));
}
}Autres articles
