CPGE Oujda SUP

Récursivité en Langage C

Introduction

La notion de récursivité est avant tout un problème algorithmique plus qu'au niveau du langage lui même. Que ce soit en C, C++, Java, VB, Python, etc.., l'implémentation d'une fonction récursive se fera toujours plus ou moins de la même manière. Ici nous allons traiter de la récursivité avec le Langage C, telle est notre rubrique !

Mais qu'est-ce que la récursivité ? Et bien en fait d'un point de vue théorique cela reste assez simple ; il s'agit de programmes ou de fonctions d'un programme qui ont la faculté de s'appeler eux-mêmes (on entend également le terme d'auto-appel ce qui est logique). La récursivité est une manière simple et élégante de résoudre certains problèmes algorithmiques, notamment en mathématique mais cela ne s'improvise pas, il convient donc de savoir comment ce principe fonctionne.

Fonctions récursives

Les fonctions récursives comme cité plus haut, sont donc des fonctions s'appelant elles-mêmes, elles sont également un moyen rapide pour poser certains problèmes algorithmique ; nous allons voir en détails comment elles fonctionnent.

Prenons un problème simple mais auquel vous n'avez peut-être pas pensé à utiliser la récursivité: le calcul d'une factorielle. Considérons n! (qui se lit: factorielle de n) comme étant la factorielle à calculer, nous aurons ceci: 6! = 6x5x4x3x2x1. Dans cette situation, nous pouvons déjà déterminer notre règle de sortie de notre fonction récursive: la valeur 1 qui symbolise la fin de la récursion !

En effet, il faut une condition de sortie pour la fonction, mais il faut être très vigilant quant au choix de la condition, vous devrez être sûr qu'elle soit validée à un moment ou à un autre sinon c'est comme si vous créez une boucle infinie sans condition de sortie !

La règle de récursion que nous devons définir, est le calcul de la factorielle en elle même soit, si nous considérons notre exemple sur 6!, cité précédemment, nous pouvons définir notre règle de cette manière: n! = (n) (n-1) (n-2) ... (1). Nous pouvons en déduire que nous allons faire des appels en décrémentant la valeur de n à chaque appel de la fonction jusqu'à ce que n == 1 !

Vous me direz surement, quoi des maths alors que nous parlons de développement en Langage C ! Hé oui, comme cité plus haut c'est avant tout un problème algorithmique et notre exemple est un exemple mathématique comme c'est le cas pour beaucoup d'algorithmes tout de même mais je vous rassure, nous n'irons pas plus loin que ca en maths, c'est tout , nous avons ce qu'il nous faut pour créer notre fonction récursive, la voici:

Fonction récursive simple

unsigned long factoriel (int n)
{
 if (n < 0) {
 exit (EXIT_FAILURE);
 }
 else if (n == 1 || n == 0) {
 return 1L;
 }
 return n * factoriel (n - 1);
}

Nous pouvons observer ici que le dernier return est en fait l'appel récursif et nous soustrayons 1 à chaque appel jusqu'à ce que n == 1 qui est, comme décrit plus haut, notre condition de sortie.

Non, cela ne s'arrête pas là et c'est ici que nous allons voir le fonctionnement des fonctions récursives. Lorsque la fonction rencontre la condition de sortie, elle remonte dans tous les appels précédents pour calculer n avec la valeur précédemment trouvée !

Les appels des fonctions récursives sont en fait empilées (pile qui est une structure de donnée régie selon le mode LIFO: Last In First Out, Dernier Entré Premier Sorti). Chaque appel se trouve donc l'un à la suite de l'autre dans la pile du programme. Une fonction de ce type possède donc deux parcours: la phase de descente et la phase de remontée.

Voyons ceci grâce à un petit schéma:

Nous voyons très bien la phase de descente et de remontée dans la pile des appels de la fonction récursive. Ce n'est qu'au moment de la remontée, donc également au moment où la condition de sortie est vraie, que les appels enregistrés sont dépilés au fur et à mesure de la remontée. Ici pour des petits calculs cela convient très bien mais lorsqu'il s'agit de faire de plus profondes récursions, un autre type de fonction récursive existe mais n'est pas forcément connue de tout le monde, c'est la récursivité terminale, que nous allons étudier dans le prochain chapitre.

Dangers et précautions

Les fonctions récursives étant un moyen assez puissant pour résoudre certains problèmes de façon élégante, elles n'en restent pas moins dangereuses et ce pour plusieurs raisons.

