• Détente
• Informatique
• Mathématiques
• Projets

Introduction à la récursivité

Ce bref article est dédié à la récursivité. Nous tenterons de la découvrir en suivant une approche pragmatique, celle du programmeur en quête d'un outil puissant, mais sans négliger pour autant l'aspect mathématique de cette notion.

Définition

Tout objet est dit récursif s'il se définit à partir de lui-même. Contrairement à ce que l'on peut penser à la lecture de cette définition, la récursivité est un concept naturel que rencontrons parfois au quotidien : voir cette page de Pierre Weis sur La récursivité et la vie pour quelques exemples.

Une fonction est donc dite récursive si elle comporte dans son corps au moins un appel à elle-même. Elle doit aussi contenir une condition terminale (aussi appelée base de récursivité) spécifiant un état où l'appel récursif ne sera pas effectué, faute de quoi le programme bouclera sans fin d'appel en appel.

Ce concept peut paraître déroutant de prime abord, mais ses applications pratiques sont nombreuses. Étudions un premier exemple de fonction récursive, dénuée d'intérêt mais simple :

int fonction_recursive(unsigned entier)
{
    // Condition terminale
    if (entier <= 0)
        return 0;
 
    // Appel récursif
    fonction_recursive(entier - 1);
}

Cette fonction retourne toujours zéro, mais lorsqu'on lui passe un entier N comme argument, elle le fera en effectuant N appels récursifs. Oui, cet fonction est inutile, et on peut aisément lui trouver un équivalent itératif, c'est-à-dire utilisant une boucle, ou calculant le résultat directement. Mais c'est un premier pas. Après avoir étudié quelques aspects mathématiques de la récursivité, nous aborderons des exemples plus concrets.

Pour comprendre la récursivité, il faut d'abord comprendre la récursivité.

Exemples de définitions récursives

Entiers naturels

En mathématiques, on préfère employer le terme de récurrence à celui de récursivité, mais nous ne détaillerons pas ici la subtilité entre ces deux termes. De nombreuses propriétés mathématiques sont récurrentes, par exemple cette définition des entiers naturels :

1. 0 est un entier naturel ;
2. Si k est un entier naturel, alors (k + 1) est un entier naturel.

Cette définition permet de construire l'ensemble des entiers naturels, mais ce qui nous intéresse particulièrement ici est la structure de la récurrence : on commence par définir une base de récurrence pour laquelle on connaît un résultat (difficile de nier que 0 est un entier !), puis on détermine le résultat de problèmes plus importants (1 est-il entier ? 42 est-il entier ?) en se ramenant au cas connu. Même si la réponse à la question "un nombre est-il entier ?" peut parraître triviale pour un être humain (et pour une machine ?) nous verrons des cas moins évidents où une approche récursive simplifie les choses.

La fonction factorielle

La définition mathématique de la fonction factorielle est la suivante (n! désigne la factorielle de l'entier positif n) :

1. 0! = 1 ;
2. Pour n entier naturel non-nul, n! = n * (n - 1)!

Cette fonction a de nombreuses applications pratiques, notamment en probabilités. On remarquera à nouveau la structure de base puis généralisation.

La suite de Fibonacci

Cette suite célèbre à la croissance exponentielle est définie de manière récursive comme suit :

1. Les deux premiers éléments de la suite sont égaux à 1 ;
2. Chaque élément de la suite est égal à la somme de ses deux prédécésseurs.

Implémentation de fonctions récursives

Après ces définitions mathématiques, nous allons nous lancer dans la mise en forme de telles fonctions récursives. Le code sera fourni en pseudo-code et en langage C, libre à vous de l'adapter dans votre langage favoris. Je tiens tout de même à préciser que certains langages ne supportent pas la récursivité, comme le Fortran et les langages plutôt anciens. Avant de lire la suite, essayez de coder vous-même une première fonction récursive, pour vous entraîner comme pour tester votre compilateur.

La fonction factorielle

Première approche

Voyons ce dont nous avons besoin pour cette factorielle : la condition terminale est claire, si on atteint 0 il suffit de retourner 1. Par ailleurs, la fonction pourra comporter un seul argument : l'entier naturel N, que nous traduirons par un entier (non-signé). Nous nommerons notre fonction fact et, dans le cas où N est non-nul, nous retournerons (N * fact(N - 1)) : il s'agit de la définition, toute la définition, et rien que la définition, que nous nous contentons de traduire.

Pseudo-code

FACT(N)
    Si (N = 0)
        Retourner 1
    Retourner N * FACT(N - 1)

Langage C

unsigned fact(unsigned N)
{
    if (N == 0)
        return 1;
 
    return (N * fact(N - 1));
}

Ces premières définitions sont simples et fonctionnent. Cependant, elles sont extrèmement gourmandes en ressources machine. Avant d'aller plus loin nous allons donc devoir aborder quelques notions techniques quant à la manière dont les machines appliquent la récursivité.

Il faut savoir qu'un ordinateur utilise une pile, ou stack (voire l'article consacré aux piles), pour stocker les données lors des appels de fonctions. Une pile applique le principe LIFO (Last-In-First-Out) : le dernier élément ajouté est le premier à être retiré. Ainsi, lorsque vous appelez une fonction, ses objets sont alloués dans la pile, et celle-ci se voit empillée. Une fois sont appel terminé, celle-ci est dépilée et la mémoire est à nouveau libre. Alors, lors de l'appel à une fonction récursive, les appels récursifs sont eux aussi empilés successivement jusqu'à atteindre la condition terminale, après quoi ils sont tous dépilés dans l'ordre inverse. Si l'occupation en mémoire est trop importante, on risque d'"exploser" la pile, c'est-à-dire de dépasser sa capacité. Dans notre cas, un appel à fact(1000000000) a de grandes chances d'engendrer une telle erreur. Imaginez ne serait-ce que l'appel à fact(5) représenté ci-dessous :

