La récursivité #

• C’est quand une methode() fait un appel à elle-même:

public void methode(){
    /* ... */


    methode();


    /* ... */
}

• Le résultat est une boucle

• Plusieurs algorithmes sont plus faciles à coder de cette façon

  • c’est souvent plus proche de la définition papier (mathématique)

• Par exemple:

  • définition mathématique de la fonction factorielle:

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

  • code Java récursif:

public int factoriel(int n){
    if(n == 0){

        return 1;

    }else{

        return n * factoriel(n-1);
    }
}

• NOTE: le prof ignore volontairement le guide de style en faisant deux return

• Il est toujours possible de transformer des appels récursifs en boucle normale

public int factoriel(int n){
    int resultat;

    if(i == 0){

        resultat = 1;

    }else{

        resultat = n;

        for(int i = n-1; i > 0; i--){
            resultat = resulat * i;
        }

    }

    return resultat;
}

• NOTE: on voit comment la code est plus loin de la définition mathématique

Pile d’appel #

• La récursivité utilise la pile d’appels pour mémoriser des valeurs

• Qu’est-ce que la pile d’appels?

  • quand on fait un appel de méthode, les arguments sont stoqués sur la pile
  • quand la méthode termine, c’est retiré de la pile
  • la pile permet de revenir là où on était dans la méthode précédente

• Par exemple:

public static void A(int x, int y){

    B("a");
}

public static void B(String c){

    C(new char[]{'a','b'});
}

public static void C(char[] tab){

}

public static void main(String[] args){

    A(0,1);  

    // La pile va être
    //
    // au début:     main()                
    // appel de A:   main(), A(0,1)
    // appel de B:   main(), A(0,1), B("a")
    // appel de C:   main(), A(0,1), B("a"), C({'a','b'})
    // retour de C:  main(), A(0,1), B("a")
    // retour de B:  main(), A(0,1)
    // retour de A:  main()
}

• En cas de plantage, la pile d’appel est affichée (équivalent de la ligne 24):

    Exception in thread "main" java.lang.RuntimeException
        at Pile.C(Pile.java:15)
        at Pile.B(Pile.java:11)
        at Pile.A(Pile.java:6)
        at Pile.main(Pile.java:20)
  

Avantages de la récursivité #

• Code souvent plus simple et plus lisible

• Les boucles infinies sont détectées par des erreurs de débordement de pile

  • en anglais: stack overflow

      Exception in thread "main" java.lang.StackOverflowError
          at Pile.A(Pile.java:6)
          at Pile.A(Pile.java:6)
          at Pile.A(Pile.java:6)
          at Pile.A(Pile.java:6)
          at Pile.A(Pile.java:6)
          at Pile.A(Pile.java:6)
          at Pile.A(Pile.java:6)
          at Pile.A(Pile.java:6)
          at Pile.A(Pile.java:6)
          ...
    

Inconvénient de la récursivité #

• Plus facile d’écrire des boucles infinies (condition d’arrêt implicite)

• En pratique, la pile d’appel est assez petite (p.ex. 1000 appels)

  • donc souvent impossible d’utiliser la récursivité sur des gros problèmes

Transformer en boucle normale #

• On peut transformer n’importe quelle méthode récursive en boucle

• On peut écrire du code récursif pour un prototype

  • et éliminer la récursivité pour le code de production

• Certains compilateurs peuvent éliminer automatiquement la récursivité

  • à condition que l’appel récursif soit la toute dernière instruction de la méthode

public int factoriel(int n){
    return factoriel(n, 1);
}

public int factoriel(int n, int courant){
    if(n == 0){

        return courant;

    }else{

        return factoriel(n-1, n * courant);
    }
}