Comprendre les fonctions récursives en Python

En tant que programmeur ou programmeuse professionnel·le, vous devez maîtriser les bases : variables, structures conditionnelles, types de données, modificateurs d’accès, appels de fonctions, portées, etc. Quel que soit le type de programme que vous écrivez — middleware, développement web ou data science — ces fondamentaux sont incontournables. Vous êtes d’abord programmeur, puis data scientist, développeur web, ingénieur en apprentissage automatique, etc.

Parmi ces notions de base figure la récursivité, essentielle lorsque vous écrivez des fonctions d’un certain type. Vous connaissez sans doute déjà la définition : « On parle de récursivité lorsqu’une fonction s’appelle elle-même. » Mais que se passe-t-il sous le capot ? Comment la mémoire physique est-elle impactée par la récursivité ? Peut-on transformer n’importe quelle fonction en fonction récursive ? Dans ce tutoriel, vous trouverez des réponses claires à ces questions.

Anatomie d’une fonction récursive :

Vous avez probablement rencontré le terme récursivité durant vos études en informatique. Dans cette section, nous allons revisiter ces concepts de façon plus concrète. C’est parti.

Repartons de la définition : « On parle de récursivité lorsqu’une fonction s’appelle elle-même. » Prenons un exemple pour l’illustrer :

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}

On voit que la fonction A() s’appelle elle-même. C’est un exemple de récursivité, et A() est une fonction récursive.

Étudions maintenant quelques bases d’une fonction récursive.

Notions de base d’une fonction récursive :

Une fonction récursive doit comporter deux éléments :

• Une relation de récurrence
• Une condition d’arrêt

Reprenons le code ci-dessus pour comprendre ces points. Clairement, la fonction suit une relation de récurrence spécifique :

$n\le 1$ est la condition d’arrêt / condition d’ancrage / condition de base. Lorsqu’elle est satisfaite, la récursivité s’arrête. Il est impératif de la préciser, sinon la fonction entrera dans une boucle infinie.

(Notez que l’extrait de code ci-dessus n’adhère à aucun langage particulier. L’objectif est simplement d’illustrer une fonction récursive.)

Vous vous demandez peut-être pourquoi écrire une fonction récursive s’il existe des alternatives plus simples. Oui, tracer une récursivité peut être déroutant au début, mais avec la pratique, vous verrez qu’elle apporte élégance et lisibilité. La récursivité ne nécessite pas de variables supplémentaires pour s’exécuter, mais exige une condition d’arrêt correcte. Souvent, identifier cette condition d’arrêt est la partie la plus délicate. Comme toujours, c’est en pratiquant que l’on progresse. Plus loin dans ce tutoriel, vous verrez à quel point un programme peut être concis et élégant grâce à la récursivité, comparé à des approches plus classiques. Passons maintenant à la représentation mémoire d’une fonction récursive.

Représentation mémoire d’une fonction récursive :

Dans cette section, vous allez voir comment les fonctions récursives s’inscrivent en mémoire à l’aide de arbres et de piles. Reprenons la fonction récursive A() pour illustrer cela :

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}

Commençons par la représentation sous forme d’arbre. Cela peut sembler abstrait, mais c’est très simple. Si vous deviez dessiner chaque appel de fonction comme un arbre, à quoi cela ressemblerait-il ?

À quelque chose comme ceci :

Quelques points à noter :

• La fonction est appelée avec A(3) et produit 4 appels (3+1). De façon générale, si A(n) est appelée, le total des appels sera de (n+1).
• Les appels P() représentent les impressions produites par print(n).
• La fonction s’arrête à l’appel A(0) car l’instruction if reçoit alors n < 1, ce qui met fin à la récursivité.

Nous avons commencé par l’arbre car cette représentation est utile pour projeter la fonction sur une pile (stack). Voyons cela.

(Une pile est une structure de données suivant l’ordre dernier entré, premier sorti — LIFO.)

Pour la représentation avec une pile, il faut parcourir l’arbre de haut en bas puis de gauche à droite. L’image suivante clarifie ce parcours.

