Qu’est-ce qu’une fonction récursive et comment en créer une en Java?

La nécessité de répéter le code ne peut jamais être sous-estimée dans la recherche de solutions à certains des plus grands problèmes du monde. Ce que vous devez savoir, c'est qu'en programmation, la répétition prend l'une des deux formes suivantes: itération ou récursivité.

Le but ici est de vous présenter la répétition dans le code et de montrer comment elle peut être utilisée pour améliorer vos programmes Java.

Les programmes répétitifs peuvent vous aider à résoudre certains des problèmes de programmation les plus difficiles. Voici ce que vous devez savoir pour créer des programmes récursifs en Java.

Utilisation de l'itération

L'itération utilise une structure en boucle pour répéter le code. Les trois types de structures itératives sont la boucle pré-test (while), la boucle post-test (do-while) et la boucle contre-contrôlée (for) .

Ces structures itératives fonctionnent en répétant un bloc de code pendant qu'une condition spécifique reste vraie, mais dès que cette condition devient fausse, la boucle s'arrête et le programme revient à son déroulement normal.

Par exemple, nous pourrions utiliser l'une des structures itératives pour résoudre le problème de la somme de tous les entiers de 1 à n. En fonction de la structure itérative utilisée, la solution prendra une forme spécifique, mais l'une des trois structures itératives peut fournir une solution à ce problème en utilisant le pseudo-code suivant.

Exemple de pseudocode d'itération

 
START
 DECLEARE sum, count as integer
 sum = 0
 count = 1
 REPEAT
 Sum = sum + count
 Count = count + 1
 UNTIL count > n
 END

Le pseudo-code ci-dessus a deux variables, sum et count, qui sont initialisées respectivement à 0 et 1. La variable "count" est initialisée à 1 car le problème que nous essayons de résoudre indique que nous avons besoin de la somme de tous les nombres entiers de 1 à n.

La variable «n» se verra attribuer un nombre aléatoire de la part de l'utilisateur et la variable «count» augmentera de un à chaque fois qu'une boucle est effectuée, mais dès que la valeur de la variable «count» dépasse celle de «n» alors la boucle s'arrêtera.

Pourquoi utiliser la récursivité?

Si nous devions examiner les faits entourant l'itération et la récursivité, nous constaterons que plusieurs choses sont vraies.

• Les deux méthodes impliquent la répétition.
• Les deux méthodes nécessitent une condition de test, qui indiquera quand s'arrêter.
• Les deux méthodes peuvent théoriquement s'exécuter indéfiniment si une condition de sortie n'est pas donnée ou remplie.
• Tout problème qui peut être résolu à l'aide de l'itération peut également être résolu à l'aide de la récursivité et vice versa.

Alors pourquoi voudrions-nous choisir une méthode plutôt qu'une autre? La réponse simple est l'efficacité. Avec la récursivité, un programmeur peut utiliser moins de code pour obtenir ce qui est essentiellement le même résultat. Moins de code signifie qu'il y a une diminution significative de la possibilité que des erreurs passent inaperçues.

La récursivité utilise plus de mémoire et est plus lente que l'itération, mais possède une pile intégrée (structure de données). Avec l'itération, vous auriez à construire une structure de données (réinventant essentiellement la roue), laissant votre programme ouvert à une plus grande possibilité d'erreurs non interceptées en raison du code supplémentaire.

Connexes: Exceptions Java : les gérez-vous correctement?

Comment fonctionne la récursivité

La récursivité est le nom donné à un processus où une fonction s'appelle à plusieurs reprises jusqu'à ce qu'une condition spécifique soit remplie. Cette méthode répétitive résout les problèmes en les décomposant en versions plus petites et plus simples d'eux-mêmes.

Chaque fonction récursive se compose de deux parties: le cas de base et le cas général.

Structure de base d'un exemple de fonction récursive

 
Function(){
 //base case
 //general case
 }

Le cas de base est la section de la fonction récursive qui résout le problème. Ainsi, chaque fois que la fonction récursive arrive au cas de base, le programme quitte la fonction récursive et continue avec son flux naturel.

Le cas général est la section de la fonction récursive qui est répétitive. C'est là que la fonction s'appelle et où le gros du travail est effectué.

Utilisation de la récursivité en Java

Certains langages de programmation ne prennent en charge que l'itération, tandis que d'autres ne prennent en charge que la récursivité. Heureusement, Java est l'un des langages qui prennent en charge les deux méthodes répétitives.

En Java, la récursivité est utilisée à peu près de la même manière qu'elle est utilisée dans tout autre langage qui la prend en charge. La clé est de toujours s'assurer que votre fonction récursive a à la fois une base et un cas général, dans cet ordre.

Revenons à notre exemple de sommation initiale, le but est de trouver la somme de tous les entiers de 1 à n, où n est un nombre entier fourni par l'utilisateur.

Exemple de récursivité Java

 
//recursive function
 int Sum(int n){
 //base case
 if (n <= 1){
 return 1;
 }
 //general case
 else{
 return n + Sum(n-1);
 }
 }

La fonction récursive ci-dessus prend un entier «n» et ne termine son exécution que lorsque la valeur de n est inférieure ou égale à 1.

Si nous devions passer l'entier 5 au programme ci-dessus, la variable «n» prendrait la valeur de 5. La valeur de «n» serait alors vérifiée dans le cas de base, mais étant donné que 5 est supérieur à 1 «n »Sera maintenant passé au cas général.

Dans cet exemple, le cas général appellera la fonction récursive quatre fois. Lors de l'appel de fonction final, la valeur de «n» sera 1, répondant effectivement aux exigences du cas de base résultant en la fin de la fonction récursive et en renvoyant 15.

Si nous changeons la valeur de «n» en 7, la fonction récursive s'appellera six fois et retournera 28 avant de terminer son exécution.

Envie de l'essayer par vous-même? Vous pouvez exécuter le programme récursif ci-dessus en utilisant la ligne de code suivante dans la fonction principale de votre programme Java.

 
System.out.println( Sum(7));

Ce que vous avez appris

Si vous avez parcouru tout cet article, vous avez maintenant une compréhension de base des deux méthodes répétitives utilisées dans la programmation. Vous reconnaissez maintenant les similitudes entre l'itération et la récursivité et pourquoi un développeur choisirait d'utiliser la récursivité sur l'itération, et comment utiliser une fonction récursive en Java.

Crédit d'image: ThisIsEngineering / Pexels