Exercice Java Corrigé – Méthodes Récursives

public class Main {

  public static int calculerFactorielle(int n) {
    // Cas de base: la factorielle de 0 est égale à 1
    if (n == 0) {
      return 1;
    }

    // Cas récursif: multiplier n par la factorielle de (n-1)
    return n * calculerFactorielle(n - 1);
  }

  public static void main(String[] args) {
    int n = 3;
    int f = calculerFactorielle(n);
    System.out.println("Factorielle de "+ n +" est: "+ f);
  }
}

Sortie:

Factorielle de 3 est: 6

Explication:

La méthode calculerFactorielle() respecte la définition récursive de la factorielle. Elle comporte deux cas:

• Cas de base: Si n est égal à 0, elle renvoie 1. Il s’agit de la condition de terminaison de la récursivité.
• Cas récursif: Pour tout n positif, il multiplie n par la factorielle de n-1. Cette étape est répétée récursivement jusqu’à ce que n atteigne 0.

public class Main {

  public static int calculerSomme(int n) {
    // Cas de base: la somme de 0 est 0
    if (n == 0) {
      return 0;
    }

    // Cas récursif: ajouter n à la somme de (n-1)
    return n + calculerSomme(n - 1);
  }

  public static void main(String[] args) {
    int n = 8;
    int s = calculerSomme(n);
    System.out.println("Somme des nombres de 1 à "+ n +" est: "+ s);
  }
}

Sortie:

Somme des nombres de 1 à 8 est: 36

Explication:

La méthode calculerSomme() respecte la définition récursive de la somme. Elle comporte deux cas:

• Cas de base: Si l’entrée n est 0, la méthode renvoie 0. Il s’agit de la condition de terminaison de la récursivité.
• Cas récursif: Pour tout n positif, il ajoute n à la somme des nombres de 1 à n-1. Cette étape est répétée de manière récursive jusqu’à ce que n atteigne 0.

public class Main {

  public static int calculerFibonacci(int n) {
    // Cas de base: Les nombres de Fibonacci aux positions 0 et 1 
    // sont respectivement 0 et 1.
    if (n == 0) {
      return 0;
    } else if (n == 1) {
      return 1;
    }

    // Cas récursif: somme des deux nombres de Fibonacci précédents
    return calculerFibonacci(n - 1) + calculerFibonacci(n - 2);
  }

  public static void main(String[] args) {
    int p = 10;
    int f = calculerFibonacci(p);
    System.out.println("Le nombre de Fibonacci à la position "+ p +" est: "+ f);
  }
}

Sortie:

Le nombre de Fibonacci à la position 10 est: 55

Explication:

La méthode « calculerFibonacci() » respecte la définition récursive de la suite de Fibonacci. Elle comporte deux cas:

• cas 1: si n est 0, elle renvoie 0.
• cas 2: si n est égal à 1, elle renvoie 1.

Ce sont les conditions de terminaison de la récursivité.

Pour tout n positif supérieur à 1, la méthode calcule récursivement le nombre de Fibonacci en additionnant les deux nombres de Fibonacci précédents (calculés à l’aide de la même méthode). Ce processus est répété jusqu’à ce que n atteigne l’un des cas de base.

public class Main {

  public static boolean isPalindrome(String str) {
    // Cas de base: une chaîne vide ou une chaîne avec un seul 
    // caractère est un palindrome
    if (str.length() <= 1) {
      return true;
    }

    // Cas récursif: vérifier si le premier et le dernier caractère 
    // sont égaux, et vérifier récursivement si la sous-chaîne qui 
    // les sépare est un palindrome
    char premChar = str.charAt(0);
    char dernChar = str.charAt(str.length() - 1);

    if (premChar != dernChar) {
      return false;
    }

    String reste = str.substring(1, str.length() - 1);
    return isPalindrome(reste);
  }

  public static void main(String[] args) {
    String str = "madam";
    boolean res = isPalindrome(str);
    System.out.println(str +" est un palindrome: "+ res);
  }
}

Sortie:

madam est un palindrome: true

Explication:

La méthode isPalindrome() a deux cas possibles:

• Cas de base: Si la longueur de la chaîne est de 0 ou 1, elle renvoie true car une chaîne vide ou une chaîne avec un seul caractère est considérée comme un palindrome.
• Cas récursif: Il compare le premier et le dernier caractère de la chaîne de caractères. S'ils ne sont pas égaux, il renvoie false. Sinon, il extrait la sous-chaîne restante entre le premier et le dernier caractère, et vérifie récursivement si cette sous-chaîne est un palindrome. Ce processus jusqu'à ce que la chaîne soit réduite à une chaîne vide ou à un caractère.

public class Main {

