Récursivité

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. 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.

Définition :

Jusqu'à présent, nous avons programmé des fonctions simples, qui éventuellement en appelaient d'autres. Rien n'empêche d'imaginer qu'une fonction puisse s'appeler elle-même. C'est ce qu'on appelle une fonction récursive. L'intérêt d'une telle fonction peut ne pas apparaître clairement au premier abord, ou encore faire peur. D'un certain point de vue, elles sont en fait proches du formalisme de la relation de récurrence en mathématique. Bien utilisées, les fonctions récursives permettent dans certains cas d'écrire des programmes beaucoup plus lisibles, et permettent d'imaginer des algorithmes dont l'analyse sera facile et l'implantation récursive aisée.

Exemple :

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 == 0 .

#include <stdio.h>

int factoriel(int n)
{
    if (n >0){
    return n * factoriel(n-1);
    }
    else {
    return 1;
    }
}
int main()
{
    int nb = 0;
    printf("Donnez un nombre \n");
    scanf("%d", &nb);
    if (nb>=0)
    printf("le factoriel est %d \n",factoriel(nb));
    else
    printf("n'éxiste pas !! vous avez tapé un nombre négative.")
    return 0;
}
			

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