Leçon 3 sur 5
La récursivité et ses pièges
Je sais écrire une fonction récursive correcte (cas de base, appel sur un problème plus petit), suivre son exécution sur la pile d'appels, reconnaître les récursions coûteuses et les corriger par mémoïsation ou par une version itérative.
- 1 h 25
- 5 exercices corrigés
- QCM de 6 questions
À la fin de la leçon, vous saurez :
- Définir une fonction récursive et identifier son cas de base et sa réduction
- Dessiner la pile d'appels et expliquer l'erreur RecursionError
- Estimer le coût d'une fonction récursive à l'aide d'une relation de récurrence
- Corriger une récursion exponentielle par mémoïsation
- Transformer une récursion simple en boucle
Avant de commencer : Leçon 2 (piles) ; Algorithmique (L1) ; Programmation 1 (L1, Python : fonctions).
1Je découvre
Pendant la révision de l'examen d'algorithmique, à l'université de Kankan, Hawa écrit une fonction qui calcule le n-ième terme de la suite de Fibonacci en recopiant directement la définition mathématique. Pour n = 10, la réponse s'affiche aussitôt. Pour n = 35, son vieil ordinateur portable mouline plusieurs secondes. Pour n = 50, elle abandonne au bout de dix minutes, juste avant la coupure de courant du soir.
Son voisin de chambre, lui, a écrit une fonction récursive qui parcourt une liste de 5 000 notes : Python s'arrête net avec le message RecursionError: maximum recursion depth exceeded.
Pourtant, leurs deux fonctions sont « justes » sur le papier.
Qu'est-ce qu'une fonction récursive correcte, comment s'exécute-t-elle réellement, et comment éviter les pièges qui la rendent lente ou la font planter ?
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 Algorithmique avancée et structures de données
Signaler une erreur dans cette leçon
Toutes les leçons de Algorithmique avancée et structures de données