  public static double calculerExp(double base, int e) {
    // Cas de base: tout nombre à la puissance 0 est égal à 1
    if (e == 0) {
      return 1;
    }

    // Cas récursif: multiplier la base avec l'exponentiation de 
    // (base, exposant-1)
    return base * calculerExp(base, e - 1);
  }

  public static void main(String[] args) {
    double base = 2;
    int e = 4;
    double res = calculerExp(base, e);
    System.out.println(base+" à la puissance de "+e+" est: "+res);
  }
}

Sortie:

2.0 à la puissance de 4 est: 16.0

Explication:

La méthode « calculerExp() » respecte la définition récursive de l'exponentiation. Elle comporte deux cas :

• Cas de base: Si l'exposant est 0, la méthode renvoie 1. En effet, tout nombre à la puissance 0 est égal à 1.
• Cas récursif: Pour tout exposant positif « exponent », il multiplie la base avec l'exponentiation de la même base à la puissance de l'exposant-1. Ce processus est répété récursivement jusqu'à ce que l'exposant atteigne 0.

public class Main {

  public static String reverseStr(String str) {
    // Cas de base: si la chaîne est vide ou ne comporte qu'un seul 
    // caractère, celle-ci est automatiquement inversée.
    if (str.isEmpty() || str.length() == 1) {
      return str;
    }

    // Cas récursif: inverser la sous-chaîne à partir du deuxième 
    // caractère et concaténer le premier caractère
    return reverseStr(str.substring(1)) + str.charAt(0);
  }

  public static void main(String[] args) {
    String str = "Hello, World!";
    String res = reverseStr(str);
    System.out.println("Chaîne originale: "+ str);
    System.out.println("Chaîne inversée: "+ res);
  }
}

Sortie:

Chaîne originale: Hello, World!
Chaîne inversée: !dlroW ,olleH

Explication:

La méthode reverseStr() peut être utilisée dans deux cas:

• Cas de base: Si la chaîne est vide ou ne contient qu'un seul caractère, elle est déjà inversée et nous renvoyons donc la chaîne originale.
• Cas récursif: Pour toute chaîne de longueur supérieure à 1, nous inversons récursivement la sous-chaîne en commençant par le deuxième caractère et en concaténant le premier caractère à la fin. Ce processus se poursuit jusqu'à ce que la chaîne soit réduite à une chaîne vide ou à un seul caractère.

public class Main {

  public static int calculerPGCD(int n1, int n2) {
    // Cas de base: si le deuxième nombre est 0, le PGCD est le 
    // premier nombre.
    if (n2 == 0) {
      return n1;
    }

    // Cas récursif: calculer le PGCD en appelant récursivement la 
    // méthode avec n2 comme nouveau n1 et le reste comme n2.
    int reste = n1 % n2;
    return calculerPGCD(n2, reste);
  }

  public static void main(String[] args) {
    int n1 = 20;
    int n2 = 24;
    int pgcd = calculerPGCD(n1, n2);
    System.out.println("Le PGCD de "+n1+" et "+n2+" est: "+ pgcd);
  }
}

Sortie:

Le PGCD de 20 et 24 est: 4

Explication:

La méthode calculerPGCD() suit la définition récursive du PGCD. Elle comporte deux cas :

• Cas de base: Si le deuxième nombre (n2) est 0, le PGCD est le premier nombre (n1). En effet, tout nombre divisé par 0 est le nombre lui-même.
• Cas récursif: Pour deux nombres quelconques (n1 et n2), nous calculons le reste lorsque n1 est divisé par n2. Nous appelons ensuite récursivement la méthode avec n2 comme nouveau n1 et le reste comme n2. Ce processus se poursuit jusqu'à ce que n2 atteigne 0.

public class Main {

  public static <T> int countOccurrences(T[] tab, T target) {
    return countOccurrences(tab, target, 0);
  }

  private static <T> int countOccurrences(T[] tab, T target, int index) {
    // Cas de base: si l'index atteint la fin du tableau, renvoyer 0
    if (index == tab.length) {
      return 0;
    }

    // Cas récursif: vérifier si l'élément à l'index actuel est égal 
    // au target, et appeler récursivement la méthode avec l'index 
    // suivant et ajouter 1 s'il est égal
    int count = countOccurrences(tab, target, index + 1);
    if (tab[index].equals(target)) {
      count++;
    }

    return count;
  }

  public static void main(String[] args) {
    Integer[] nbrs = {1, 2, 2, 3, 2, 4, 3, 5};
    int target = 2;
    int res = countOccurrences(nbrs, target);
    System.out.println("Le nombre d'occurrences de "+ target +" dans le tableau est: "+ res);
  }
}

Sortie:

Le nombre d'occurrences de 2 dans le tableau est: 3

Explication:

La méthode countOccurrences() comporte deux cas :