// PHASE DE DESCENTE RECURSIVE
Appel à fact(5)
    Appel à fact(4)
        Appel à fact(3)
            Appel à fact(2)
                Appel à fact(1)
                    Appel à fact(0)
                        // CONDITION TERMINALE
                        Retour de la valeur 1
                    // PHASE DE REMONTÉE
                    Retour de la valeur 1
                Retour de la valeur 2
            Retour de la valeur 6
        Retour de la valeur 24
    Retour de la valeur 120

Sachant que chaque appel alloue au moins un entier, et qu'un entier représente 4 octets en mémoire, au moment de l'appel à fact(0), 24 octets ont été alloués. Imaginez dans le cas de N = 1.000.000.000 : il faudrait allouer à peu près 4 Go de mémoire avant de retourner le résultat ! Tout ceci pour vous mettre en garde face à l'occupation en mémoire des appels récursifs, qui peut vite devenir catastrophique. Il existe une solution pour éviter une telle occupation : la récursivité terminale.

Une optimisation remarquable

L'idée d'une fonction récursive terminale est de supprimer la phase de remontée, et ce en réutilisant le même emplacement dans la pile pour la fonction appelante que pour son appel récursif. Attention cependant, cette optimisation n'est pas supportée par tous les compilateurs. Pour ce faire, il s'agit que le dernier appel de la fonction soit son appel récursif, sans qu'elle ait à en manipuler le résultat comme ci-dessus. En effet, le calcul (N * fact(N - 1)) nécessite de connaître la valeur de fact(N - 1) avant de la multiplier par N, ce qui nécessite donc une phase de remontée. Dans la plupart des cas, il suffit d'ajouter un second argument à la fonction, comportant le résultat temporaire lors de l'appel à la fonction.

Essayez de coder une version récursive terminale de cette fonction avant de passer à la suite.

Pseudo-code

FACT(N, a = 1)
    Si (N = 0) ou (N = 1)
        Retourner(a)
    Retourner(FACT(N - 1, N * a))

Langage C

unsigned fact(unsigned N = 1, unsigned a = 1)
{
    if (N == 1 || N == 0)
        return a;
 
    return fact(N - 1, a * N);
}

Vous remarquerez que, comme (1! = 0! = 1), on a ajouté 1 à la base de récursivité de la fonction, en vous laissant le soin de comprendre pourquoi. Si on étudie le comportement d'un ordinateur lors de l'appel à fact(5) pour cette fonction, on obtient désormais le schéma suivant :

Appel à fact(5)
Appel à fact(4)
Appel à fact(3)
Appel à fact(2)
Appel à fact(1)
Retour de la valeur 120

L'utilisation mémoire est moindre, de même que le temps d'exécution, étant donné qu'e la phase de remontée à été supprimée. Il n'est pas toujours possible d'appliquer une récursivité terminale, mais c'est une optimisation à prendre en compte lors de la rédaction de fonctions récursives.

La version itérative

Une version itérative, par opposition à la forme récusrive, construit le résultat à partir d'un unique appel à la fonction. Généralements, l'utilisation de boucles et instructions conditionnelles suffit amplement, le "goto" étant, je vous le rappelle, à proscrire. Nous ne pouvons donc pas faire l'impasse sur une solution itérative, qui serait tout aussi efficace, voire beaucoup plus.

Je vous propose le code suivant, sachant qu'il est possible de partir de 0 (ou 1) comme de partir de N. [[:4 Langage C ]]

unsigned fact_from_1(unsigned N)
{
  unsigned result = 1;
 
  for (unsigned i = 1; i <= N; i++)
    result *= i;
 
  return result;
}
 
unsigned int fact_from_N(unsigned N)
{
  unsigned result = 1;
 
  for (; N >= 1; N--)
    result *= N;
 
  return result;
}

La seconde version, qui nécessite un entier de moins, est très proche de la version récursive terminale, et techniquement elle se comporte de la même façon (le compilateur optimise souvent les appels récursifs terminaux de la sorte). Vous remarquerez néanmoins que la définition récursive terminale et plus claire et compréhensible, et par la même plus intuitive. Ce dernier point est sans doute un avantage majeur de la récursivité : elle peut permettre de coder rapidement des solutions instinctives (voire bourrines), aisément optimisables et adaptables par la suite.

