Récursivité en Java
La récursivité est au cœur de la programmation et est utilisée dans de nombreux concepts connexes tels que le tri, le parcours d'arbres et les graphes. De plus, la récursivité a une grande variété d'utilisations dans les structures de données et les algorithmes, et même s'il s'agit d'un concept complexe, il peut être utilisé pour faciliter la tâche.
La récursivité, en termes simples, est une fonction qui s'appelle elle-même. Voyons notre premier code, qui décrit littéralement la définition.
Récursion en Java
/**
This class has a recursive method.
*/
public class EndlessRecursion
{
public static void message()
{
System.out.println("This is a recursive method.");
//recursive call
message();
}
} Le code ci-dessus est assez simple. Nous avons une récursivité sans fin d'appel de classe avec une fonction nommée message, et la fonction imprime la ligne "Ceci est une méthode récursive.". Cependant, il y a un problème. Il n'y a aucun moyen d'arrêter les appels récursifs. Donc, cette méthode est comme une boucle infinie car il n'y a pas de code pour l'empêcher de se répéter. Nous avons donc conclu qu'une fonction récursive nécessite également une condition de terminaison pour s'arrêter, tout comme une boucle.
Un code simple est illustré ci-dessous avec une condition de terminaison.
/**
This class has a recursive method, message,
which displays a message n times.
*/
public class Recursive
{
public static void message(int n)
{
if (n > 0)
{
System.out.println("This is a recursive method.");
message(n - 1);
//After the condition is false the control returns to the end of the if
//expression and since no statement is written below the recursive
//call, the method returns.
}
}
} Maintenant, la méthode message() contient une condition if qui contrôle la répétition de la fonction. Tant que le paramètre n est supérieur à zéro, la méthode affiche le message et s'appelle à nouveau. Considérons que n=5 dans ce cas. Ainsi, la fonction message() s'appellera 5 fois et affichera le contenu de l'instruction print. Le nombre de fois qu'une méthode est appelée est la profondeur de la récursivité. Dans ce cas, la profondeur de récursivité est de 5. Lorsque la méthode atteint le sixième appel, n=0. À ce stade, l'expression conditionnelle de l'instruction if est fausse, donc la méthode est renvoyée.
Résoudre les problèmes avec la récursivité
La récursivité peut être un outil puissant pour résoudre des problèmes répétitifs et constitue un sujet important dans les cours d'informatique de niveau supérieur. Ce qui n'est peut-être pas encore clair pour vous, c'est comment utiliser la récursivité pour résoudre un problème. Tout problème qui peut être résolu de manière récursive peut également être résolu à l'aide d'une boucle. En fait, les solutions récursives sont moins efficaces que les solutions itératives. Cependant, la récursivité est encore largement utilisée car elle simplifie le travail d'un programmeur.
En général, une méthode récursive fonctionne comme ceci :
• Si le problème peut être résolu sans récursivité, alors la méthode le résout
et revient.
• Si le problème ne peut pas être résolu, la méthode le réduit à un plus petit mais
problème similaire et appelle lui-même à résoudre le problème plus petit.
Pour appliquer cela, nous devons identifier au moins un cas dans lequel le problème peut être résolu sans récurrence, et c'est ce qu'on appelle le cas de base. Ensuite, nous déterminons un moyen de résoudre le problème dans toutes les autres circonstances en utilisant la récursivité. Enfin, considérons un code qui décrit cette méthode récursive.
/**
The factorial method uses recursion to calculate
the factorial of its argument, which is assumed
to be a nonnegative number.
@param n The number to use in the calculation.
@return The factorial of n.
*/
private static int factorial(int n)
{
if (n == 0)
return 1; // Base case
else
//Although this is a return statement, it does not immediately return. Before the return value
//can be determined, the value of factorial(n − 1) must be determined. The factorial
//method is called recursively until the n parameter will be set to zero.
return n * factorial(n - 1);
}Célèbres problèmes récursifs
Certains problèmes récursifs bien connus incluent la série de Fibonacci, la factorielle, le plus grand diviseur commun, la recherche binaire et bien d'autres.
Commençons par la plus simple, c'est-à-dire la série de Fibonacci. La série de Fibonacci est une séquence qui ressemble à ceci.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, . . .
Notez que chaque nombre de la série est la somme des deux nombres précédents après le deuxième nombre. Ainsi, la série de Fibonacci peut être définie comme suit.
public static int fib(int n)
{
//base case 1
if (n == 0)
return 0;
//base case 2
else if (n == 1)
return 1;
else
return fib(n - 1) + fib(n - 2);
}Écrivons tout le code pour tester cette fonction
/**
This program demonstrates the recursive fib method.
*/
public class FibNumbers
{
public static void main(String[] args)
{
System.out.println("The first 10 numbers in " +
"the Fibonacci series are:");
for (int i = 0; i < 10; i++)
System.out.print(fib(i) + " ");
System.out.println();
}
/**
The fib method calculates the nth
number in the Fibonacci series.
@param n The nth number to calculate.
@return The nth number.
*/
public static int fib(int n)
{
if (n == 0)
return 0;
else if (n == 1)
return 1;
else
return fib(n − 1) + fib(n − 2);
}
} Vient ensuite le plus grand diviseur commun, c'est-à-dire le PGCD.
Le PGCD de deux entiers positifs, x et y, est le suivant :
si y divise x uniformément, alors pgcd(x, y) =y
Sinon, pgcd(x, y) =pgcd(y, reste de x/y)
Cette définition stipule que le PGCD de x et y est y si x/y n'a pas de reste. C'est le cas de base. Sinon, la réponse est le PGCD de y et le reste de x/y.
import java.util.Scanner;
/**
This program demonstrates the recursive gcd method.
*/
public class GCDdemo
{
public static void main(String[] args)
{
int num1, num2; // Two numbers for GCD calculation
// Create a Scanner object for keyboard input.
Scanner keyboard = new Scanner(System.in);
// Get the first number from the user.
System.out.print("Enter an integer: ");
num1 = keyboard.nextInt();
// Get the second number from the user.
System.out.print("Enter another integer: ");
num2 = keyboard.nextInt();
// Display the GCD.
System.out.println("The greatest common divisor " +
"of these two numbers is " +
gcd(num1, num2));
}
/**
The gcd method calculates the greatest common
divisor of the arguments passed into x and y.
@param x A number.
@param y Another number.
@returns The greatest common divisor of x and y.
*/
public static int gcd(int x, int y)
{
if (x % y == 0)
return y;
else
return gcd(y, x % y);
}
} La sortie du programme ci-dessus est
Enter an integer: 49 [Enter]
Enter another integer: 28 [Enter]
The greatest common divisor of these two numbers is 7Conclusion
Toutes les méthodes décrites ci-dessus ont une solution itérative, mais la solution récursive crée une solution d'écriture élégante et facile. Dans les structures de données telles que les arbres et les graphiques, les appels récursifs sont répandus car ils rendent le code concis et facile à comprendre.
