 |
| La récursivité - SAGProfProg - LANGAGE C - Programmation, Développement web, Développement d'application, Génie Logiciel, Langage de programmation, Application web, Tutos, Informatique, Système d'information, Administration d'application |
La récursivité est le processus qui apparaît lorsqu'une fonction appelle une copie d'elle-même pour travailler sur un problème plus petit. Toute fonction qui s'appelle elle-même est appelée fonction récursive, et de tels appels de fonction sont appelés appels récursifs. La récursivité implique plusieurs nombres d'appels récursifs. Cependant, il est important d'imposer une condition de terminaison de la récursivité. Le code récursif est plus court que le code itératif mais il est difficile à comprendre.
La récursivité ne peut pas être appliquée à tous les problèmes, mais elle est plus utile pour les tâches qui peuvent être définies en termes de sous-tâches similaires. Par exemple, la récursivité peut être appliquée aux problèmes de tri, de recherche et de traversée.
Généralement, les solutions itératives sont plus efficaces que la récursivité puisque l'appel de fonction est toujours en surcharge. Tout problème qui peut être résolu de manière récursive, peut aussi être résolu de manière itérative. Cependant, certains problèmes sont mieux adaptés pour être résolus par la récursivité, par exemple, la tour de Hanoï, les séries de Fibonacci, la recherche factorielle, etc.
Dans l'exemple suivant, la récursivité est utilisée pour calculer la factorielle d'un nombre.
#include <stdio.h>
int fact(int);
int main()
{
int n,f ;
printf("Entrez le nombre dont vous voulez calculer la factorielle ?");
scanf("%d",&n);
f = fact(n);
printf("factoriel = %d",f);
}
int fact(int n)
{
if(n==0)
{
return 0 ;
}
else if ( n == 1)
{
return 1 ;
}
else
{
return n*fact(n-1);
}
}
Production
Nous pouvons comprendre le programme ci-dessus de l'appel de méthode récursive par la figure ci-dessous :
Fonction récursive
Une fonction récursive exécute les tâches en les divisant en sous-tâches. Il existe une condition de terminaison définie dans la fonction qui est satisfaite par une sous-tâche spécifique. Après cela, la récursivité s'arrête et le résultat final est renvoyé par la fonction.
Le cas dans lequel la fonction ne se reproduit pas est appelé le cas de base, tandis que les instances où la fonction continue de s'appeler pour effectuer une sous-tâche sont appelées le cas récursif. Toutes les fonctions récursives peuvent être écrites en utilisant ce format.
Le pseudo-code pour écrire toute fonction récursive est donné ci-dessous.
if(test_for_base)
{
return une_valeur ;
}
else if (test_for_another_base)
{
return une_autre_valeur ;
}
else
{
// Déclarations ;
appel récursif ;
}
Exemple de récursivité en C
Voyons un exemple pour trouver le nième terme de la série de Fibonacci.
#include<stdio.h>
int fibonacci(int);
void main()
{
int n,f ;
printf("Entrez la valeur de n?");
scanf("%d",&n);
f = fibonacci(n);
printf("%d",f);
}
int fibonacci (int n)
{
if (n==0)
{
return 0 ;
}
else if (n == 1)
{
return 1 ;
}
else
{
return fibonacci(n-1)+fibonacci(n-2);
}
}
Production
Allocation de mémoire de la méthode récursive
Chaque appel récursif crée une nouvelle copie de cette méthode dans la mémoire. Une fois que certaines données sont renvoyées par la méthode, la copie est supprimée de la mémoire. Étant donné que toutes les variables et autres éléments déclarés à l'intérieur de la fonction sont stockés dans la pile, une pile distincte est donc conservée à chaque appel récursif. Une fois la valeur renvoyée par la fonction correspondante, la pile est détruite. La récursivité implique tellement de complexité dans la résolution et le suivi des valeurs à chaque appel récursif. Par conséquent, nous devons maintenir la pile et suivre les valeurs des variables définies dans la pile.
Considérons l'exemple suivant pour comprendre l'allocation de mémoire des fonctions récursives.
int affichage(int n)
{
if(n == 0)
return 0 ; // condition de terminaison
else
{
printf("%d",n);
return affichage(n-1); // appel récursif
}
}
Explication
Examinons cette fonction récursive pour n = 4. Tout d'abord, toutes les piles sont maintenues, ce qui imprime la valeur correspondante de n jusqu'à ce que n devienne 0. Une fois la condition de terminaison atteinte, les piles sont détruites une par une en renvoyant 0 à son appelant. empiler. Considérez l'image suivante pour plus d'informations concernant la trace de pile pour les fonctions récursives.
Aucun commentaire:
Enregistrer un commentaire