Leçon 2 sur 5
La récursivité
Je sais écrire une fonction récursive correcte (cas de base, appel récursif qui progresse), prévoir son exécution grâce à la pile d'appels, prouver sa terminaison et comparer son coût à une version itérative.
- 1 h 10
- 4 exercices corrigés
- QCM de 5 questions
À la fin de la leçon, vous saurez :
- Définir une fonction récursive et identifier cas de base et appel récursif
- Dérouler l'exécution à l'aide de la pile d'appels
- Justifier la terminaison et la correction par récurrence
- Évaluer le nombre d'appels (factorielle, Fibonacci, exponentiation rapide)
- Choisir entre version récursive et itérative
Avant de commencer : Leçon 1 de ce cours (fonctions) ; raisonnement par récurrence (mathématiques de L1).
1Je découvre
Pendant une séance de TD à Conakry, l'enseignant pose une question : « Combien de façons y a-t-il de ranger 5 livres différents sur une étagère ? » Mamadou répond : « Je choisis le premier livre (5 choix), puis il reste à ranger 4 livres, ce qui est le même problème en plus petit. » Il vient d'avoir une idée récursive : résoudre un problème en le ramenant au même problème de taille plus petite, jusqu'à un cas trivial (ranger 0 livre : une seule façon).
Les mathématiciens connaissent cette idée sous le nom de raisonnement par récurrence ; en programmation, elle donne des fonctions qui s'appellent elles-mêmes.
Comment écrire une fonction récursive qui termine et donne le bon résultat, et quand est-ce une bonne idée ?
La suite se lit avec votre compte Kharandi Université
La première leçon de chaque cours est libre. Kharandi Université est une inscription à part de l’école : avec votre compte étudiant, vous lisez toutes les leçons en entier, avec les exercices corrigés et les QCM, et les 7 premiers jours sont offerts.