La suite de Fibonacci

Pour découvrir plus avant la suite de Fibonacci, voir l'article dédié à cette suite.

Implémentation et dynamisation

En dehors de la récursivité terminale, il existe d'autres méthodes pour optimiser une fonction récursive. Pour en illustrer quelques unes, nous allons définir une fonction qui, pour un entier N donné, retourne la valeur de l'entier d'indice i de la suite de Fibonacci (que l'on note généralement Fi). Encore une fois, essayez de coder une version récursive vous même avant de lire la solution, aussi violente soit-elle : nous verrons les optimisations ci-après.

Attention à un point : on part ici du principe que le premier élément de la suite est F0.

Pseudo-code

F(N)
    Si (N = 1) ou (N = 0)
        Retourner(1)
    Retourner(F(N - 1) + F(N - 2))

Langage C

unsigned F(unsigned N)
{
    if (N == 1 || N == 0)
        return 1;
 
    return (F(N - 1) + F(N - 2));
}

Cette première approche a un énorme désavantage : des éléments seront recalculés de nombreuses fois. Par exemple, pour un appel avec N = 5 :

Appel à F(5)
    Appel à F(4)
        Appel à F(3)
            Appel à F(2)
                Appel à F(1)
                Retour de 1
            Retour de 2
        Retour de 3
        Appel à F(2)
            Appel à F(1)
            Retour de 1
        Retour de 2
    Retour de 5
    Appel à F(3)
        Appel à F(2)
            Appel à F(1)
            Retour de 1
        Retour de 2
    Retour de 3
Retour de 8

Ainsi, F(3), F(2) et F(1) sont recalculés plusieurs fois. Là encore, nous avons pris un cas assez simple pour éviter un schéma trop complexe, mais imaginez le nombre d'appels recalculés inutilement pour un appel avec N = 1.000.000.000 ! Cette solution n'est donc pas convenable, et nous allons tenter d'optimiser la version récursive avant de coder une version itérative.

Pour ne pas recalculer des éléments, il suffit de stocker les résultats dans un tableau ou toute autre structure de donnée à accès direct. Dans notre cas, nous allons partir du fait que vous n'aurez pas à calculer d'élément supérieurs à un million, pour une simple raison d'occupation mémoire. Si tel n'était pas le cas, il vous faudrait opter pour des structures de stockage dynamiques (par exemple, des vecteurs standards) ou passer à une version itérative.

L'idée est de vérifier à chaque appel récursif si le résultat n'a pas déjà été calculé en testant la valeur correspondante dans le tableau. Si le résultat n'a pas été calculé, on calcule sa valeur, on la stocke, puis on la renvoie. Dans le cas contraire, il suffit de retourner la valeur stockée. Ce principe s'appelle la dynamisation.

Dans le code suivant, les valeurs du tableau save sont initialisés à 0.

Langage C

unsigned save[1000000];
 
unsigned F(unsigned N)
{
    if (N == 1 || N == 0)
        return 1;
 
    if (save[N] != 0)
        return save[N];
 
    save[N] = (F(N - 2) + F(N - 1));
 
    return save[N];
}

Ainsi, si l'on se représente les appels récursifs pour N = 5, on obtient le résultat suivant :

Appel à F(5)
    Appel à F(4)
        Appel à F(3)
            Appel à F(2)
                Appel à F(1)
                Retour de 1
            Retour de 2
        Retour de 3
        Appel à F(2)
        Retour de 2
    Retour de 5
    Appel à F(3)
    Retour de 3
Retour de 8

Le gain en performances est d'autant plus significatif que la valeur de N est élevée.

Toujours mieux en itératif

Ici encore, l'exemple de la suite de Fibonacci sert à illustrer un certain type d'optimisation, mais une solution itérative demeure plus efficace (quoique l'écart en termes de performances est ici beaucoup plus faible que précédemment). Par exemple, une approche itérative du problème peut s'implémenter comme suit :

Langage C

unsigned F(unsigned N)
{
    unsigned prev_1 = 1;
    unsigned prev_2 = 1;
    unsigned result;
 
    for (unsigned i = 2; i <= N; i++) {
        result  = prev_1 + prev_2;
        prev_2 = prev_1;
        prev_1 = result;
    }
 
    return result;
}

Conclusion

Ainsi s'achève cette brève introduction à la notion de récursivité. Nous avons ici abordé les concepts de base sur des exemples courrants. Dans les articles suivants, nous aborderons des problèmes où les solutions itératives, toujours plus performantes, seront beaucoup moins instinctives que des versions récursives. Nous aborderons également les structures récursives, comme les abres, non moins importantes.

Avant de chercher plus loin, trouver d'autres exemples de fonctions récursives et les implémenter soi-même constitue un très bon entraînement.