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 de pré-test (while), la boucle de post-test (do-while) et boucle contre-contrôlée (pour).

Ces structures itératives fonctionnent en répétant un bloc de code alors qu'une condition spécifique demeure vrai, mais dès que cette condition devient fausse, la boucle s'arrête et le programme revient à sa normale couler.

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 les trois structures itératives peuvent fournir une solution à ce problème en utilisant les éléments suivants pseudocode.

Exemple de pseudocode d'itération

DÉMARRER
DECLEARE somme, compte comme un entier
somme = 0
count = 1
RÉPÉTER
Somme = somme + nombre
Compte = compte + 1
JUSQU'À nombre> n
FINIR

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 chacun fois qu'une boucle est exécutée, mais dès que la valeur de la variable «count» dépasse celle de «n» alors la boucle arrêter.

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 en utilisant l'itération peut également être résolu en utilisant 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.

En rapport: 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

Une fonction(){
//cas de base
// cas général
}

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

// fonction récursive
int Sum (int n) { 
//cas de base
si (n <= 1) {
return 1;
}
// cas général
autre{
renvoie n + somme (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 elle-même 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

Qu'est-ce que la récursivité et comment l'utilisez-vous?

Apprenez les bases de la récursivité, l'outil essentiel mais un peu déroutant pour les programmeurs.

Lire la suite

A propos de l'auteur