Lycée > Terminale > NSI > Utiliser la récursivité en Python

Utiliser la récursivité en Python

Fiche de cours
Quiz
Profs en ligne
Videos
Application mobile

Objectifs

Comprendre la notion de récursivité.
Savoir programmer une fonction récursive en Python.

Points clés

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.

Pour bien comprendre

Savoir écrire une fonction en Python.

1. Introduction à la récursivité

a. Généralités

En algorithmique et en programmation, une fonction récursive f est une fonction dont le code contient un ou plusieurs appels à f. Ces appels sont appelés des appels récursifs.

La récursivité est un moyen de répéter des blocs d’instructions sans utiliser de boucle while ou for.

Exemple
On peut définir la fonction puissance f(y , n) = yⁿ (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 yⁿ = y × yⁿ^–¹.

La récursivité s’apparente ici à la récurrence en mathématiques.

b. Avec Python

En Python, l’implémentation d’une fonction récursive est semblable à celle des autres fonctions, à ceci près qu’une fonction récursive doit impérativement contenir un retour avec le mot clé return pour faire les appels récursifs.

Méthode
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.

Exemple
En Python, la fonction puissance(y, n) implémente le calcul de yⁿ (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 y⁰=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).

Lors de l’exécution d’un algorithme récursif, les appels récursifs successifs sont stockés dans une pile, c’est la pile d’exécution.
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.

2. Les limites de la récursivité

a. Espace mémoire

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

La taille de la pile d’exécution est limitée. Par défaut, le nombre maximum d’appels récursifs autorisés est fixé à 1000.

Exemple
En reprenant la fonction puissance(y, n), on peut facilement obtenir cette erreur en appelant puissance(1, 1000).

Le module sys de Python permet de régler le nombre maximum d’appels récursifs autorisé.

Exemple
Pour un nombre maximum de 5000, il suffit d’utiliser les instructions suivantes.

import sys
sys.setrecursionlimit(5000)

b. Fonction récursive ou itérative - Exemple

La suite de Fibonacci

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.

Exemple
Après 5 – 8, on obtient le nombre 13 car 5 + 8 = 13.

La programmation de la suite de Fibonacci

Fonction récursive

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 9^e 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.

Fonction itérative

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.