Ce tutoriel approfondi sur la récursion en Java explique ce qu'est la récursion avec des exemples, des types et des concepts connexes. Il couvre également la récursion par rapport à l'itération :
Dans nos précédents tutoriels en Java, nous avons vu l'approche itérative dans laquelle nous déclarons une boucle et parcourons ensuite une structure de données de manière itérative en prenant un élément à la fois.
Nous avons également vu le flux conditionnel dans lequel nous conservons 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 pour les appels de fonction.
Dans ce tutoriel, nous aborderons une approche différente de la programmation, à savoir l'approche récursive.
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 elle-même encore et encore. Cette fonction qui est appelée encore et encore, directement ou indirectement, est appelée "fonction récursive".
Nous verrons plusieurs exemples pour comprendre la récursivité. Voyons maintenant la syntaxe de la récursion.
Syntaxe de récursion
Toute méthode qui met en œuvre la récursivité comporte deux parties essentielles :
- Appel d'une méthode qui peut s'appeler elle-même, c'est-à-dire récursive
- 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 mettons pas fin à la récursivité, celle-ci continuera à fonctionner à l'infini et entraînera un débordement de la pile.
La syntaxe générale de la récursion est la suivante :
methodName (T parameters...) { if (precondition == true) //precondition ou condition de base { return result ; } return methodName (T parameters...) ; //appel récursif } Il convient de noter que la condition préalable est également appelée condition de base. Nous reviendrons plus en détail sur la condition de base dans la section suivante.
Comprendre la récursivité en Java
Dans cette section, nous essaierons de comprendre le processus de récursion et de voir comment il se déroule. Nous apprendrons ce qu'est la condition de base, le débordement de pile, et nous verrons comment un problème particulier peut être résolu à l'aide de la récursion et d'autres détails de ce type.
Recursion Condition de base
Lors de l'écriture du programme récursif, nous devons d'abord fournir la solution pour le cas de base. Ensuite, nous exprimons le problème principal en termes de problèmes plus petits.
En tant que exemple, Nous pouvons 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 !
Implémentons maintenant le programme pour calculer la factorielle n (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) ; } } Sortie
Dans ce programme, nous pouvons voir que la condition (n<=1) est la condition de base et que lorsque cette condition est atteinte, la fonction renvoie 1. La partie else de la fonction est l'appel récursif. Mais à chaque fois que la méthode récursive est appelée, n est décrémenté de 1.
Nous pouvons donc conclure qu'en fin de compte, la valeur de n deviendra 1 ou inférieure à 1 et qu'à ce moment-là, la méthode renverra 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 de l'utilisation de la récursivité est d'exprimer un problème plus important en termes de problèmes plus petits. Nous devons également ajouter une ou plusieurs conditions de base afin de pouvoir sortir de la récursivité.
Dans ce programme, nous avons exprimé la factorielle n (n !) en termes de valeurs plus petites et nous avions une condition de base (n <=1) de sorte que lorsque n atteint 1, nous pouvons quitter la méthode récursive.
Erreur de dépassement de pile dans la récursion
Nous savons 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 si la condition de base n'est pas atteinte ou exécutée d'une manière ou d'une autre. Si cette situation se produit, un débordement de la pile peut survenir.
Prenons l'exemple suivant 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 renvoie 1 mais la récursivité ne s'arrête pas. La valeur de n continue à se décrémenter indéfiniment car il n'y a pas d'autre condition pour l'arrêter. Cela continue jusqu'à ce que la pile déborde.
Un autre cas se présente lorsque la valeur de n <; 100. Dans ce cas également, la méthode n'exécutera jamais la condition de base et entraînera un débordement de la pile.
Exemples de récursion en Java
Dans cette section, nous allons mettre en œuvre les exemples suivants en utilisant la récursivité.
#1) Série de 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 et que le premier élément de la série de Fibonacci est 1.
Ainsi, en général, si n est le nombre actuel, il est donné par la somme de (n-1) et (n-2). Comme l'élément actuel est exprimé en termes d'éléments précédents, nous pouvons exprimer ce problème à l'aide de la récursivité.
Le programme permettant de mettre en œuvre la série de Fibonacci est donné ci-dessous :
public class Main { //méthode de calcul de la série de fibonacci 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 ; //imprime les 10 premiers nombres de la série de fibonacci System.out.println ("Série de fibonacci : 10 premiers nombres :") ; for (int i = 1 ; i <= number ; i++) { System.out.print(fibonacci(i) + " ") ;} } } Sortie
#2) Vérifier si un nombre est un palindrome en utilisant la récursivité
Un palindrome est une séquence qui est égale lorsqu'on la lit de gauche à droite ou de droite à gauche.
Étant donné le nombre 121, nous constatons que lorsque nous le lisons de gauche à droite et de droite à gauche, il est égal. Le nombre 121 est donc un palindrome.
Prenons un autre nombre, 1242. Lorsque nous le lisons de gauche à droite, nous obtenons 1242 et lorsque nous le lisons de droite à gauche, nous obtenons 2421. Il ne s'agit donc pas d'un palindrome.
Nous implémentons le programme palindrome en inversant les chiffres des nombres et en comparant récursivement le nombre donné à sa représentation inversée.
Le programme ci-dessous implémente le programme de vérification du palindrome.
import java.io.* ; import java.util.* ; public class Main { // vérifier si le numéro ne contient qu'un seul chiffre public static int oneDigit(int num) { if ((num>= 0) && ; (num <; 10)) return 1 ; else return 0 ; } //fonction utilitairepalindrome public static int isPalindrome_util (int num, int revNum) throws Exception { // condition de base ; return if num=0 if (num == 0) { return revNum ; } else { //callfonction utilitaire récursivement revNum = isPalindrome_util(num / 10, revNum) ; } // Vérifier si le premier chiffre de num et revNum sont égaux if (num % 10 == revNum % 10) { // si oui, revNum sera déplacé avec num return revNum / 10 ; } else { // exit throw new Exception() ; } } //méthode pour vérifier si un nombre donné est palindrome en utilisant la fonction utilitaire palindrome public static int isPalindrome(int num) throwsException { 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("Oui, le nombre donné " + n + " est un palindrome.") ; } catch (Exception e) { System.out.println("Non, le nombre donné " + n + " n'est pas un palindrome.") ; } n = 1221 ; try { isPalindrome(n) ;System.out.println("Oui, le nombre donné " + n + " est un palindrome.") ; } catch (Exception e) { System.out.println("Non, le nombre donné " + n + " n'est pas un palindrome.") ; } } Sortie
#3) Récursion inversée de chaînes de caractères Java
Étant donné une chaîne de caractères "Hello", nous devons l'inverser de sorte que la chaîne résultante soit "olleH".
En partant 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 de caractères donnée.
class String_Reverse { //méthode récursive pour inverser une chaîne donnée void reverseString(String str) { //condition de base ; retour si la chaîne est nulle ou contient 1 caractère ou moins if ((str==null)} } } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp" ; System.out.println("La chaîne donnée : " + inputstr) ; String_Reverse obj = new String_Reverse() ; System.out.print("La chaîne inversée : ") ; obj.reverseString(inputstr) ; } } } Sortie
#4) Recherche binaire Récursion Java
L'algorithme de recherche binaire est un algorithme de recherche bien connu. 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 central du tableau.
Ensuite, en fonction de l'emplacement de la clé, nous limitons notre recherche à la première ou à la deuxième 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 allons mettre en œuvre cet algorithme en utilisant la récursivité.
import java.util.* ; class Binary_Search { // recherche binaire récursive int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { //calculer le milieu du tableau int mid = left + (right - left) / 2 ; // si la clé est au milieu, retourner mid if (numArray[mid] == key) return mid ; // si clé key) return binarySearch(numArray, left, mid - 1, key) ; // Sinon rechercher récursivement dans le tableau int mid.sous-réseau de droite return binarySearch(numArray, mid + 1, right, key) ; } // aucun élément dans le tableau, return -1 return -1 ; } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search() ; //déclarer et imprimer le tableau int numArray[] = { 4,6,12,16,22} ; System.out.println("Le tableau donné : " + Arrays.toString(numArray)) ; int len = numArray.length ; //longueur du tableauint key = 16 ; //clé à rechercher 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) ; } }. Sortie
#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 du tableau.
Le programme Java permettant de 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) { //renvoie le premier élément s'il n'y en a qu'un ou le minimum des éléments du tableau 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("Élément minimum du tableau : " + getMin(numArray, 0, n) + "\n") ; } } } Sortie
Il s'agit là de quelques exemples de récursivité. Outre ces exemples, de nombreux autres problèmes logiciels peuvent être résolus à l'aide de techniques récursives.
Types de récursion
Il existe deux types de récursion, en fonction du moment où la méthode récursive est appelée.
Il s'agit de
#1) Récursion 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 parle de "récursivité de queue".
Dans la récursivité de queue, l'instruction d'appel récursif est généralement exécutée en même temps que l'instruction de retour de la méthode.
La syntaxe générale de la récursion de queue est présentée ci-dessous :
methodName ( T parameters...){ { if (base_condition == true) { return result ; } return methodName (T parameters ...) //tail recursion } #2) Récurrence de tête
La récursion en tête est toute approche récursive qui n'est pas une récursion en queue. Ainsi, même la récursion générale est une récursion en tête.
La syntaxe de la récursion de tête est la suivante :
methodName (T parameters...){ if (some_condition == true) { return methodName (T parameters...) ; } return result ; } Récursion et itération en Java
| Récursion | Itération |
|---|---|
| La récursivité est un processus par 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é de manière répétée pendant un nombre fini de fois ou jusqu'à ce qu'une condition soit remplie. |
| Est la demande de fonctions. | S'applique aux boucles. |
| Fonctionne bien pour les codes de petite taille. | Fonctionne bien pour les codes de grande taille. |
| Utilise plus de mémoire car chaque appel récursif est poussé sur la pile. | La quantité de mémoire utilisée est relativement faible. |
| Difficulté de débogage et de maintenance | Plus facile à déboguer et à entretenir |
| Entraîne un débordement de la pile si la condition de base n'est pas spécifiée ou n'est pas atteinte. | Peut s'exécuter à l'infini mais s'arrêtera finalement en cas d'erreur de mémoire. |
| La complexité du temps est très élevée. | La complexité du temps est relativement faible. |
Questions fréquemment posées
Q #1) Comment fonctionne la récursivité en Java ?
Réponse : Dans la récursivité, la fonction récursive s'appelle elle-même à plusieurs reprises jusqu'à ce qu'une condition de base soit remplie. La mémoire de la fonction appelée est poussée sur la pile au sommet 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 utilise-t-on la récursivité ?
Réponse : La récursivité est utilisée pour résoudre les problèmes qui peuvent être décomposés en plusieurs problèmes plus petits et le problème entier peut être exprimé en termes d'un problème plus petit.
La récursivité est également utilisée pour les problèmes trop complexes pour être résolus par une approche itérative. En dehors des problèmes pour lesquels la complexité temporelle n'est pas un problème, utilisez la récursion.
Q #3) Quels sont les avantages de la récursivité ?
Réponse :
Les avantages de la récursivité sont les suivants
- La récursivité permet de réduire les appels redondants de fonctions.
- La récursivité permet de résoudre les problèmes plus facilement que l'approche itérative.
Q #4) Lequel est le meilleur - la récursivité ou l'itération ?
Réponse : La récursivité répète les appels jusqu'à ce que la fonction de base soit atteinte, ce qui entraîne une surcharge de mémoire puisque chaque appel de fonction est placé sur la pile.
L'itération, quant à elle, n'entraîne pas de surcharge de mémoire. L'exécution par récursion est plus lente que l'approche itérative. La récursion réduit la taille du code, tandis que l'approche itérative l'alourdit.
Q #5) Quels sont les avantages de la récursivité par rapport à l'itération ?
Réponse :
- 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 tels que la Tour de Hanoi, les parcours d'arbres, etc.
- Étant donné que chaque appel de fonction entraîne l'ajout de mémoire à la pile, la récursivité utilise davantage de mémoire.
- La récursivité est plus lente que l'approche itérative.
Conclusion
La récursion est un concept très important dans les logiciels, quel que soit le langage de programmation. La récursion est principalement utilisée pour résoudre des problèmes de structure de données tels que les tours de Hanoi, les parcours d'arbres, les listes chaînées, etc. Bien qu'elle prenne plus de mémoire, la récursion rend le code plus simple et plus clair.
Dans ce tutoriel, nous avons exploré tous les aspects de la récursivité et mis en place de nombreux exemples de programmation pour une meilleure compréhension du concept.