Interprétons cet « arbre parcouru ». Rappelez-vous qu’une pile propose deux opérations : 1) Push, pour empiler un élément ; 2) Pop, pour le dépiler.

Lancez le parcours de haut en bas puis de gauche à droite :

• À chaque appel de fonction, on empile sur la pile.
• À chaque appel print() / P(), on affiche simplement l’élément correspondant.

Voici les éléments empilés à l’issue du parcours de haut en bas, de A(3) à A(0) :

Vient ensuite la seconde moitié du parcours, c’est-à-dire de gauche à droite. Chaque fois que vous rencontrez un appel de fonction pour la seconde fois, vous le dépilez. Fait marquant : le premier élément dépilé (A(0)) est le dernier qui avait été empilé (LIFO). Sur le trajet, vous rencontrez trois appels P() : P(1), P(2) et P(3). Vous les affichez dans l’ordre d’arrivée pendant le parcours. L’ordre sera :

À la fin du parcours, la pile est entièrement vide. Pour mieux visualiser les opérations de dépilement, voici l’état de la pile une fois totalement vidée.

Vous venez de voir comment représenter en mémoire une fonction récursive simple à l’aide d’un arbre et d’une pile. Passons maintenant au traçage d’une récursivité.

Tracer une récursivité :

Dans cette section, vous allez apprendre à tracer méthodiquement une récursivité. Considérez la fonction suivante :

void A(n){
    if(n>0){
        print(n-1);
        A(n-1);
    }
}

Point crucial : à chaque appel de fonction, un enregistrement d’activation est créé en mémoire. Il contient les variables locales de la fonction et un pointeur d’instruction (qui indique la prochaine étape à exécuter lorsque l’exécution revient dans cette fonction). Supposons qu’une fonction main() appelle A() via A(3). Numérotons les lignes de A() à partir du if pour plus de clarté :

void A(n){
    1. if(n>0)
    2. {
        3. print(n-1);
        4. A(n-1);
    5. }
}

Les enregistrements d’activation ressemblent à ceci :

Comme indiqué, chaque fonction possède sa copie des variables locales et du pointeur d’instruction (ici, le numéro de ligne). Après A(0), la fonction A() se termine et les dépilements s’enchaînent. Remarquez que la pile est dessinée horizontalement, mais il s’agit du même mécanisme que précédemment. Au fur et à mesure que les enregistrements sont empilés, les impressions ont lieu, et les valeurs suivantes sont affichées :

Les pointeurs d’instruction sont essentiels, car le flot d’exécution revient souvent dans la même fonction avec des valeurs différentes. Ils garantissent la bonne reprise au bon endroit. Vous pouvez suivre ce même processus de traçage en utilisant la représentation en arbre.

Passons maintenant à l’analyse espace-temps d’une fonction récursive.

Analyse espace-temps d’une fonction récursive :

DataCamp propose un excellent article sur l’analyse asymptotique en Python. Nous vous conseillons de le consulter avant de poursuivre. Rappelons rapidement ce que recouvrent l’analyse en temps et l’analyse en espace d’une fonction (aussi appelées complexité temporelle et complexité spatiale) :

Pour une entrée donnée, une fonction produit un résultat. Combien de temps cela prend-il ? La complexité en temps approxime cette durée, aussi appelée temps d’exécution. De même, la complexité en espace approxime la mémoire requise par la fonction pour une entrée donnée. Pourquoi ces mesures sont-elles utiles ?

• Plutôt que d’exécuter une fonction sur toute une plage d’entrées de tailles variables, vous pouvez estimer son comportement à l’échelle.
• Si deux fonctions remplissent le même objectif, laquelle choisir ? Vous les comparerez via leurs complexités en temps et en espace pour retenir la plus efficace.

Analysons maintenant la complexité d’une fonction récursive simple.

void A(n){
    if(n>1) // Anchor condition
    {
       return A(n-1);
    }
}

Commençons par la complexité en temps. Supposons que le temps total pris par A() soit $T(n)$. Alors $T(n)$ est la somme du temps nécessaire pour comparer si n est supérieur à 1 et du temps d’exécution de A(n-1). On peut écrire :

