Une fonction récursive est une fonction qui s’appelle elle-même. Cette idée permet d’écrire très simplement des algorithmes qui découpent un problème en un problème plus petit de même nature : factorielle, puissance, parcours d’arbres, tri fusion… Encore faut-il savoir s’arrêter.
Une question sur ce cours ?
ULU, le tuteur d’ULUMINE, t’aide à partir de ce cours.
Objectifs
- Écrire une fonction récursive avec un ou plusieurs cas de base
- Analyser le fonctionnement d’un programme récursif à l’aide de la pile d’appels
- Justifier la terminaison d’une fonction récursive
- Comparer une version récursive et une version itérative d’un même algorithme
1. Principe d’une fonction récursive
Fonction récursive : Fonction dont la définition contient un appel à elle-même. Elle comporte toujours au moins un cas de base (résultat donné directement, sans appel récursif) et un ou plusieurs appels récursifs portant sur des données « plus petites ».
La factorielle se définit par 0! = 1 et n! = n × (n − 1)! pour n ≥ 1. Cette définition mathématique se traduit directement en Python.
def fact(n):
if n == 0: # cas de base
return 1
return n * fact(n - 1) # appel récursif2. La pile d’appels
Chaque appel de fonction est mémorisé dans la pile d’appels (avec ses paramètres et ses variables locales). Un appel récursif empile un nouveau contexte ; quand un appel se termine, son contexte est dépilé et son résultat est transmis à l’appel précédent.
Déroulé de fact(3)
- fact(3) attend le résultat de fact(2) pour calculer 3 × fact(2).
- fact(2) attend fact(1), qui attend fact(0).
- fact(0) est le cas de base : il renvoie 1. La pile commence à se vider.
- fact(1) renvoie 1 × 1 = 1, puis fact(2) renvoie 2 × 1 = 2, puis fact(3) renvoie 3 × 2 = 6.
fact(3) vaut 6, après 4 appels empilés (fact(3), fact(2), fact(1), fact(0)).
3. Exemples classiques
def somme(L):
if L == []:
return 0
return L[0] + somme(L[1:])
def puissance(x, n):
if n == 0:
return 1
return x * puissance(x, n - 1)
def pgcd(a, b):
if b == 0:
return a
return pgcd(b, a % b)Une fonction peut aussi faire plusieurs appels récursifs. La suite de Fibonacci est définie par F0 = 0, F1 = 1 et Fn = Fn−1 + Fn−2.
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)4. Terminaison et comparaison avec l’itératif
Pour prouver qu’une fonction récursive termine, on montre qu’une quantité entière positive (souvent n, ou la longueur d’une liste) diminue strictement à chaque appel et que le cas de base est atteint lorsqu’elle devient minimale.
Terminaison de pgcd(a, b) pour a, b entiers naturels
- À chaque appel, le second paramètre devient a % b, qui est strictement inférieur à b.
- Une suite d’entiers naturels strictement décroissante ne peut pas être infinie.
- Le second paramètre finit donc par valoir 0 : c’est le cas de base.
pgcd(a, b) termine pour tous entiers naturels a et b.
| Version récursive | Version itérative | |
|---|---|---|
| Écriture | Proche de la définition mathématique, souvent courte | Boucle for ou while, variables accumulatrices |
| Mémoire | Un contexte par appel dans la pile | Mémoire constante en général |
| Limite | Profondeur maximale (RecursionError) | Pas de limite de profondeur |
def fact_iter(n):
r = 1
for k in range(2, n + 1):
r = r * k
return rÀ retenir
- Une fonction récursive s’appelle elle-même et possède au moins un cas de base.
- Chaque appel est empilé dans la pile d’appels ; les calculs se font à la remontée.
- La terminaison se prouve avec une quantité entière qui décroît strictement jusqu’au cas de base.
- Une récursivité double (comme fib) peut provoquer un nombre exponentiel d’appels.
- Toute fonction récursive peut être réécrite en itératif, et inversement.
Et maintenant, à toi !
Vérifie que tu as compris avec les exercices, puis révise avec la fiche.