• Cas de base: Si l'index atteint la fin du tableau (index == arr.length), nous renvoyons 0 car il n'y a plus d'éléments à vérifier.
• Cas récursif: Pour tout indice situé dans les limites du tableau, nous vérifions si l'élément situé à cet indice est égal au target. Nous appelons alors récursivement la méthode avec l'index suivant et ajoutons 1 au compteur si l'élément est égal au target. Ce processus se poursuit jusqu'à ce que nous atteignions la fin du tableau.

public class Main {

  public static int calculerSommeNbrImpaire(int[] tab) {
    return calculerSommeNbrImpaire(tab, 0);
  }

  private static int calculerSommeNbrImpaire(int[] tab, int index) {
    // Cas de base: si l'index atteint la fin du tableau, renvoyer 0
    if (index == tab.length) {
      return 0;
    }

    // Cas récursif: vérifier si l'élément à l'index actuel est 
    // impair, et appeler récursivement la méthode avec l'index 
    // suivant et ajouter l'élément actuel s'il est impair
    int sum = calculerSommeNbrImpaire(tab, index + 1);
    if (tab[index] % 2 != 0) {
      sum += tab[index];
    }

    return sum;
  }

  public static void main(String[] args) {
    int[] nbrs = {1, 2, 3, 4, 5, 6};
    int sum = calculerSommeNbrImpaire(nbrs);
    System.out.println("La somme de tous les nombres impairs dans le tableau est: "+sum);
  }
}

Sortie:

La somme de tous les nombres impairs dans le tableau est: 9

Explication:

La méthode calculerSommeNbrImpaire() comporte deux cas:

• Cas de base: Si l'index atteint la fin du tableau (index == tab.length), nous renvoyons 0 car il n'y a plus d'éléments à vérifier.
• Cas récursif: Pour tout indice situé dans les limites du tableau, nous vérifions si l'élément situé à cet indice est impair. Nous appelons alors récursivement la méthode avec l'index suivant et ajoutons l'élément courant à la somme s'il est impair. Ce processus se poursuit jusqu'à ce que nous atteignions la fin du tableau.

public class Main {

  public static int calculateLengthStr(String str) {
    // Cas de base: si la chaîne est vide, la longueur est de 0
    if (str.isEmpty()) {
      return 0;
    }

    // Cas récursif: supprimer le premier caractère de la 
    // chaîne et appeler récursivement la méthode
    // avec la sous-chaîne restante, et ajouter 1 à la longueur
    return 1 + calculateLengthStr(str.substring(1));
  }

  public static void main(String[] args) {
    String str = "Hello World!";
    int length = calculateLengthStr(str);
    System.out.println("La longueur de la chaîne \""+ str +"\" est: "+ length);
  }
}

Sortie:

La longueur de la chaîne "Hello World!" est: 12

Explication:

La méthode calculateLengthStr() peut être utilisée dans deux cas:

• Cas de base: Si la chaîne est vide (str.isEmpty()), nous renvoyons 0 car la longueur d'une chaîne vide est de 0.
• Cas récursif: Pour toute chaîne non vide, nous supprimons le premier caractère en utilisant str.substring(1) et appelons récursivement la méthode avec la sous-chaîne restante. Nous ajoutons ensuite 1 à la longueur calculée lors de l'appel récursif. Ce processus se poursuit jusqu'à ce que la chaîne soit réduite à une chaîne vide.

import java.util.Arrays;

public class Main {
  public static int findMax(int[] tab) {
    return findMax(tab, 0, tab.length - 1);
  }

  private static int findMax(int[] tab, int left, int right) {
    // Cas de base: si les index de gauche et de droite sont égaux, 
    // nous avons un seul élément et nous le renvoyons en tant que 
    // maximum.
    if (left == right) {
      return tab[left];
    }

    // Cas récursif: diviser le tableau en deux moitiés, trouver 
    // récursivement le maximum dans chaque moitié, et renvoyer 
    // le plus grand des deux maximums. 
    int mid = (left + right) / 2;
    int maxLeft = findMax(tab, left, mid);
    int maxRight = findMax(tab, mid + 1, right);

    return Math.max(maxLeft, maxRight);
  }

  public static void main(String[] args) {
    int[] nbrs = {1, 5, 8, 2, 9, 3};
    System.out.println("Tableau original: "+ Arrays.toString(nbrs));
    int max = findMax(nbrs);
    System.out.println("L'élément maximum du tableau est: "+ max);
  }
}

Sortie:

Tableau original: [1, 5, 8, 2, 9, 3]
L'élément maximum du tableau est: 9

Explication:

La méthode findMax() peut être utilisée dans deux cas :