1 représente le coût de la comparaison (toute constante conviendrait). Quel sera alors le temps (en termes de $T$) pour A(n-1) ?

De même,

et ainsi de suite.

En observant ces équations, on voit qu’elles s’enchaînent. En substituant successivement, on obtient :

$T(n)$ = 1 + (1 + $T(n-2)$) = 2 + $T(n-2)$ = 3 + $T(n-3)$ = … = k + $T(n-k)$ (après k itérations)

Quand la fonction s’arrête-t-elle ? D’après la condition d’ancrage :

Supposons qu’après k étapes, la fonction s’arrête. Alors :

$n - k = 1 => k = n - 1$

En remplaçant k (= n - 1) dans $T(n) = k + T(n-k)$ :

$T(n) = (n-1) + T(n-(n-1))$
$=> T(n) = (n-1) + T(1)$
$=> T(n) = n-1 + 1 = n$ // Pour T(1), seule la comparaison est effectuée

Par les règles de l’analyse asymptotique, $T(n) = n$ se note $T(n) = \mathcal{O}(n)$. La complexité temporelle (pire cas) de la fonction est donc $\mathcal{O}(n)$.

Prenez un instant pour revoir chaque étape. Il est vivement conseillé de le refaire au papier-crayon.

Pour la complexité en espace, c’est simple : la fonction ne crée pas de variables supplémentaires, mais chaque appel s’empile en mémoire. On conclut donc à une complexité spatiale de $\mathcal{O}(n)$.

Mettons maintenant tout cela en pratique avec une implémentation récursive en Python.

Implémenter une fonction récursive simple en Python :

Nous allons écrire une fonction récursive qui calcule la factorielle d’un nombre, puis une version itérative. Allons-y.

# Fonction récursive factorial_recursion()

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

# Appel de la fonction

num = 7
print("The factorial of ",num," is ",factorial_recursion(num))

The factorial of  7  is  5040

Vous vous souvenez des deux ingrédients clés d’une fonction récursive ?

• Relation de récurrence
• Condition d’arrêt

Ici, la relation de récurrence est :

$f(n) = n!$
$f(n) = n * f(n-1)$, etc.

La condition d’arrêt est lorsque n est égal à 1.

Simple, n’est-ce pas ?

Implémentons maintenant la version itérative.

def factorial_iterative(num):
    factorial = 1
    if num < 0:
        print("Sorry, factorial does not exist for negative numbers")
    elif num == 0:
        print("The factorial of 0 is 1")
    else:
        for i in range(1,num + 1):
           factorial = factorial*i
        print("The factorial of",num,"is",factorial)

factorial_iterative(7)

The factorial of 7 is 5040

La différence entre les deux versions saute aux yeux. La version récursive est plus élégante et concise, n’est-ce pas ?

Félicitations !

Vous êtes arrivé·e au bout. Dans ce tutoriel, vous avez étudié en profondeur les fonctions récursives : des bases jusqu’à l’analyse des complexités en temps et en espace. Vous avez vu en quoi la récursivité peut être particulièrement adaptée à certains problèmes. Vous devriez maintenant être en mesure de résoudre des problèmes (munis d’une relation de récurrence et d’une condition d’arrêt) à l’aide de la récursivité. Vous pouvez, par exemple, écrire une fonction pour calculer les nombres de Fibonacci dans un intervalle donné.

Nous vous encourageons à résoudre des classiques comme la recherche dichotomique (Binary Search), le tri fusion (Merge Sort), la tour de Hanoï, etc., en récursif, puis à en analyser la complexité. Vous progresserez ainsi en tant que programmeur ou programmeuse.

Pour une introduction, ce que nous avons couvert suffit largement. Pour aller plus loin, consultez :

• Recursion and Dictionaries par le Prof. Grimson
• Programmation dynamique pour optimiser les fonctions récursives

Pour en savoir plus sur Python, suivez le cours gratuit de DataCamp : Intro to Python for Data Science.