Tutoriel de programmation C sous Linux Partie 18 : Fonctions récursives

Indépendamment du langage de programmation que vous utilisez, à mesure que vous commencez à coder de plus en plus, vous apprenez des concepts qui rendent votre code concis et facile à lire/comprendre. Il existe plusieurs de ces concepts en C également. L’un d’eux est les ‘fonctions récursives’, que nous allons discuter ici dans cet article.

Une fonction récursive est une fonction qui s’appelle elle-même. L’appel peut être effectué directement à partir du corps de la fonction, ou indirectement à partir d’une autre fonction qui est appelée par la fonction en question.

Voici un exemple de récursion directe :

int func (int a)  
{  
    //instructions  
  
    func(a-1);  
  
    // instructions  
  
    return 0;  
}

Et voici un exemple de récursion indirecte :

int func (int a)  
{  
    //instructions  
  
    func_new(a);  
  
    // instructions  
  
    return 0;  
}  
  
int func_new(int b)  
{  
    //instructions  
  
    func(b-1);  
  
    //instructionsur  
  
    return 0;  
}

Comme déjà mentionné au début, la récursion vous aide à obtenir un code compact, qui est non seulement facile à écrire mais aussi facile à comprendre et à réviser. Prenons un exemple pour rendre cet avantage plus clair.

Je suis sûr que vous avez tous entendu parler du concept de factoriel. Pour ceux qui ne le savent pas, le factoriel est le résultat que vous obtenez lorsque vous multipliez un entier par tous les entiers positifs inférieurs à lui. Par exemple, le factoriel de 5 est 5x4x3x2x1, ce qui est égal à 120.

Voici un code simple pour trouver le factoriel d’un nombre :

#include   
  
int main()  
{  
 int a = 0, i = 0, fact = 1;  
 printf("Entrez un nombre : ");  
  
 scanf("%d", &a);  
   
 for(i=1; i<=a; i++)  
 {  
 fact = fact * i;  
   
 }  
 printf("Le factoriel du nombre est : %d ", fact);  
 return 0;  
}

Notez que ce code est juste pour vous faire savoir comment le factoriel d’un nombre peut être calculé à travers un programme C. Le programme ne prend pas en compte les cas particuliers qui peuvent affecter l’exactitude du résultat qu’il produit.

Donc, c’est l’une des nombreuses façons dont vous pouvez calculer le factoriel d’un nombre sans utiliser une fonction récursive. Maintenant, voyons un morceau de code qui utilise la récursion pour calculer un factoriel.

#include   
  
int factorial (int b)  
{  
 if(!b)  
 return 1;  
   
 return (b * factorial(b-1));  
}  
  
int main()  
{  
 int a = 0, fact = 1;  
 printf("Entrez un nombre : ");  
  
 scanf("%d", &a);  
   
 fact = factorial(a);  
   
 printf("Le factoriel du nombre est : %d ", fact);  
 return 0;  
}

Donc, vous pouvez voir, la fonction ‘factorial’ qui calcule réellement le factoriel est très compacte. Et si vous faites attention, elle est également très facile à comprendre.

Pour ceux qui ne savent pas ce qui se passe, la valeur que l’utilisateur a entrée, disons 5, est passée à la fonction ‘factorial’ lorsqu’elle est appelée pour la première fois à partir de la fonction ‘main’. À l’intérieur de la fonction ‘factorial’, il y a une vérification pour voir si la valeur d’entrée est zéro, ce qui n’est pas vrai lorsque la fonction est appelée pour la première fois avec la valeur d’entrée ‘5’.

Ensuite, l’instruction de retour contient une expression qui multiplie 5 par la valeur de retour de ‘factorial(4)’. Donc maintenant, la fonction ‘factorial’ s’exécute à nouveau, et nous atteignons l’expression suivante : return (4 * factorial(3)). Et encore une fois, ces étapes se répètent.

Donc, si vous regardez de manière large, voici comment ces appels de fonction sont empilés :

• 5 * factorial(4)
• 4 * factorial(3)
• 3 * factorial(2)
• 2 * factorial (1)
• 1 * factorial (0)

Maintenant, lorsque factorial(0) s’exécute, la condition ‘if’ dans la fonction ‘factorial’ devient vraie, et la valeur ‘1’ est retournée. Donc maintenant, voici comment les appels listés ci-dessus se complètent (comparez la dernière entrée de la liste précédente avec la première entrée de cette liste, et ainsi de suite) :

• 1 * 1
• 2 (11)
• 3 (2(1*1))
• 4 (3(2(11)))
• 5 (4 (3(2(1*1))))

Ce qui est effectivement 5 4 3 2 1, ce qui à son tour est 120, le factoriel de 5.

Donc, c’est ainsi que fonctionnent les fonctions récursives. Bien qu’il n’y ait aucun doute sur les avantages des fonctions récursives que nous avons listés jusqu’à présent, il y a aussi quelques inconvénients.

Par exemple, dans notre exemple ci-dessus, jusqu’à ce que l’appel ‘factorial(0)’ soit terminé, tous les appels ‘factorial’ précédents attendaient que le traitement de la fonction soit terminé. Sans parler du fait que les variables automatiques ou locales occupent de la mémoire pour chaque appel récursif effectué.

Donc, il n’y a effectivement aucune économie d’espace de stockage lorsque vous utilisez la récursion. De plus, il n’y a également aucune garantie que votre code sera plus rapide à exécuter. Le véritable avantage d’une fonction récursive est lorsque vous traitez des structures de données, ce que nous allons discuter plus tard dans le cadre de cette série de tutoriels C en cours.

Conclusion

Pour conclure, bien que vous ne puissiez pas utiliser fréquemment des fonctions récursives dans vos tâches de codage quotidiennes, c’est un concept dont vous devez être conscient. Essayez l’exemple que nous avons mentionné ici, et modifiez-le pour mieux comprendre le concept des fonctions récursives.