Skip to content

2 4 1 intro

Introduction à la récursivité

Voir aussi

Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein - Algorithmique - 3ème édition - Cours avec 957 exercices et 158 problèmes, Dunod, 2010, ISBN: 978-2-10-054526-1

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