Récursivité est le processus de définition de quelque chose en termes delui-même. En ce qui concerne la programmation Java, la récursivité est l'attribut qui permet à une méthode de s'appeler elle-même. Une méthode qui s'appelle elle-même est dite récursive et Java prend en charge la récursivité.
Au début, cela peut sembler une boucle sans fin,et il semble que notre méthode ne finira jamais. Cela peut être vrai dans certains cas, mais dans la pratique, nous pouvons vérifier si une certaine condition est vraie et dans ce cas, quitter (revenir de) notre méthode. Le cas dans lequel nous terminons notre récursivité est appelé un cas de base. De plus, tout comme dans une boucle, nous devons modifier une valeur et avancer progressivement vers notre scénario de base.
Chaque récursivité doit avoir les caractéristiques suivantes:
- Un cas de base simple pour lequel nous avons une solution et une valeur de retour.
- Un moyen de rapprocher notre problème du cas de base. c'est-à-dire un moyen de couper une partie du problème pour obtenir un problème un peu plus simple.
- Un appel récursif qui retransmet le problème le plus simple à la méthode.
Les avantages
Le principal des méthodes récursives est qu'elles peuvent êtreutilisé pour créer des versions plus claires et plus simples de plusieurs algorithmes que leurs parents itératifs. Par exemple, l'algorithme de tri QuickSort est assez difficile à implémenter de manière itérative.
Désavantages
Les versions récursives de nombreuses routines peuvent exécuter unun peu plus lentement que l'équivalent itératif en raison de la surcharge supplémentaire des appels de fonction supplémentaires. De nombreux appels récursifs à une méthode peuvent entraîner un dépassement de pile. Du fait du stockage des paramètres et des variables locales, il est possible que la pile soit épuisée. Si cela se produit, le système d'exécution java provoquera une exception. Cependant, vous n'aurez probablement pas à vous en préoccuper à moins qu'une routine récursive ne s'exécute.
Par exemple:
int myFactorial(int integer) {
if( integer == 1) {
return 1;
}
else {
return(integer*(myFactorial(integer-1);
}
}La récursivité de la queue est définie comme se produisantl'appel récursif est à la fin de l'instruction récursive. Ce n'est pas le cas avec ma solution factorielle ci-dessus. Il est utile de remarquer quand l'algorithme utilise la récursion de queue car dans un tel cas, l'algorithme peut généralement être réécrit pour utiliser l'itération à la place. En fait, le compilateur convertira (ou du moins devrait) convertir le programme récursif en programme itératif. Cela élimine le problème potentiel de débordement de pile.
Ce n'est pas le cas avec la récursion de la tête, ou lorsquela fonction s'appelle récursivement à différents endroits comme dans la solution Towers of Hanoi. Bien sûr, même dans ces cas, nous pourrions également supprimer la récursivité en utilisant notre propre pile et en simulant essentiellement le fonctionnement de la récursivité.
Dans mon exemple de factorielle au-dessus du compilateurdevra appeler la fonction récursive avant de faire la multiplication car elle doit résoudre la valeur (de retour) de la fonction avant de pouvoir terminer la multiplication. Ainsi, l'ordre d'exécution sera la récursion «tête», c'est-à-dire que la récursivité se produit avant les autres opérations.
Pour convertir cela en récursion de queue, nous devons obtenirtoute la multiplication est terminée et résolue avant d'appeler récursivement la fonction. Nous devons forcer l'ordre de fonctionnement afin de ne pas attendre la multiplication avant de revenir. Si nous le faisons, le cadre de pile peut être libéré.
Auparavant, vous avez vu notre programme Java pour calculer la factorielle d'un entier.
La bonne façon de faire une factorielle récursive de queue est la suivante:
int factorial(int number) {
if(number == 0) {
return 1;
}
factorial_i(number, 1);
}
int factorial_i(int currentNumber, int sum) {
if(currentNumber == 1) {
return sum;
} else {
return factorial_i(currentNumber - 1, sum*currentNumber);
}
}Notez que dans le retour d'appelfactorial_i (currentNumber - 1, sum * currentNumber); les deux paramètres sont immédiatement résolvables. Nous pouvons calculer ce que chaque paramètre est sans attendre le retour d'un appel de fonction récursive. Ce n'est pas le cas avec la version précédente de factorielle. Cette rationalisation permet au compilateur de minimiser l'utilisation de la pile comme expliqué ci-dessus.
Vous pouvez également prendre le numéro de l'utilisateur comme argument de ligne de commande.
Programme de récursivité Java
class Factorial{
int fact(int n){
int result;
if ( n ==1)
return 1;
result = fact (n-1) * n;
return result;
}
}
class Recursion{
public static void main (String args[]){
Factorial f =new Factorial();
System.out.println("Factorial of 3 is " + f.fact(3));
System.out.println("Factorial of 4 is " + f.fact(4));
System.out.println("Factorial of 5 is " + f.fact(5));
}
}Production
Explication du code Java et de la sortie
Si vous n'êtes pas familier avec les méthodes récursives, le fonctionnement de fait() peut sembler un peu déroutant. Voici comment cela fonctionne. Quand fait() est appelée avec un argument de 1, la fonction renvoie 1; sinon il retourne le produit de fait (n-1) * n. d'évaluer cette expression, fait() est appelé avec n-1. Ce processus se répète jusqu'à n est égal à 1 et les appels à la méthode commencent à revenir.
Pour mieux comprendre comment fait() fonctionne, voyons un court exemple. Lorsque vous calculez la factorielle de 3, le premier appel à fait() provoquera un deuxième appel avec un argument de 2. Cette invocation provoquera fait() être appelé une troisième fois avec un argument de 2. Cet appel renverra 1, qui sera ensuite appelé une troisième fois avec un argument de 1. Cet appel renverra 1, qui est ensuite multiplié par 2 (la valeur de n dans la deuxième invocation). Ce résultat (qui est 2) est ensuite renvoyé à l'invocation d'origine de fait() et multipliez par 3 (la valeur d'origine de n). Cela donne la réponse, 6. Vous pourriez trouver intéressant d'insérer println () déclarations en fait() qui montrera à quel niveau chaque appel est et quelles sont les réponses intermédiaires.
Lorsqu'une méthode s'appelle elle-même, de nouvelles variables localeset les paramètres se voient allouer du stockage sur la pile, et le code de la méthode est exécuté avec ces nouvelles variables depuis le début. Un appel récursif ne fait pas une nouvelle copie de la méthode. Seuls les arguments sont nouveaux. Lorsque chaque appel récursif revient, les anciennes variables et paramètres locaux sont supprimés de la pile et l'exécution reprend au point de l'appel à l'intérieur de la méthode.
Ensuite, nous apprendrons comment gérer Tableau en Java.
Découvrez des tutoriels plus utiles et des directives définitives sur la programmation Java ici.
commentaires