Mise en oeuvre de méthodes récursives

Méthodes à nombre variable de paramètres Nos premières expressions régulières

Accès rapide :
La vidéo
Qu'est-ce qu'une méthode récursive ?
Mise en oeuvre d'une méthode récursive
Itératif VS récursif
Travaux pratiques
Le sujet
La correction

La vidéo

Cette vidéo vous montre comment coder des méthodes récursives. L'exemple de la fonction factorielle est proposé. Une comparaison entre une approche itérative et une approche récursive est aussi proposée.

Qu'est-ce qu'une méthode récursive ?

Une méthode récursive est une méthode qui s'appuie sur sa propre exécution (elle s'appelle elle-même) pour calculer un résultat. Vous pouvez utiliser la récursivité pour peu que le problème auquel vous cherchez à répondre soit intrinsèquement récursif, sans quoi vous risquez d'avoir du mal à arriver à vos fins.

Nous allons considérer deux « cas d'école » dans ce chapitre. Le premier, un calcul de puissance, nous allons le réaliser ensemble. Le second, un calcul de factorielle, vous le réaliserez en travaux pratiques.

Commençons par un calcul de puissance. Mathématiquement, la puissance est une fonction récursive : parfait. Voici une définition de la puissance pour des entiers positifs.

x0 = 1
x1 = x
xn = x * xn-1

