Corrigé 7

Prérequis

1.	Une méthode récursive est une méthode qui s’appelle elle-même. Ce mécanisme est utilisé pour programmer les algorithmes qui nécessitent de conserver un ensemble de valeurs à chaque étape du calcul. La récursivité est une généralisation de la boucle.
2.	La condition d’arrêt est réalisée au sein d’une méthode récursive pour éviter qu’elle s’appelle elle-même de façon illimitée. La condition d’arrêt de la récursivité correspond à la condition d’arrêt d’une boucle.
3.	La récursivité croisée se produit quand deux ou plusieurs méthodes s’appellent mutuellement.

Corrigé 7.1 : La factorielle (écriture récursive)

La fonction factorielle est écrite sous la forme récursive. La condition d’arrêt se produit lorsque n vaut zéro. Dans le cas où n est positif, la formule de calcul par récursivité de la factorielle est appliquée.

La solution en Java se présente de la façon suivante.

import java.util.Scanner; 
 
public class Factorielle { 
 
    public static long fact(int n) { 
        if (n == 0) 
            return 1; 
        else 
            return n * fact(n - 1); 
    } 
 
    public static void main(String[] args) { 
        Scanner reader = new Scanner(System.in); 
        System.out.print("Entrez n : "); 
        int n = reader.nextInt(); 
        System.out.println(n + "! = " + fact(n)); 
    } 
}

La solution Python définissant la fonction factorielle et l’utilisant dans un programme principal conduit au code qui suit.

def fact(n: int) -> int: 
    if n == 0: 
        return 1 
    else: 
       ...

Corrigé 7.2 : Le PGCD (écriture récursive)

La fonction est très simple à écrire de façon récursive. Son écriture se base sur les explications données dans l’exercice 1.13, à savoir que PGCD(a,0) = a et que PGCD(a,b) = PGCD (b, a mod b).

La solution en Java se présente comme suit :

import java.util.Scanner; 
 
public class CalculPGCDRecursif { 
 
    public static int pgcd(int a, int b) { 
        if (b > 0) 
            return pgcd(b, a % b); 
        else 
            return a; 
    } 
 
    public static void main(String[] args) { 
        int a, b; 
        Scanner reader = new Scanner(System.in); 
        System.out.print("Entrez le premier nombre entier strictement  
positif : "); 
        a = reader.nextInt(); 
        System.out.print("Entrez le second nombre entier strictement  
positif : "); 
        b = reader.nextInt(); 
        System.out.println("Le PGCD vaut : " + pgcd(a, b)); 
    } 
}

Voici la solution en Python...

Corrigé 7.3 : L’additionneur/multiplicateur

Dans cet exercice, la récursivité est utilisée pour transmettre au fur et à mesure les différentes valeurs lues au clavier jusqu’à ce que l’utilisateur saisisse un opérateur. Quand cette saisie se produit, la variable operateur est initialisée et la dernière valeur lue est renvoyée.

Au retour de l’appel récursif, le résultat de cet appel est multiplié ou additionné avec la dernière valeur lue qui avait été transmise à ce moment. Le calcul est donc fait en remontant jusqu’à la première valeur qui avait été lue dans le programme principal.

Voici le code de la solution en Java.

import java.util.Scanner; 
 
public class AdditionneurMultiplicateur { 
    static Scanner reader = new Scanner(System.in); 
    static String operateur; 
 
    public static int addMult(int dernValeur) { 
        System.out.print("Entrez un nombre ou '*' ou '+' : "); 
        String ligne = reader.next(); 
        if ((ligne.equals("*")) || (ligne.equals("+"))) { 
            operateur = ligne; 
           ...

Corrigé 7.4 : Le tri par sélection (écriture récursive)

La fonction récursive de tri par sélection est écrite ci-après pour Java et Python. La condition d’arrêt se produit lorsque la prochaine position à trier est égale à la taille du tableau, ce qui signifie que le tableau a été entièrement trié. Dans le cas où la condition d’arrêt n’est pas vérifiée, la fonction échange la valeur à la position avec la plus petite valeur située à la suite de la position. Puis elle s’appelle récursivement pour continuer ce mécanisme à la position suivante.

En Java, l’écriture de la fonction et un programme qui l’utilise donne lieu au code suivant.

public class TriSelectionRecursif { 
 
    public static void triSelection(int[] tableau,  
int position){ 
        if (position >= tableau.length) 
            return; // le tableau est trié 
        int indiceValeurMin = position; 
        // recherche de la plus petite valeur 
        for (int j = position + 1; j < tableau.length; j++) 
            if (tableau[j] < tableau[indiceValeurMin]) 
 ...

Corrigé 7.5 : La classe Expression

Le programme de test de la classe Expression écrit en Java est présenté ci-dessous :

public class TestExpression { 
 
    public static void main(String[] args) { 
        Expression expression = new Expression(); 
        System.out.println("Résultat : " +  
expression.evalue()); 
    } 
}

En Python, le programme principal créant un objet de la classe Expression et invoquant sa méthode d’évaluation devient comme suit :

def main() -> None: 
    expression: Expression = Expression() 
    print(f"Résultat : {expression.evalue()}") 
 
if __name__ == "__main__": 
    main()

Pour pouvoir traiter les parenthèses, il faut modifier la méthode valeur de la classe Expression. Au lieu de ne lire que des nombres entiers, elle autorise aussi l’utilisateur à saisir une parenthèse ouvrante et traite ce cas en appelant récursivement la méthode add pour traiter le contenu de la parenthèse. Au retour de cet appel, la fonction vérifie la présence d’une parenthèse fermante qui a été lue lors de l’appel de la fonction add (ce qui explique la modification des instructions print de la fonction mult qui avait été faite dans l’énoncé).

La classe Expression2 avec la modification de la méthode valeur est décrite ci-après en Java.

import java.util.Scanner; 
 
public class Expression2 { 
    Scanner reader = new Scanner(System.in); 
    String token; ...

Corrigé 7.6 : Le comptage des fichiers et des répertoires

Dans la classe Repertoire, chaque méthode de comptage s’appelle récursivement pour chaque nœud du répertoire. La méthode comptant les fichiers additionne tous les fichiers contenus dans chaque nœud du répertoire. La méthode comptant les répertoires additionne tous les répertoires contenus dans chaque nœud du répertoire.

La classe Repertoire écrite en Java est présentée à la suite.

public class Repertoire implements Noeud { 
    final int nbrMaxNoeuds = 10; 
    Noeud[] noeuds = new Noeud[nbrMaxNoeuds]; 
    int nbrNoeuds = 0; 
 
    public long nombreFichiers() { 
        int resultat = 0; 
        for (int i = 0; i < nbrNoeuds; i++) 
            resultat += noeuds[i].nombreFichiers(); 
        return resultat; 
    } 
 
    public long nombreRepertoires() { 
        int resultat = 1; // y compris le répertoire lui-même 
        for (int i = 0; i < nbrNoeuds; i++) 
            resultat += noeuds[i].nombreRepertoires(); 
        return resultat; ...