recursion java tutorial with examples
Ce didacticiel approfondi sur la récursivité en Java explique ce qu'est la récursivité avec des exemples, des types et des concepts associés. Il couvre également la récursivité contre l'itération:
De nos tutoriels précédents en Java, nous avons vu l'approche itérative dans laquelle nous déclarons une boucle puis traversons une structure de données de manière itérative en prenant un élément à la fois.
Nous avons également vu le flux conditionnel où encore une fois nous gardons une variable de boucle et répétons un morceau de code jusqu'à ce que la variable de boucle remplisse la condition. En ce qui concerne les appels de fonction, nous avons également exploré l'approche itérative des appels de fonction.
=> Consultez TOUS les didacticiels Java ici.
java passe le tableau à la méthode par valeur
Dans ce tutoriel, nous discuterons d'une approche différente de la programmation, à savoir l'approche récursive.
Ce que vous apprendrez:
- Qu'est-ce que la récursivité en Java?
- Récursivité vs itération en Java
- Conclusion
Qu'est-ce que la récursivité en Java?
La récursivité est un processus par lequel une fonction ou une méthode s'appelle encore et encore. Cette fonction qui est appelée à maintes reprises, directement ou indirectement, est appelée «fonction récursive».
Nous verrons différents exemples pour comprendre la récursivité. Voyons maintenant la syntaxe de la récursivité.
Syntaxe de récursivité
Toute méthode qui implémente la récursivité comporte deux parties de base:
- Appel de méthode qui peut s'appeler, c'est-à-dire récursif
- Une condition préalable qui arrêtera la récursivité.
Notez qu'une condition préalable est nécessaire pour toute méthode récursive car, si nous ne cassons pas la récursion, elle continuera à s'exécuter indéfiniment et entraînera un débordement de pile.
La syntaxe générale de la récursivité est la suivante:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Notez que la condition préalable est également appelée condition de base. Nous discuterons plus en détail de la condition de base dans la section suivante.
Comprendre la récursivité en Java
Dans cette section, nous allons essayer de comprendre le processus de récursivité et voir comment il se déroule. Nous allons en apprendre davantage sur la condition de base, le débordement de pile et voir comment un problème particulier peut être résolu avec la récursivité et d'autres détails similaires.
Condition de base de récursivité
Lors de l'écriture du programme récursif, nous devons d'abord fournir la solution pour le cas de base. Ensuite, nous exprimons le plus gros problème en termes de problèmes plus petits.
En tant que Exemple, on peut prendre un problème classique de calcul de la factorielle d'un nombre. Étant donné un nombre n, nous devons trouver une factorielle de n notée n!
Maintenant, implémentons le programme pour calculer la n factorielle (n!) En utilisant la récursivité.
public class Main{ static int fact(int n) { if (n == 1) // base condition return 1; else return n*fact(n-1); } public static void main(String() args) { int result = fact(10); System.out.println('10! = ' + result); } }Production
Dans ce programme, nous pouvons voir que la condition (n<=1) is the base condition and when this condition is reached, the function returns 1. The else part of the function is the recursive call. But every time the recursive method is called, n is decremented by 1.
Ainsi, nous pouvons conclure que finalement la valeur de n deviendra 1 ou inférieure à 1 et à ce stade, la méthode retournera la valeur 1. Cette condition de base sera atteinte et la fonction s'arrêtera. Notez que la valeur de n peut être n'importe quoi tant qu'elle satisfait la condition de base.
Résolution de problèmes à l'aide de la récursivité
L'idée de base derrière l'utilisation de la récursivité est d'exprimer le plus gros problème en termes de problèmes plus petits. De plus, nous devons ajouter une ou plusieurs conditions de base afin de pouvoir sortir de la récursivité.
Cela a déjà été démontré dans l'exemple factoriel ci-dessus. Dans ce programme, nous avons exprimé la n factorielle (n!) En termes de valeurs plus petites et avons une condition de base (n<=1) so that when n reaches 1, we can quit the recursive method.
Erreur de débordement de pile dans la récursivité
Nous sommes conscients que lorsqu'une méthode ou une fonction est appelée, l'état de la fonction est stocké sur la pile et est récupéré lorsque la fonction revient. La pile est également utilisée pour la méthode récursive.
Mais dans le cas de la récursivité, un problème peut survenir si nous ne définissons pas la condition de base ou lorsque la condition de base n'est pas atteinte ou exécutée. Si cette situation se produit, le débordement de pile peut survenir.
Prenons l'exemple ci-dessous de notation factorielle.
Ici, nous avons donné une condition de base erronée, n == 100.
public class Main { static int fact(int n) { if (n == 100) // base condition resulting in stack overflow return 1; else return n*fact(n-1); } public static void main(String() args) { int result = fact(10); System.out.println('10! = ' + result); } }Ainsi, lorsque n> 100, la méthode retournera 1 mais la récursivité ne s'arrêtera pas. La valeur de n continuera à décrémenter indéfiniment car il n'y a pas d'autre condition pour l'arrêter. Cela continuera jusqu'à ce que la pile déborde.
Un autre cas sera lorsque la valeur de n<100. In this case, as well the method will never execute the base condition and result in a stack overflow.
Exemples de récursivité en Java
Dans cette section, nous implémenterons les exemples suivants en utilisant la récursivité.
# 1) Série Fibonacci utilisant la récursivité
La série de Fibonacci est donnée par,
1,1,2,3,5,8,13,21,34,55, ...
La séquence ci-dessus montre que l'élément actuel est la somme des deux éléments précédents. En outre, le premier élément de la série Fibonacci est 1.
Donc, en général, si n est le nombre courant, alors il est donné par la somme de (n-1) et (n-2). Comme l'élément courant est exprimé en termes d'éléments précédents, nous pouvons exprimer ce problème en utilisant la récursivité.
Le programme de mise en œuvre de la série Fibonacci est donné ci-dessous:
public class Main { //method to calculate fibonacci series static int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); } public static void main(String() args) { int number = 10; //print first 10 numbers of fibonacci series System.out.println ('Fibonacci Series: First 10 numbers:'); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + ' '); } } } Production
# 2) Vérifier si un nombre est un palindrome en utilisant la récursivité
Un palindrome est une séquence qui est égale quand on la lit de gauche à droite ou de droite à gauche.
Étant donné un nombre 121, nous voyons que lorsque nous le lisons de gauche à droite et de droite à gauche, il est égal. Le numéro 121 est donc un palindrome.
meilleur logiciel espion pour les téléphones portables Android
Prenons un autre nombre, 1242. Lorsque nous le lisons de gauche à droite, il est 1242 et, lu de droite à gauche, il se lit comme 2421. Ce n’est donc pas un palindrome.
Nous implémentons le programme palindrome en inversant les chiffres des nombres et comparons récursivement le nombre donné à sa représentation inversée.
Le programme ci-dessous implémente le programme pour vérifier le palindrome.
import java.io.*; import java.util.*; public class Main { // check if num contains only one digit public static int oneDigit(int num) { if ((num >= 0) && (num <10)) return 1; else return 0; } //palindrome utility function public static int isPalindrome_util (int num, int revNum) throws Exception { // base condition; return if num=0 if (num == 0) { return revNum; } else { //call utility function recursively revNum = isPalindrome_util(num / 10, revNum); } // Check if first digit of num and revNum are equal if (num % 10 == revNum % 10) { // if yes, revNum will move with num return revNum / 10; } else { // exit throw new Exception(); } } //method to check if a given number is palindrome using palindrome utility function public static int isPalindrome(int num) throws Exception { if (num < 0) num = (-num); int revNum = (num); return isPalindrome_util(num, revNum); } public static void main(String args()) { int n = 1242; try { isPalindrome(n); System.out.println('Yes, the given number ' + n + ' is a palindrome.'); } catch (Exception e) { System.out.println('No, the given number ' + n + ' is not a palindrome.'); } n = 1221; try { isPalindrome(n); System.out.println('Yes, the given number ' + n + ' is a palindrome.'); } catch (Exception e) { System.out.println('No, the given number ' + n + ' is not a palindrome.'); } } }Production
# 3) Récursivité de chaîne inverse Java
Étant donné une chaîne «Hello», nous devons l'inverser pour que la chaîne résultante soit «olleH».
Ceci est fait en utilisant la récursivité. À partir du dernier caractère de la chaîne, nous imprimons chaque caractère de manière récursive jusqu'à ce que tous les caractères de la chaîne soient épuisés.
Le programme ci-dessous utilise la récursivité pour inverser une chaîne donnée.
class String_Reverse { //recursive method to reverse a given string void reverseString(String str) { //base condition; return if string is null or with 1 or less character if ((str==null)||(str.length() <= 1)) System.out.println(str); else { //recursively print each character in the string from the end System.out.print(str.charAt(str.length()-1)); reverseString(str.substring(0,str.length()-1)); } } } class Main{ public static void main(String() args) { String inputstr = 'SoftwareTestingHelp'; System.out.println('The given string: ' + inputstr); String_Reverse obj = new String_Reverse(); System.out.print('The reversed string: '); obj.reverseString(inputstr); } } Production
# 4) Récursivité Java de recherche binaire
Un algorithme de recherche binaire est un algorithme de recherche célèbre. Dans cet algorithme, étant donné un tableau trié de n éléments, nous recherchons dans ce tableau l'élément clé donné. Au début, nous divisons le tableau en deux moitiés en trouvant l'élément médian du tableau.
Ensuite, selon que la clé au milieu, nous limitons notre recherche dans la première ou la seconde moitié du tableau. De cette façon, le même processus est répété jusqu'à ce que l'emplacement des éléments clés soit trouvé.
Nous implémenterons cet algorithme en utilisant la récursivité ici.
import java.util.*; class Binary_Search { // recursive binary search int binarySearch(int numArray(), int left, int right, int key) { if (right >= left) { //calculate mid of the array int mid = left + (right - left) / 2; // if the key is at mid, return mid if (numArray(mid) == key) return mid; // if key key) return binarySearch(numArray, left, mid - 1, key); // Else recursively search in the right subarray return binarySearch(numArray, mid + 1, right, key); } // no elements in the array, return -1 return -1; } } class Main{ public static void main(String args()) { Binary_Search ob = new Binary_Search(); //declare and print the array int numArray() = { 4,6,12,16,22}; System.out.println('The given array : ' + Arrays.toString(numArray)); int len = numArray.length; //length of the array int key = 16; //key to be searched int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println('Element ' + key + ' not present'); else System.out.println('Element ' + key + ' found at index ' + result); } } Production
# 5) Trouver la valeur minimale dans un tableau à l'aide de la récursivité
En utilisant la récursivité, nous pouvons également trouver la valeur minimale dans le tableau.
Le programme Java pour trouver la valeur minimale dans le tableau est donné ci-dessous.
import java.util.*; class Main { static int getMin(int numArray(), int i, int n) { //return first element if only one element or minimum of the array elements return (n == 1) ? numArray(i) : Math.min(numArray(i), getMin(numArray,i + 1 , n - 1)); } public static void main(String() args) { int numArray() = { 7,32,64,2,10,23 }; System.out.println('Given Array : ' + Arrays.toString(numArray)); int n = numArray.length; System.out.print('Minimum element of array: ' + getMin(numArray, 0, n) + '
'); } }Production
meilleur éditeur de texte pour les fenêtres python
Voici quelques exemples de récursivité. En dehors de ces exemples, de nombreux autres problèmes dans le logiciel peuvent être implémentés à l'aide de techniques récursives.
Types de récursivité
La récursivité est de deux types en fonction du moment où l'appel est effectué à la méthode récursive.
Elles sont:
# 1) Récurrence de la queue
Lorsque l'appel à la méthode récursive est la dernière instruction exécutée à l'intérieur de la méthode récursive, on l'appelle «Tail Recursion».
Dans la récursivité de queue, l'instruction d'appel récursive est généralement exécutée avec l'instruction return de la méthode.
La syntaxe générale de la récursivité de queue est donnée ci-dessous:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } # 2) Récursivité de la tête
La récursivité de tête est toute approche récursive qui n'est pas une récursivité de queue. Ainsi, même la récursivité générale est une récursion anticipée.
La syntaxe de la récursivité de la tête est la suivante:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Récursivité vs itération en Java
| Récursion | Itération |
|---|---|
| La complexité temporelle est très élevée. | La complexité temporelle est relativement inférieure. |
| La récursivité est un processus dans lequel une méthode s'appelle elle-même à plusieurs reprises jusqu'à ce qu'une condition de base soit remplie. | L'itération est un processus par lequel un morceau de code est exécuté à plusieurs reprises un nombre fini de fois ou jusqu'à ce qu'une condition soit remplie. |
| Est l'application pour les fonctions. | S'applique aux boucles. |
| Fonctionne bien pour une taille de code plus petite. | Fonctionne bien pour une taille de code plus grande. |
| Utilise plus de mémoire à mesure que chaque appel récursif est poussé vers la pile | Comparativement moins de mémoire est utilisée. |
| Difficile à déboguer et à maintenir | Plus facile à déboguer et à maintenir |
| Entraîne un débordement de pile si la condition de base n'est pas spécifiée ou n'est pas atteinte. | Peut s'exécuter indéfiniment mais arrêtera finalement l'exécution avec des erreurs de mémoire |
Questions fréquemment posées
Q # 1) Comment fonctionne la récursivité en Java?
Répondre: En récursivité, la fonction récursive s'appelle elle-même à plusieurs reprises jusqu'à ce qu'une condition de base soit satisfaite. La mémoire de la fonction appelée est poussée sur la pile en haut de la mémoire de la fonction appelante. Pour chaque appel de fonction, une copie distincte des variables locales est effectuée.
Q # 2) Pourquoi la récursivité est-elle utilisée?
Répondre: La récursivité est utilisée pour résoudre les problèmes qui peuvent être décomposés en plus petits et l'ensemble du problème peut être exprimé en termes d'un problème plus petit.
La récursivité est également utilisée pour les problèmes qui sont trop complexes pour être résolus à l'aide d'une approche itérative. Outre les problèmes pour lesquels la complexité temporelle n'est pas un problème, utilisez la récursivité.
Q # 3) Quels sont les avantages de la récursivité?
Répondre:
Les avantages de la récursivité comprennent:
- La récursivité réduit les appels redondants de fonction.
- La récursivité nous permet de résoudre facilement les problèmes par rapport à l'approche itérative.
Q # 4) Lequel est le meilleur - récursion ou itération?
Répondre: La récursivité effectue des appels répétés jusqu'à ce que la fonction de base soit atteinte. Il y a donc une surcharge de mémoire car une mémoire pour chaque appel de fonction est poussée sur la pile.
L'itération, en revanche, n'a pas beaucoup de surcharge de mémoire. L'exécution de la récursivité est plus lente que l'approche itérative. La récursivité réduit la taille du code tandis que l'approche itérative agrandit le code.
Q # 5) Quels sont les avantages de la récursivité par rapport à l'itération?
Répondre:
- La récursivité rend le code plus clair et plus court.
- La récursivité est meilleure que l'approche itérative pour des problèmes comme la tour de Hanoi, les traversées d'arbres, etc.
- Comme chaque appel de fonction a de la mémoire poussée sur la pile, la récursivité utilise plus de mémoire.
- Les performances de récursivité sont plus lentes que l'approche itérative.
Conclusion
La récursivité est un concept très important dans le logiciel quel que soit le langage de programmation. La récursivité est principalement utilisée pour résoudre des problèmes de structure de données comme les tours de Hanoi, les traversées d'arbres, les listes chaînées, etc.
Nous avons exploré tout sur la récursivité dans ce tutoriel. Nous avons également implémenté de nombreux exemples de programmation pour une meilleure compréhension du concept.
=> Lisez la série de formations Easy Java.
lecture recommandée
- Récursivité en C ++
- Java Iterator: Apprenez à utiliser les itérateurs en Java avec des exemples
- Interface ListIterator en Java avec des exemples
- Tutoriel JAVA pour les débutants: plus de 100 tutoriels vidéo Java pratiques
- Tutoriel Java For Loop avec des exemples de programmes
- Java While Loop - Tutoriel avec des exemples de programmation
- Java Do While Loop - Tutoriel avec des exemples
- Jagged Array In Java - Tutoriel avec des exemples