Il faut bien noter un point important : quand vous codez un algorithme récursif il faut, en premier, envisager les cas terminaux (ce qui permettra d'arrêter la récursivité). Dans le cas de la puissance, xn = x * xn-1 contient l'appel récursif et du coup à chaque rappel de la puissance (pour la value n-1) on réduit la valeur de n. Du coup on arrête la descente récursive quand n atteint 0. Il ne faut pas oublier ce cas terminal. Passons à la mise en oeuvre technique.

Mise en oeuvre d'une méthode récursive

L'exemple de code suivant, met en oeuvre, en Java, un calcul de puissance en utilisant la récursivité.

 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 

public class Demo {
    
    public static int power( int value, int pow ) {
        if ( pow == 0 ) return 1;
        return value * power( value, pow-1 );
    }
    
    public static void main(String[] args) {
        System.out.println( power( 2, 0 ) );    // Affiche 1
        System.out.println( power( 2, 1 ) );    // Affiche 2
        System.out.println( power( 2, 2 ) );    // Affiche 4
        System.out.println( power( 2, 3 ) );    // Affiche 8
        System.out.println( power( 2, 16 ) );   // Affiche 65536
    }

}

En ligne 4, nous avons le traitement du cas terminal : si pow vaut 0, on arrête la descente récursive.

En ligne 5, nous avons l'appel récursif à proprement parlé. Remarquez bien, qu'à chaque nouvel appel à la méthode power, on réduit de 1 la valeur de la puissance. Si pow est bien un entier positif, on devrait bien finir par atteindre 0 et donc terminer le calcul.

Itératif VS récursif

Pour rappel, dans un des chapitre précédent, nous avions aussi codé un calcul de puissance, mais avec une approche itérative (une boucle). Voici le code que nous avions considéré.

 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 

public class Demo {
    
    public static int power( int value, int pow ) {
        int accumulator = 1;
        
        for (int i = 0; i < pow; i++) {
            accumulator *= value;
        }
        
        return accumulator;
    }
    
    public static void main(String[] args) {
        System.out.println( power( 2, 0 ) );    // Affiche 1
        System.out.println( power( 2, 1 ) );    // Affiche 2
        System.out.println( power( 2, 2 ) );    // Affiche 4
        System.out.println( power( 2, 3 ) );    // Affiche 8
        System.out.println( power( 2, 16 ) );   // Affiche 65536
    }

}

La question, que vous êtes en droit de vous poser, est de savoir qu'elle est la meilleur approche ?

Du point de vue de la lisibilité du code, il est vrai que l'approche récursive est toujours plus expressives et donc plus lisible. Je pense que l'exemple de la puissance valide cette affirmation.

Par contre, l'approche récursive peut poser des problèmes du point de vue des performances. Effectivement, avec l'approche récursive, on produit un grand nombre d'appels de méthodes. Il faut savoir qu'un appel de méthode n'est pas complétement gratuit en termes de consommation de cycles CPU. Il faut gérer la pile d'exécution : y empiler les paramètres, y sauvegarder un contexte d'exécution et gérer la valeur de retour. Du coup, une approche itérative sera forcément plus rapide. Voici un petit exemple de code qui met en évidence ce point.

 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 

public class Demo {
    
    public static int powerRec( int value, int pow ) {
        if ( pow == 0 ) return 1;
        return value * powerRec( value, pow-1 );
    }
    
    public static int power( int value, int pow ) {
        int accumulator = 1;
        
        for (int i = 0; i < pow; i++) {
            accumulator *= value;
        }
        
        return accumulator;
    }
    
    public static void main(String[] args) {
        final int LOOP_COUNT = 1_000_000_000;
        
        // Mesure de temps pour un milliard d'appels à powerRec
        long res = 0;
        long begin = System.currentTimeMillis();
        for ( int i = 0; i < LOOP_COUNT; i++ ) {
            res += powerRec( 2, i%10 );
        }
        long end = System.currentTimeMillis();
        System.out.println( "Duration REC: " + (end-begin) + "ms - " + res );
        
        // Mesure de temps pour un milliard d'appels à power
        res = 0;
        begin = System.currentTimeMillis();
        for ( int i = 0; i < LOOP_COUNT; i++ ) {
            res += power( 2, i%10 );
        }
        end = System.currentTimeMillis();
        System.out.println( "Duration IT: " + (end-begin) + "ms - " + res );
    }

}

Et voici les résultats produits par ce programme.

$> java Demo
Duration REC: 6664ms - 102300000000
Duration IT: 3815ms - 102300000000
$> 

Enfin, rappelez-vous que la pile d'exécution, qui est utilisée pour effectuer chaque appel de méthode, est limitée en termes de taille. Un trop grand nombre d'appels de méthodes, enchainés, peut donc produire une erreur de type java.lang.StackOverflowError. Voici un exemple de code saturant la pile d'exécution.

 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 

public class Demo {
    
    public static long powerRec( long value, long pow ) {
        if ( pow == 0 ) return 1;
        return value * powerRec( value, pow-1 );
    }
        
    public static void main(String[] args) {
        
        System.out.println( powerRec( 2, 100_000 ) );
        
    }

}

Et voici les résultats produits par ce code.

$>  java Demo
Exception in thread "main" java.lang.StackOverflowError
    at Demo.powerRec(Demo.java:5)
    at Demo.powerRec(Demo.java:5)
    at Demo.powerRec(Demo.java:5)
    at Demo.powerRec(Demo.java:5)
    at Demo.powerRec(Demo.java:5)
    at Demo.powerRec(Demo.java:5)
    at Demo.powerRec(Demo.java:5)
    at Demo.powerRec(Demo.java:5)
    at Demo.powerRec(Demo.java:5)
    ...
$> 

Travaux pratiques

Le sujet

Je vous propose, en guise de travaux pratiques, de coder la fonction mathématiques factorielle de manière récursive (vous pouvez aussi chercher à la recoder de manière itérative si vous en avez le courage). Cette fonction est notée n! ou n est l'entier pour lequel calculer la factorielle : elle renvoie les produits des n premiers entiers. En voici sa définition récursive :

0! = 1
1! = 1
n! = n * (n-1)!

Bon courage et jouez le jeu : ne regardez pas la correction immédiatement.

La correction

Voici ma proposition de codage de la méthode de calcul de la factorielle.

 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 

public class Demo {

    public static int factRec( int value ) {
        if ( value == 0 || value == 1 ) return 1;
        return value * factRec( value - 1 );
    }

    
    public static int fact( int value ) {
        int accumulator = 1;
        
        for (int i = 2; i <= value; i++) {
            accumulator *= i;
        }
        
        return accumulator;
    }
        
    public static void main(String[] args) {
       
        System.out.println( "0! == " + factRec( 0 ) );  // 1
        System.out.println( "1! == " + factRec( 1 ) );  // 1
        System.out.println( "3! == " + factRec( 3 ) );  // 6
        System.out.println( "5! == " + factRec( 5 ) );  // 120
        System.out.println( "6! == " + factRec( 6 ) );  // 720

        System.out.println( "0! == " + fact( 0 ) );     // 1
        System.out.println( "1! == " + fact( 1 ) );     // 1
        System.out.println( "3! == " + fact( 3 ) );     // 6
        System.out.println( "5! == " + fact( 5 ) );     // 120
        System.out.println( "6! == " + fact( 6 ) );     // 720
 
    }

}

Et voici les résultats que vous devriez afficher :

$> java Demo
0! == 1
1! == 1
3! == 6
5! == 120
6! == 720
0! == 1
1! == 1
3! == 6
5! == 120
6! == 720
$>

Méthodes à nombre variable de paramètres Nos premières expressions régulières