Aller au contenu
Programmation 2 · L2

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.

Voir toutes les leçons de Programmation 2

Signaler une erreur dans cette leçon

Toutes les leçons de Programmation 2

Pose ta question à Karamö