7- Fonctions récursives
Une fonction récursive est une fonction qui s'appelle elle-même. C'est une manière très naturelle (bien que pas toujours si intuitive que ça) d'écrire beaucoup d'algorithmes : on résout un problème en se ramenant au même problème, sur une entrée plus petite.
I. Principe
a) Un premier exemple
Loading editor...
def compte_a_rebours(n):
if n == 0:
print("Décollage !")
else:
print(n)
compte_a_rebours(n - 1)
compte_a_rebours(5)Pour afficher le compte à rebours depuis n, on affiche n, puis on affiche le compte à rebours depuis n - 1... qui est le même problème, en plus petit !
Structure d'une fonction récursive
Une fonction récursive contient toujours :
- un (ou plusieurs) cas de base, où la fonction renvoie directement un résultat, sans s'appeler elle-même ;
- un (ou plusieurs) appels récursifs, sur des entrées "plus petites", qui se rapprochent du cas de base.
Si on oublie le cas de base, ou si les appels récursifs ne s'en rapprochent pas, la fonction s'appelle sans fin (voir la partie VI).
b) Renvoyer un résultat
Une fonction récursive peut aussi renvoyer une valeur, construite à partir du résultat de l'appel récursif. Par exemple, la somme des éléments d'une liste est le premier élément, plus la somme des autres :
Loading editor...
def somme(L):
if len(L) == 0:
return 0
else:
return L[0] + somme(L[1:])
somme([3, 1, 4, 1, 5])Autre exemple : un mot est un palindrome si sa première et sa dernière lettre sont égales, et si ce qui reste au milieu est un palindrome.
Loading editor...
def palindrome(mot):
if len(mot) <= 1:
return True
return mot[0] == mot[-1] and palindrome(mot[1:-1])
print(palindrome("radar"))
print(palindrome("kayak"))
print(palindrome("python"))c) Que se passe-t-il pendant l'exécution ?
Chaque appel de fonction a ses propres variables locales. Quand une fonction en appelle une autre (ou elle-même), elle est mise en attente jusqu'à ce que l'appel se termine : les appels en attente forment la pile d'appels.
Loading editor...
def somme_bavarde(L, profondeur=0):
marge = " " * profondeur
print(marge + "somme de", L)
if len(L) == 0:
resultat = 0
else:
resultat = L[0] + somme_bavarde(L[1:], profondeur + 1)
print(marge + "->", resultat)
return resultat
somme_bavarde([3, 1, 4])II. Figures avec des print
La récursivité permet de dessiner des figures qui contiennent une copie d'elles-mêmes, en plus petit.
a) Une pyramide
Une pyramide de hauteur marge :
Loading editor...
def pyramide(n, marge=0):
if n > 0:
pyramide(n - 1, marge + 1) # le haut : une pyramide plus petite, décalée
print(" " * marge + "*" * (2 * n - 1)) # puis la base
pyramide(5)b) Un sablier
De même, un sablier de taille
Loading editor...
def sablier(n, marge=0):
if n > 0:
print(" " * marge + "*" * (2 * n - 1))
sablier(n - 1, marge + 1)
print(" " * marge + "*" * (2 * n - 1))
sablier(4)c) Une règle graduée
Sur une règle, la graduation du milieu est la plus grande ; de chaque côté, on retrouve une règle plus petite, de taille
Loading editor...
def regle(n):
"""Affiche les graduations d'une règle, la plus longue mesurant n."""
if n > 0:
regle(n - 1)
print("-" * n)
regle(n - 1)
regle(4)Pour une règle de taille
III. Dichotomie récursive
La recherche dichotomique se découpe naturellement de manière récursive : on cherche dans une moitié de la liste, qui est le même problème en plus petit. Pour ne pas recopier la liste, on passe en argument les bornes de la partie où l'on cherche.
Loading editor...
def recherche_dicho(L, x, i, j):
"""Cherche x dans L[i:j], supposée triée. Renvoie un indice de x, ou None."""
if j <= i:
return None
milieu = (i + j) // 2
if L[milieu] < x:
return recherche_dicho(L, x, milieu + 1, j)
elif L[milieu] > x:
return recherche_dicho(L, x, i, milieu)
else:
return milieu
L = [-1, 0, 1, 2, 3, 4, 5, 10, 123, 124]
print(recherche_dicho(L, 10, 0, len(L)))
print(recherche_dicho(L, 6, 0, len(L)))IV. Énumérer des objets
La récursivité est très pratique pour énumérer toutes les possibilités.
a) Les sous-listes
Les sous-listes de [a, b, c] (en gardant l'ordre des éléments) sont : celles qui ne contiennent pas a, c'est-à-dire les sous-listes de [b, c], et les mêmes auxquelles on ajoute a au début.
Loading editor...
def sous_listes(L):
if len(L) == 0:
return [[]]
sans_premier = sous_listes(L[1:])
avec_premier = [[L[0]] + s for s in sans_premier]
return sans_premier + avec_premier
print(sous_listes([1, 2, 3]))
print(len(sous_listes(list(range(10)))))Une liste de taille
b) Les permutations
Une permutation de L commence par l'un des éléments de L, suivi d'une permutation des autres éléments.
Loading editor...
def permutations(L):
if len(L) <= 1:
return [L[:]]
resultat = []
for i in range(len(L)):
autres = L[:i] + L[i+1:]
for p in permutations(autres):
resultat.append([L[i]] + p)
return resultat
print(permutations([1, 2, 3]))
print(len(permutations([1, 2, 3, 4, 5])))Une liste de
V. Fractales
Une fractale est une figure qui contient des copies d'elle-même en plus petit : c'est une figure récursive !
Le flocon de Koch est obtenu en remplaçant chaque segment par quatre segments trois fois plus petits, formant une "pointe" au milieu, et en recommençant sur chacun des nouveaux segments :
Loading editor...
from math import sqrt
from affichage import tracer
def koch(xa, ya, xb, yb, n):
"""Renvoie la liste des points de la courbe de Koch d'ordre n entre A et B (sans le point B)."""
if n == 0:
return [(xa, ya)]
dx, dy = (xb - xa) / 3, (yb - ya) / 3
# les points au tiers et aux deux tiers du segment
x1, y1 = xa + dx, ya + dy
x2, y2 = xa + 2 * dx, ya + 2 * dy
# la pointe : le troisième sommet du triangle équilatéral construit sur [P1, P2]
xp = x1 + dx / 2 - dy * sqrt(3) / 2
yp = y1 + dy / 2 + dx * sqrt(3) / 2
return (koch(xa, ya, x1, y1, n - 1) + koch(x1, y1, xp, yp, n - 1)
+ koch(xp, yp, x2, y2, n - 1) + koch(x2, y2, xb, yb, n - 1))
def flocon(n):
a, b, c = (0, 0), (0.5, -sqrt(3) / 2), (1, 0)
points = koch(*a, *b, n) + koch(*b, *c, n) + koch(*c, *a, n) + [a]
tracer(([x for (x, y) in points], [y for (x, y) in points]), titre=f"Flocon de Koch d'ordre {n}")
flocon(3)Essayez avec d'autres valeurs de n (au-delà de 6, il y a beaucoup de points !).
VI. La pile d'appels et ses limites
Chaque appel en attente occupe de la place dans la mémoire, dans la pile d'appels. Cette pile a une taille limitée : si une fonction s'appelle trop de fois "en profondeur", on obtient une erreur de dépassement de la pile.
Loading editor...
import sys
print("Nombre maximal d'appels imbriqués :", sys.getrecursionlimit())
def compte(n):
if n == 0:
return 0
return 1 + compte(n - 1)
print(compte(500))
print(compte(100000))C'est ce qui arrive aussi lorsqu'on oublie le cas de base : les appels ne s'arrêtent jamais, et la pile déborde.
En Python, la limite est volontairement basse. Pour des traitements très longs (parcourir une liste de 100 000 éléments, par exemple), on préférera une boucle.
Exercices
Exercice 1
Écrire une fonction récursive puissance(x, n) qui calcule
Loading editor...
def puissance(x, n):
if n == 0:
return 1
return x * puissance(x, n - 1)Exercice 2
Écrire une fonction récursive maximum(L) qui renvoie le plus grand élément d'une liste non vide.
Loading editor...
def maximum(L):
if len(L) == 1:
return L[0]
m = maximum(L[1:])
if L[0] > m:
return L[0]
return mExercice 3
Écrire une fonction récursive binaire(n) qui renvoie la chaîne de caractères de l'écriture en base 2 de l'entier
Loading editor...
def binaire(n):
if n <= 1:
return str(n)
return binaire(n // 2) + str(n % 2)Exercice 4
Écrire une fonction récursive escalier(n) qui affiche un escalier de
#
#
#Loading editor...
def escalier(n, marge=0):
if n > 0:
print(" " * marge + "#")
escalier(n - 1, marge + 2)