Récursivité

Introduction

La récursivité est un concept fondamental en informatique qui permet de résoudre des problèmes en les décomposant en sous-problèmes de même nature. Elle est particulièrement utile pour traiter des structures de données hiérarchiques telles que les arbres. Dans cette leçon, nous allons explorer la notion de récursivité, apprendre à écrire et analyser des programmes récursifs, et comprendre pourquoi cette approche est souvent privilégiée pour manipuler des structures arborescentes.

Comprendre la récursivité

Principe de la récursivité

La récursivité repose sur l'idée qu'une fonction peut s'appeler elle-même pour résoudre un problème. Une fonction récursive doit comporter deux éléments essentiels : un cas de base et un cas récursif. Le cas de base est une condition qui permet de terminer la récursion, tandis que le cas récursif est l'étape où la fonction s'appelle elle-même avec des arguments modifiés.

Prenons un exemple simple : le calcul de la factorielle d'un nombre entier $n$, noté $n!$. La définition mathématique de la factorielle est :

• $0! = 1$

• $n! = n \times (n-1)!$ pour $n > 0$

En termes de programmation, cela se traduit par la fonction récursive suivante :

Dans cet exemple, le cas de base est atteint lorsque $n$ est égal à zéro, et la fonction retourne 1. Pour tout autre cas, la fonction s'appelle elle-même avec l'argument $n - 1$, multipliant le résultat par $n$.

Exemple intermédiaire : somme des éléments d’une liste

Avant d’appliquer la récursivité à des structures arborescentes, il est utile de l’illustrer sur une structure linéaire comme une liste. Voici un exemple de fonction qui calcule la somme des éléments d’une liste d’entiers :

Ce code suit la même logique que pour la factorielle : on définit un cas de base (liste vide) et on traite le premier élément en appelant la fonction sur le reste de la liste.

Analyse d'une fonction récursive

Analyser une fonction récursive implique de vérifier que chaque appel récursif se rapproche du cas de base, garantissant ainsi la terminaison de la fonction. Dans les exemples précédents, chaque appel réduit la taille du problème : la valeur de $n$ ou la longueur de la liste.

Il est crucial d’éviter les appels récursifs infinis, qui surviennent lorsque le cas de base est absent ou mal formulé.

Remarque : Chaque appel récursif consomme de la mémoire en empilant un nouveau cadre d’exécution sur la pile d’appels. Une récursion trop profonde peut entraîner un dépassement de pile (« stack overflow »). En Python, la profondeur maximale est limitée par défaut à environ 1000 appels récursifs, ce qui peut poser problème pour certaines structures très profondes.

Comparaison récursif / itératif

Voici un tableau synthétique des avantages et inconvénients de la récursivité par rapport à une approche itérative :

Intérêt de la récursivité pour les structures arborescentes

Les arbres en informatique

Un arbre est une structure de données hiérarchique composée de nœuds, où chaque nœud peut avoir plusieurs enfants, mais un seul parent. Le nœud supérieur est appelé racine. Les feuilles sont les nœuds qui n’ont pas d’enfant.

Les arbres binaires, dans lesquels chaque nœud possède au plus deux enfants (souvent appelés gauche et droit), sont particulièrement utilisés en NSI.

Modélisation en Python

En Python, un arbre binaire peut être modélisé à l’aide d’une classe :

Cette classe permet de représenter chaque nœud et d’accéder récursivement aux sous-arbres gauche et droit.

Exemple de construction d’un arbre :

Parcours d’un arbre binaire

La récursivité est particulièrement adaptée pour manipuler les arbres, car elle permet de traiter chaque sous-arbre de manière indépendante, en appliquant la même logique à chaque niveau de la structure. Le parcours en profondeur (DFS, Depth First Search) constitue une famille de parcours, parmi lesquels on distingue :

• Le parcours préfixe (préordre) : on traite le nœud courant, puis le sous-arbre gauche, puis le sous-arbre droit.

• Le parcours infixe (inordre) : on traite d’abord le sous-arbre gauche, puis le nœud courant, puis le sous-arbre droit.

• Le parcours suffixe (postordre) : on traite d’abord les deux sous-arbres, puis le nœud courant.

Voici un exemple de parcours préfixe récursif :

Ce traitement est naturellement récursif car chaque sous-arbre est lui-même un arbre.

Parcours en largeur

Le parcours en largeur (BFS, Breadth First Search), quant à lui, ne s’implémente pas de manière récursive : il s’effectue en parcourant tous les nœuds d’un même niveau avant de passer au niveau suivant. Il repose généralement sur l’utilisation d’une file.

Conclusion

La récursivité consiste à définir un problème en termes de sous-problèmes plus simples de même nature.

Une fonction récursive comprend un cas de base et un cas récursif.

Elle est particulièrement adaptée aux structures hiérarchiques comme les arbres.

Les parcours en profondeur incluent les ordres préfixe, infixe et suffixe.

Le parcours en largeur est une autre stratégie, généralement implémentée de manière itérative.

La récursivité utilise la pile d’appels, ce qui a un coût en mémoire. Python limite par défaut la profondeur de récursion à environ 1000 appels.