• Cas de base: Si les index de gauche et de droite sont égaux, nous avons un seul élément et nous le renvoyons en tant qu'élément maximal.
• Cas récursif: Pour tout tableau comportant plus d'un élément, nous divisons le tableau en deux moitiés en trouvant l'index du milieu. Nous trouvons ensuite de manière récursive l'élément maximal dans chaque moitié en appelant la méthode avec les index appropriés. Enfin, nous renvoyons la valeur la plus élevée des deux maximums obtenus par les appels récursifs.

public class Main {

  public static int calculerProduit(int[] tab) {
    return calculerProduit(tab, 0, tab.length - 1);
  }

  private static int calculerProduit(int[] tab, int left, int right) {
    // Cas de base: si les indices de gauche et de droite sont égaux, 
    // renvoie l'élément unique en tant que produit
    if (left == right) {
      return tab[left];
    }

    // Cas récursif : diviser le tableau en deux moitiés, 
    // récursivement calculer le produit dans chaque moitié, et
    // renvoyer le produit des deux produits calculés
    int mid = (left + right) / 2;
    int prodLeft = calculerProduit(tab, left, mid);
    int prodRight = calculerProduit(tab, mid + 1, right);

    return prodLeft * prodRight;
  }

  public static void main(String[] args) {
    int[] tab = {1, 2, 3};
    int res = calculerProduit(tab);
    System.out.println("Le produit de tous les nombres du tableau est: "+ res);
  }
}

Sortie:

Le produit de tous les nombres du tableau est: 6

Explication:

La méthode calculerProduit() comporte deux cas:

• Cas de base: Si les indices de gauche et de droite sont égaux, nous avons un seul élément et nous le renvoyons en tant que produit.
• Cas récursif: Pour tout tableau comportant plus d'un élément, nous divisons le tableau en deux moitiés en trouvant l'index du milieu. Nous calculons ensuite récursivement le produit dans chaque moitié en appelant la méthode avec les index appropriés. Enfin, nous renvoyons le produit des deux produits calculés à partir des appels récursifs.

public class Main {

  public static int calculerSommeChiffre(int n) {
    // Cas de base: si le nombre est un seul chiffre, le nombre lui-
    // même est renvoyé.
    if (n < 10) {
      return n;
    }

    // Cas récursif: calculer la somme du dernier chiffre et la somme 
    // des chiffres du nombre restant
    int lastChiffr = n % 10;
    int reste = n / 10;

    return lastChiffr + calculerSommeChiffre(reste);
  }

  public static void main(String[] args) {
    int n = 123;
    int res = calculerSommeChiffre(n);
    System.out.println("La somme des chiffres de "+n+" est: "+ res);
  }
}

Sortie:

La somme des chiffres de 123 est: 6

Explication:

La méthode calculerSommeChiffre() comporte deux cas :

• Cas de base: Si le nombre est un chiffre unique (inférieur à 10), nous renvoyons le nombre lui-même en tant que somme de ses chiffres.
• Cas récursif: Pour tout nombre comportant plus d'un chiffre, nous calculons le dernier chiffre en prenant le nombre modulo 10. Nous calculons ensuite la somme du dernier chiffre et la somme des chiffres du nombre restant obtenu en divisant le nombre par 10. Ce processus se poursuit jusqu'à ce que le nombre soit réduit à un seul chiffre.

import java.util.Arrays;

public class Main {
  public static boolean isSorted(int[] tab) {
    return isSorted(tab, 0);
  }

  private static boolean isSorted(int[] tab, int index) {
    // Cas de base : si l'index atteint la fin du tableau, 
    // le tableau est trié, 
    if (index == tab.length - 1) {
      return true;
    }

    // Cas récursif: vérifier si l'élément à l'index actuel est plus 
    // grand que l'élément suivant, et appeler récursivement la 
    // méthode avec l'index suivant.
    if (tab[index] > tab[index + 1]) {
      return false;
    }

    return isSorted(tab, index + 1);
  }

  public static void main(String[] args) {
    int[] tab = {1, 2, 3, 4, 5};
    System.out.println("Tableau original: " + Arrays.toString(tab));
    boolean res = isSorted(tab);
    System.out.println("Tab est-il trié par ordre croissant? "+res);
  }
}

Sortie:

Tableau original: [1, 2, 3, 4, 5]
Tab est-il trié par ordre croissant? true

Explication:

La méthode isSorted() peut être utilisée dans deux cas:

• Cas de base: Si l'index atteint la fin du tableau (index == tab.length - 1), nous avons parcouru tout le tableau et retournons true pour indiquer que le tableau est trié.
• Cas récursif: Pour tout index situé dans les limites du tableau, nous vérifions si l'élément à cet index est plus grand que l'élément suivant. Si c'est le cas, nous renvoyons false pour indiquer que le tableau n'est pas trié. Sinon, nous appelons récursivement la méthode avec l'index suivant.