ntro.ca

        • Contrats de classe
        • Liens utiles
        • Calendrier
        • Calendrier groupe 2
        • Calendrier groupes 1, 3
        • Structure du cours
        • Évaluations
        • Matériel à se procurer
        • Les profs
          • Marc-Olivier Tremblay
          • Mathieu Bergeron
        • Module 1.1: installation + trier des cartes
        • Module 1.2: rappels POO
        • Module 1.3: tableau d'objets
        • Examen 1
        • Module 2.1: données JSON
        • Module 2.2: données en Java
        • Module 2.3: récursivité
        • Examen 2
        • Module 3.1: structure générique
        • Module 3.2: efficacité (1)
        • Module 3.3: efficacité (2)
        • Examen 3
        • Module 4.1: liste naïve
        • Module 4.2: liste par tableau
        • Module 4.3: liste chaînée
        • Examen 4
        • Module 5.1: mappage naïf
        • Module 5.2: mappage par hachage
        • Module 5.3: mappage par arbre
        • Examen 5
        • Équipes
          • Horaire groupe 1
          • Horaire groupe 2
          • Horaire groupe 3
          • Groupe 1
          • Groupe 2
          • Groupe 3
        • Projets vedettes 2022
        • Projets vedettes 2023
        • Projets vedettes 2024
        • Projets vedettes 2025
        • Survol
        • Structure
        • Calendrier
        • Calendrier des séances
        • Évaluations
        • Exemples de jeu
        • Exemples de pages
        • Réponses à vos questions
        • Module 1: créer le projet
        • Module 2: concevoir l'application
        • Module 3: vues NtroFx
        • Module 4: modèle et navigation
        • Module 5: ajouter le dorsal, modifier le modèle
        • Module 7: améliorer l'affichage
        • Module 8: jeu en 2d
        • Module 9: client/serveur
        • Module 10: plusieurs instances du même modèle
        • TP1
        • Examen 1
        • TP2
        • Examen 2
        • Projet de fin de session
        • Calendrier
        • Structure du cours
        • Évaluations
        • Contrat de classe
        • Le prof
        • 01: Windows et Word
          • Astuces et raccourcis
        • 02: Word
        • 03: Word
          • Exercice Word: insertion d'éléments spéciaux
          • Exercice Word: tableaux
        • 04: Word
          • Exercice Word: références
          • TP01: Word (15%)
        • 05: PowerPoint
          • TP02: PowerPoint (10%)
        • 06: Examen Word (20%)
        • 07: Excel
        • 08: Excel
        • 09: Excel
          • TP03: Excel (15%)
        • 10: Excel
        • 11: Examen Excel (20%)
        • 12: Access
        • 13: Access
        • 14: Access
        • 15: Examen Access
      • Sondage H2023 (dept. info)
      • Vision H2023 (dept. info)
      • P1) exercices interactifs de lecture
      • P2) transition Excel vers Python
        • Atelier 2: un exemple
      • Jquery
      • Jquery Ui
      • Point de vue sur l'IA
    Pile Appel
    • La récursivité
      • Pile d’appel
      • Avantages de la récursivité
      • Inconvénient de la récursivité
      • Transformer en boucle normale

    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);
        }
    }
    
    Creative Commons License Creative Commons Attribution Creative Commons ShareAlike
    • La récursivité
      • Pile d’appel
      • Avantages de la récursivité
      • Inconvénient de la récursivité
      • Transformer en boucle normale