Introduction à la fonction récursive en C
Le processus de répétition des éléments d'une manière similaire à ce qu'il était auparavant est connu sous le nom de récursivité. Une fonction est dite récursive si elle est appelée en elle-même. La récursivité est prise en charge par le langage de programmation C. Voici deux conditions essentielles pour implémenter la récursivité en C:
- Une condition de sortie: cette condition permet à la fonction d'identifier quand quitter cette fonction. Dans le cas où nous ne spécifions pas la condition de sortie, le code entrera dans une boucle infinie.
- Changer le compteur: Changer le compteur à chaque appel à cette fonction.
De cette façon, nous pouvons implémenter une fonction récursive dans le langage de programmation C. Ces fonctions sont utiles pour résoudre des problèmes mathématiques monétaires qui nécessitent un processus similaire appelé plusieurs fois. Des exemples de tels problèmes sont le calcul de la factorielle d'un certain nombre de générations de séries de Fibonacci.
Syntaxe:
int fun(a1)
(
If(base_condition) return val;
fun(a2);
)
Comment fonctionne la fonction récursive en C?
Les fonctions récursives sont le moyen d'implémenter l'équation en langage de programmation C. Une fonction récursive est appelée avec un argument qui lui est passé disons n, la mémoire de la pile est allouée aux variables locales ainsi qu'aux fonctions. Toutes les opérations présentes dans la fonction sont effectuées à l'aide de cette mémoire. La condition de sortie est vérifiée si elle est remplie. Lorsque le compilateur détecte un appel à une autre fonction, il alloue immédiatement une nouvelle mémoire en haut de la pile où une copie différente des mêmes variables locales et la fonction est créée. Entrez le même processus continue.
Lorsque la condition de base renvoie true, la valeur particulière transmise à la fonction appelante. La mémoire allouée à cette fonction est effacée. de même, la nouvelle valeur est calculée dans la fonction appelante et IT retourne à la fonction super appelante. De cette façon, des appels récursifs sont effectués vers la fonction delete atteint la première fonction et toute la mémoire de la pile est effacée et la sortie est renvoyée. La condition de base ou la condition de sortie n'est pas spécifiée dans la fonction, alors les appels récursifs à la fonction peuvent conduire à une boucle infinie.
Exemple de fonction récursive
Maintenant, nous allons voir les exemples de fonction récursive en C
Code:
#include
int fun(int n)
(
if(n==1) return 1 ; //exit or base condition which gives an idea when to exit this loop.
return n*fun(n-1); //function is called with n-1 as it's argument .
//The value returned is multiplied with the argument passed in calling function.
)
int main()(
int test=4;
int result =0;
result =fun(test);
printf("%d", result);//prints the output result.
)
Production:
Explication du code ci-dessus
L'exemple ci-dessus est de trouver la factorielle d'un nombre. Lorsque la fonction principale appelle fun (4), la condition de sortie (4 == 1) est d'abord vérifiée, puis 4 * fun (3) est appelée. Encore une fois, l'état de base (3 == 1) est vérifié. De même, il retournera 3 * fun (2) est appelé et cela continue jusqu'à 2 * fun (1) est appelé et où il remplit la condition de base et retourne 1 puis la fonction appelante retourne 2 * 1 puis, 3 * 2 * 1 et dès le premier appel 4 * 3 * 2 * 1 est renvoyé. Il en résulte donc que la fonction principale stocke 24 et l'imprime en sortie.
Allocation de mémoire de la fonction récursive
Chaque appel à une fonction en langage c entraîne une allocation de mémoire en haut d'une pile. Lorsqu'une fonction récursive est appelée, de la mémoire lui est allouée en haut de la mémoire qui a été allouée à la fonction appelante avec toutes les différentes copies de variables locales sont créées pour chaque appel à la fonction.
Quelle est la condition de base atteinte, la mémoire allouée à la fonction est détruite et le pointeur revient à la fonction appelante? ce processus est répété puis la première fonction appelante et enfin, la mémoire de la pile devient vide.
Dans l'exemple donné ci-dessus pour calculer la factorielle d'un nombre ci-dessous est le scénario d'allocation de mémoire.
Étape 1
Étape 2
Étape 3
Étape 4
Étape - 5
Étape - 6
Étape - 7
Étape - 8
Étape - 9
Types de récursivité
Il existe deux types de récursivité dans la programmation C qui sont donnés ci-dessous:
1. Récursion de queue et sans queue
Le type de récursion ci-dessus est expliqué ci-dessous:
- Récursivité de la queue
Il s'agit d'un type d'appel récursif de fonction récursive dans la fonction qui est la dernière action à effectuer dans la définition de la fonction. Signifie que l'appel récursif se produit après que tout le reste de la logique dans la fonction est implémenté.
L'utilisation d'une récursion de queue dans notre programme à hans est la performance du programme et réduit également l'utilisation de la mémoire de la fonction so. Il en est ainsi car, comme une autre logique de la fonction a été implémentée, la mémoire allouée à la fonction appelante peut être supprimée de la pile et réutilisée.
Code:
int fun1(n)(
printf(“the result is “);
return fun1(n-1);
)
void main()
(
fun1(4);
)
- Récursion sans queue
Ce type de collage récursif récursif fait au milieu de la définition de la fonction. La récursivité des pantalons pour hommes est terminée et les valeurs renvoyées à la fonction appelante nécessitent davantage d'étapes, de sorte que la mémoire ne peut pas être effacée.
Code:
int fun1(n)(
printf(“the result is “);
return n* fun1(n-1);
)
void main()(
fun1(4);
)
2. Récursivité directe et indirecte
Le type de récursion ci-dessus est expliqué ci-dessous:
- Récursivité indirecte
On dit qu'une récursion indirecte se produit lorsqu'une fonction particulière est appelée de manière récursive par le biais d'une autre fonction.
Code:
int fun1()(
fun2();
)
int fun2()(
fun1(); // calling the procedure recursively using another function.
)
void main()(
fun1();
)
- Récursivité directe
On dit que la récursivité directe se produit lorsque l'appel récursif à la fonction est effectué dans sa propre définition. '
Code:
int fun1()(
fun1();
)
void main()(
fun1();
)
Conclusion
On peut facilement conclure que les fonctions récursives sont tout au plus importantes pour résoudre des problèmes mathématiques qui nécessitent une méthode similaire, toute la logique devant être implémentée à plusieurs reprises jusqu'à ce qu'une condition de sortie soit remplie. De nombreux problèmes tels que les tours de Hanoi, les traversées d'arbres, le calcul de la profondeur des graphiques.
Il est important de mentionner une condition de base pour la fonction récursive. Les besoins en mémoire et en temps sont plus importants pour le programme récursif que pour les programmes itératifs, ils doivent donc être utilisés avec prudence.
Articles recommandés
Ceci est un guide d'exemple de fonction récursive en C. Ici, nous discutons du travail, des types, de l'allocation de mémoire et des exemples de fonction récursive en C. Vous pouvez également consulter les articles suivants pour en savoir plus -
- Tableaux en programmation C
- Palindrome en programme C
- Modèles en programmation C
- C vs C ++
- Palindrome en JavaScript
- Guide de la série Fibonacci en JavaScript