Utiliser la récursivité en Python
- Fiche de cours
- Quiz et exercices
- Vidéos et podcasts
- Comprendre la notion de récursivité.
- Savoir programmer une fonction récursive en Python.
- Une fonction récursive est une fonction qui s’appelle elle-même. Ces appels sont les appels récursifs.
- Les appels récursifs d’une fonction récursive sont stockés dans la pile d’exécution.
- Une fonction récursive peut vite être gourmande en mémoire en saturant la pile d’exécution.
Savoir écrire une fonction en Python.
On peut définir la fonction puissance f(y , n) = yn (pour y un nombre et n un entier positif) de deux manières différentes.
- De manière itérative
(répétition) :
f(y , n) = y × y × y × y… × y (avec n facteurs tous égaux à y).
On répète plusieurs fois une opération. - De manière récursive :
- initialisation : f(y , 0) = 1.
- relation pour n > 0 :
f(y , n) = y × f(y , n – 1)
car si n > 0, on a yn = y × yn–1.
La récursivité s’apparente ici à la récurrence en mathématiques.
Lorsque l’on écrit une fonction récursive en Python, on peut partager son code en deux parties.
- Une condition d’arrêt pour stopper les appels récursifs.
- Les appels récursifs.
En Python, la fonction puissance(y, n) implémente le calcul de yn (pour y un nombre et n un entier positif)
| Python | Explication |
| def puissance(y, n): | On définit la fonction puissance. |
| if n == 0: | Si n est égal à 0, alors |
| return 1 | on retourne 1 (car y0=1). |
| else: | Sinon |
| return y*puissance(y, n-1) |
on retourne : y*puissance(y,n-1) |
Les deuxième et troisième lignes
constituent la condition d’arrêt.
La dernière ligne organise les appels
récursifs de la fonction puissance(y, n).
On peut visualiser sur Python Tutor les appels
récursifs qui permettent de calculer
puissance(2, 10).
Plus précisément, la pile d’exécution est un emplacement mémoire destiné à stocker les paramètres, les variables locales ainsi que les adresses mémoires de retour des fonctions en cours d’exécution.
Une fonction récursive peut rapidement être gourmande en mémoire. C’est pourquoi on peut obtenir le message d’erreur :
RuntimeError: maximum recursion depth exceeded
En reprenant la fonction puissance(y, n), on peut facilement obtenir cette erreur en appelant puissance(1, 1000).
Pour un nombre maximum de 5000, il suffit d’utiliser les instructions suivantes.
sys.setrecursionlimit(5000)
En programmation, il faut être vigilant à ce que l’utilisation de la récursivité ne soit pas moins efficace qu’une programmation itérative, plus classique.
La programmation de la suite de Fibonacci en est un exemple célèbre.
La suite de Fibonacci est la suite de nombres entiers :
1 – 1 – 2 – 3 – 5 – 8 – ....
En pratique, on obtient un élément de la suite en additionnant les deux termes précédents.
Après 5 – 8, on obtient le nombre 13 car 5 + 8 = 13.
En Python, la fonction fibo(n) suivante implémente le calcul du (n+1)-ème terme de la suite de Fibonacci.
| Python | Explication |
| def fibo(n): | On définit la fonction fibo. |
| if n < 2 | Si i=0 ou i=1, alors |
| return 1 | on retourne 1. |
| else: | Sinon |
| return fibo(n-1)+ fibo(n-2) | on retourne la somme des deux termes précédents fibo(n). |
Cette fonction récursive calcule effectivement les termes de la suite de Fibonacci. Toutefois, est-ce efficace de la coder ainsi ?
Voici l’appel de cette fonction sur Python Tutor pour n=8.
En observant l’exécution de ce programme, Python Tutor compte 270 étapes pour calculer le 9e terme de la suite de Fibonacci.
À la main, cela donne :
1 – 1 (0
+
1) – 2 (1
+
1) – 3 (1
+
2) – 5 (2
+ 3) – 8 (3
+
5) – 13 (5 –
8) – 21 (8
+
13) – 34 (13
+ 21).
Nous sommes loin des 270 étapes.
Théoriquement, la suite de Fibonacci est programmable avec une fonction récursive. En pratique, il est plus judicieux de la programmer sans récursivité, de manière itérative.
Par exemple, la fonction fibo2(n) suivante implémente le calcul du (n+1)-ème terme de la suite de Fibonacci sans récursivité.
| Python | Explication |
| def fibo2(n): | On définit la fonction fibo2. |
| u0, u1 = 1, 1 | On initialise u0 et u1 aux premiers termes de la suite. |
| for i in range(n-1): | Pour i allant de 0 à n – 2, |
| u0, u1 = u1, u0 + u1 | on affecte à u0 et u1 les termes suivants : u0 prend la valeur de u1 et u1 référence le terme suivant u0+u1. |
| return u1 | on retourne le dernier terme calculé : u1. |
Voici l’appel de cette fonction sur Python Tutor pour n=8.
Dans ce cas, Python Tutor compte 21 étapes.
La programmation de la suite de Fibonacci semble être plus efficace avec des itérations qu’en récursivité.
Évalue ce cours !
Des quiz et exercices pour mieux assimiler sa leçon
La plateforme de soutien scolaire en ligne myMaxicours propose des quiz et exercices en accompagnement de chaque fiche de cours. Les exercices permettent de vérifier si la leçon est bien comprise ou s’il reste encore des notions à revoir.
Des exercices variés pour ne pas s’ennuyer
Les exercices se déclinent sous toutes leurs formes sur myMaxicours ! Selon la matière et la classe étudiées, retrouvez des dictées, des mots à relier ou encore des phrases à compléter, mais aussi des textes à trous et bien d’autres formats !
Dans les classes de primaire, l’accent est mis sur des exercices illustrés très ludiques pour motiver les plus jeunes.
Des quiz pour une évaluation en direct
Les quiz et exercices permettent d’avoir un retour immédiat sur la bonne compréhension du cours. Une fois toutes les réponses communiquées, le résultat s’affiche à l’écran et permet à l’élève de se situer immédiatement.
myMaxicours offre des solutions efficaces de révision grâce aux fiches de cours et aux exercices associés. L’élève se rassure pour le prochain examen en testant ses connaissances au préalable.
Des vidéos et des podcasts pour apprendre différemment
Certains élèves ont une mémoire visuelle quand d’autres ont plutôt une mémoire auditive. myMaxicours s’adapte à tous les enfants et adolescents pour leur proposer un apprentissage serein et efficace.
Découvrez de nombreuses vidéos et podcasts en complément des fiches de cours et des exercices pour une année scolaire au top !
Des podcasts pour les révisions
La plateforme de soutien scolaire en ligne myMaxicours propose des podcasts de révision pour toutes les classes à examen : troisième, première et terminale.
Les ados peuvent écouter les différents cours afin de mieux les mémoriser en préparation de leurs examens. Des fiches de cours de différentes matières sont disponibles en podcasts ainsi qu’une préparation au grand oral avec de nombreux conseils pratiques.
Des vidéos de cours pour comprendre en image
Des vidéos de cours illustrent les notions principales à retenir et complètent les fiches de cours. De quoi réviser sa prochaine évaluation ou son prochain examen en toute confiance !
Fiches de cours les plus recherchées
NSI
Utiliser une API et des bibliothèques
NSI
Utiliser les paradigmes impératifs et fonctionnels
NSI
Utiliser le paradigme objet
NSI
Repérer les bugs : typages, effets de bords, débordements
NSI
Repérer les bugs : structures
NSI
Anticiper les erreurs classiques
NSI
Utiliser Python pour déterminer les mesures des arbres binaires
NSI
Utiliser Python dans les arbres binaires de recherche
NSI
Rechercher et insérer une clé dans un arbre binaire de recherche
NSI
Parcourir un arbre binaire
Fermer
Accédez gratuitement à
