Récursivité

Vous avez peut être entendu parlé en mathématiques du raisonnement par récurrence. Si c'est le cas, vous constaterez des similitudes entre la notion mathématique de récurrence et la récursivité en informatique.

Algorithme récursif

Un algorithme récursif est algorithme qui résoud un problème en calculant des solutions plus petites du même problème.

Fonction récursive

Une fonction est dite récursive si elle s'appelle dans sa propre définition.

Par exemple, supposons que je veuille calculer la factorielle d'un entier naturel \(n\). Sa définition est :

Factorielle

Soit \(n \in \mathbb{N}\).

\(n! = n \times (n -1) \times (n-2) \times (n-3) \times ... \times 1\)

Par exemple \(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\).
A noter que par définition \(0! = 1\)

On voit ici qu'il faut arrêter nos calculs lorsqu'au bout "on arrive à" multiplier par 1.

Cas d'arrêt

Bien penser à ajouter un cas d'arrêt, on dit aussi cas de base, sinon votre fonction récursive ne s'arrête jamais. En général on commence même à réfléchir d'abord au cas d'arrêt avant d'implémenter l'algorithme, cela permet de bien comprendre l'algorithme à implémenter.

Dans le cas de la factorielle vous voyez qu'on peut décomposer ce calcul en sous calculs qui ont la même "logique" (on dit la même "structure" en informatique).

On pourrait calculer \(5 \times 4\) et multiplier ce résultat à \(3 \times 2\) que l'on multiplie à \(2 \times 1\) et là on ajouterai une condition d'arrêt puisque l'entier utilisé est 1.

En Python cela donnerait :

def factorielle(n):
   if n == 1:
       return n
   else:
       return n * factorielle(n - 1)

On voit que la définition de la fonction Python est très proche de la définition mathématiques.

La définition itérative de la factorielle donne le même résulat :

def factorielle(n):
    resultat = 1
    for i in range(n, 1, -1):
        resultat *= i
    return resultat

On peut se demander alors, quel est l'intérêt de passer par la définition récursive si on peut faire la même chose de de manière itérative ?

D'une part on pourrait répondre que dans le cas de la factorielle la définition récursive est quasiment la même que celle que l'on a donné en mathématique et donc plus simple, plus "naturelle", plus élégante même.

Mais cela n'est pas suffisant car d'une part dans cet exemple la définition itérative n'est pas très éloignée de la définition mathématique et d'autre part en tant qu'informatien(ne) on ne peut pas se limiter à des considérations esthétiques. On doit aussi prendre en compte des problèmes d'efficacité, de complexité en temps et en espace mémoir

Mais généralement il est important de noter que certains problèmes peuvent être résolu plus facilement si on utilise un algorithme récursif. Par exemple dans la résolution de problèmes de structures arborescentes ou de graphes que nous verrons par la suite, nous verrons que la résolution récursive aboutit à une solution très "naturelle", adaptée aux problèmes liés à ces structures.

Pile mémoire et complexité

Vous vous souvenez (je l'espère) du type abstrait qui correspond à la pile. Et bien, lorsque vous effectuez des appels récursifs pour une fonction donnée ces appels avec les arguments passés et les variables locales sont stockés en mémoire sous la forme d'une pile :

Vous avez peut être entendu parlé de débordement de pile ou "stack overflow" en anglais. Et bien certains programmes récursifs peuvent générer ce type d'erreur, soit parce que la fonction est correctement implémentée de manière récursive mais qu'elle n'est pas suffisamment optimisée (nous verrons plus tard des méthodes pour optimiser certains appels récursifs), soit parce que le cas d'arrêt est mal géré, et donc les appels finissent par occuper toute la place en mémoire vive.