IV-A. Dépassement de capacité

Une des causes assez fréquente quand vous travaillez sur de très grands nombres, est le dépassement de capacité. C'est un phénomène qui se produit lorsque vous essayez de stocker un nombre plus grand que ce que peut contenir le type de votre variable.

Il est d'usage de choisir un type approprié, même si vous êtes certains que le type que vous avez choisi ne sera jamais dépassé, utilisez tant que possible une variable pouvant contenir de plus grandes données. Ceci s'applique à tous types de données.

Evitez le type int si vous travaillez avec une fonction récursive, comme les exemples précédents pour le calcul de factoriels. Ce type est très petit et dans une fonction récursive il peut très vite arriver de le dépasser et c'est donc le plantage assuré.

Préférez-lui un type comme long pour assurer un minimum la viabilité de votre application !

Il faut noter que la taille d'un int peut être différente suivant les implémentations systèmes. En effet, par exemple en 32 bits avec un compilateur Microsoft (c), la taille d'un int est la même que celle d'un long, il est donc préférable de se renseigner sur la taille des variables suivant votre système !

IV-B. Débordement de pile (Stack Overflow)

Ceci est sans doute une des causes les plus souvent rencontrés dans le plantage de programmes avec des fonctions récursives. Nous savons que les appels récursifs de fonctions sont placés dans la pile du programme, pile qui est d'une taille assez limité car elle est fixée une fois pour toutes lors de la compilation du programme.

Dans la pile sont non seulement stockés les valeurs des variables de retour mais aussi les adresses des fonctions entre autres choses, les données sont nombreuses et un débordement de la pile peut très vite arriver ce qui provoque sans conteste une sortie anormale du programme.

Une autre méthode existe cependant ! Si vous êtes presque sûr de dépasser ce genre de limites, préférez alors une approche itérative plutôt qu'une approche récursive du problème. Une approche récursive demande beaucoup de moyens en ressources car énormément de données doivent êtres stockées dans la pile d'exécution alors qu'en revanche, une approche itérative telle une boucle for est bien moins coûteuse en terme de ressources et est bien plus sûre, sauf dans le cas d'un dépassement de capacité bien sûr !

IV-C. Forme itérative

Voyons en vitesse une possibilité de forme itérative pour notre calcul de 6! :

Forme itérative

unsigned long factoriel_iterative (unsigned int n)
{
 unsigned long ret = 1;
 unsigned int i = 1;
 
 for (i = 1; i <= n; i++)
 {
 ret *= i;
 }
 return ret;
}

Vous voyez que cela reste simple mais bien sûr, cette forme est un peu moins lisible qu'une approche récursive. L'avantage ici, réside dans le fait que vous ne risquez pas de débordement de pile mais très certainement un dépassement de capacité qui dans ce cas fait également terminer le programme en retournant le signal SIGFPE qui est une constante standard qui indique diverses opérations mathématiques incorrectes telle qu'une division par zéro ou dans notre cas un dépassement de capacité !

Code source complet avec exemple

#include <stdio.h>
#include <stdlib.h>
 * Fonction recursive simple.
 */
unsigned long factoriel (int n)
{
 if (n < 0) {
 exit (EXIT_FAILURE);
 }
 else if (n == 1 || n == 0) {
 return 1L;
 }
 return n * factoriel (n - 1);
}
 * Fonction recursive terminale.
 */
unsigned long factoriel_terminal (int n, unsigned long result)
{
 if (n < 0) {
 exit (EXIT_FAILURE);
 }
 if (n == 1) {
 return result;
 }
 else if (n == 0) {
 return 1L;
 }
 return factoriel_terminal (n - 1, n * result);
}
 * Fonction iterative.
 */
unsigned long factoriel_iterative (unsigned int n)
{
 unsigned long ret = 1;
 unsigned int i = 1;
 
 for (i = 1; i <= n; i++)
 {
 ret *= i;
 }
 return ret;
}
int main (void)
{
 unsigned long ret = 0;
 * Recursivite simple.
 */
 ret = factoriel (6);
 printf ("6! = %ld\n", ret);
  * Recursivite terminale.
 */
 ret = 0;
 ret = factoriel_terminal (6, 1);
 printf ("6! = %ld\n", ret);
 * Fonction iterative.
 */
 ret = 0;
 ret = factoriel_iterative (6);
 printf ("6! = %ld\n", ret);
 return EXIT_SUCCESS;
}