2 4 1 intro
Introduction à la récursivité¶
Voir aussi
Motivation et introduction du concept¶
Un algorithme est dit récursif s'il s'appelle lui-même directement ou indirectement via l'appel d'une ou de plusieurs autres fonctions qui elles-mêmes finissent par l'appeler.
La récursivité est un concept fondamental en informatique qui met naturellement en pratique un mode de pensée puissant qui consiste à pouvoir découper la tâche à réaliser en sous-tâches de même nature mais plus petites qui finalement sont simples à résoudre.
La démarche s'inspire de la démarche inductive mathématique utilisée dans les preuves par récurrence :
Rappel du principe
Si l'on doit prouver l'assertion S(n) = f (n) pour tout n supérieur ou égal à n_0 :
Pour le cas de base on prouve l'assertion pour certaines petites valeurs de n (n_0 par exemple).
Pour l'étape de récurrence : on suppose que c'est vrai pour n inférieur ou égal à k (avec k supérieur ou égal à n0), et prouve que c'est également vrai pour n = k + 1.
Remarque : on peut aussi supposer que c'est vrai pour n inférieur ou égal à k - 1 et prouver que c'est vrai pour n = k.
C'est ce qu'on fera ici : souvent plus intuitif d'un point de vue informatique.
Prenons par exemple le calcul de la factorielle d'un nombre n. Par définition pour un n entier strictement positif, n! est égale au produit des entiers strictement positifs inférieurs à n. Par convention on a aussi 0! = 1.
Donnons le code itératif d'une fonction calculant la factorielle :
def fact(n):
"""Renvoie la factorielle de n."""
res = 1
i = 1
for i in range(1,n+1):
res = res * i
return res
La définition récursive se base sur la définition n! = n.(n-1)! pour tout n>0 avec 0! = 1
On obtient le code :
def fact(n):
"""Renvoie la factorielle de n (méthode récursive)."""
if n == 0:
res = 1
else:
res = n*fact(n-1)
return res
ou plus court :
def fact(n):
"""Renvoie la factorielle de n (méthode récursive)."""
return 1 if n == 0 else n * fact(n-1)
De nombreux algorithmes écrits de façon itérative sont énoncés de façon récursive.
Par exemple la conjecture de syracuse est la suivante : ayant un nombre n entier strictement positif, à chaque étape si n est pair on le divise par 2 sinon on le multiplie par 3 et ajoute 1.
Le programme de test de la conjecture de syracuse :
def test_syracuse(n):
"""Teste si à partir de n le code s'arrête bien (la conjecture de syracuse est respectée pour n)."""
while n != 1:
if n % 2 == 0:
n = n//2
else:
n = n*3+1
return True
Littéralement on pourrait l'écrire :
def test_syracuse(n):
"""Teste si à partir de n le code s'arrête bien (la conjecture de syracuse est respectée pour n)."""
if n == 1:
res = True
else:
if n%2 == 0:
n = n//2
else:
n = 3*n+1
res = test_syracuse(n)
return res
ou de façon plus abrégée :
def test_syracuse(n):
"""Teste si à partir de n le code s'arrête bien (la conjecture de syracuse est respectée pour n)."""
if n == 1:
res = True
else:
res = test_syracuse(n//2 if n%2 == 0 else 3*n+1)
return res
ou encore plus abrégé (ce qui devient illisible) :
def test_syracuse(n):
return True if n == 1 else test_syracuse(n//2 if n%2 == 0 else 3*n+1)
En pratique, le nombre d'appels imbriqués de fonction est limité, par défaut, à 1000 appels. Par exemple, l'exécution de la version récursive de fact(1000) provoque l'erreur
RuntimeError: maximum recursion depth exceeded in comparison
.
Le code pour la recherche dichotomique sur une liste de couples triés sur la clé (premier élément des couples) :
def recherche_dichotomique(s,x):
"""Recherche de l'indice de x dans s par dichotomie."""
bi, bs = 0, len(s)
m = (bi+bs)//2
while bi < bs and x != s[m][0]:
m = (bi+bs)//2
if s[m][0] < x:
bi = m+1
else:
bs = m # x est avant ou est trouvé
if len(s) <= m or s[m][0] != x: # pas trouvé
m = -1
return m
peut s'écrire récursivement :
def recherche_dichotomique(s,x,bi, bs):
"""Recherche de l'indice de x dans s par dichotomie (version récursive)."""
if bi >= bs:
res = -1
else:
m = (bi+bs)//2
if s[m][0] < x:
res = recherche_dichotomique(s,x,m+1,bs)
elif s[m][0] > x:
res = recherche_dichotomique(s,x,bi,m)
else:
res = m
return res