Récursivité en Java

1. Introduction

Dans cet article, nous allons nous concentrer sur un concept de base dans n'importe quel langage de programmation: la récursivité.

Nous expliquerons les caractéristiques d'une fonction récursive et montrerons comment utiliser la récursivité pour résoudre divers problèmes en Java.

2. Comprendre la récursivité

2.1. La définition

En Java, le mécanisme d'appel de fonction prend en charge la possibilité d'avoir un appel de méthode lui-même . Cette fonctionnalité est connue sous le nom de récursivité .

Par exemple, supposons que nous voulions additionner les entiers de 0 à une valeur n :

public int sum(int n) { if (n >= 1) { return sum(n - 1) + n; } return n; }

Il existe deux exigences principales d'une fonction récursive:

  • Une condition d'arrêt - la fonction renvoie une valeur lorsqu'une certaine condition est satisfaite, sans autre appel récursif
  • L'appel récursif - la fonction s'appelle elle-même avec une entrée qui se rapproche de la condition d'arrêt

Chaque appel récursif ajoutera une nouvelle trame à la mémoire de pile de la JVM. Donc, si nous ne faisons pas attention à la profondeur de notre appel récursif, une exception de mémoire insuffisante peut se produire.

Ce problème potentiel peut être évité en tirant parti de l'optimisation de la récursivité de la queue.

2.2. Récurrence de la queue et récursivité de la tête

Nous nous référons à une fonction récursive en tant que récursivité de queue lorsque l'appel récursif est la dernière chose que la fonction exécute. Sinon, c'est ce qu'on appelle la récursivité de la tête .

Notre implémentation ci-dessus de la fonction sum () est un exemple de récursivité de tête et peut être changée en récursivité de queue:

public int tailSum(int currentSum, int n) { if (n <= 1) { return currentSum + n; } return tailSum(currentSum + n, n - 1); }

Avec la récursivité de queue, l'appel récursif est la dernière chose que fait la méthode, il n'y a donc plus rien à exécuter dans la fonction courante.

Ainsi, logiquement, il n'est pas nécessaire de stocker le cadre de pile de la fonction courante.

Bien que le compilateur puisse utiliser ce point pour optimiser la mémoire, il convient de noter que le compilateur Java n'optimise pas pour le moment la récursivité finale .

2.3. Récursivité contre itération

La récursivité peut aider à simplifier la mise en œuvre de certains problèmes complexes en rendant le code plus clair et plus lisible.

Mais comme nous l'avons déjà vu, l'approche récursive nécessite souvent plus de mémoire car la mémoire de pile requise augmente à chaque appel récursif.

En alternative, si nous pouvons résoudre un problème avec la récursivité, nous pouvons également le résoudre par itération.

Par exemple, notre méthode de somme pourrait être implémentée en utilisant l'itération:

public int iterativeSum(int n) { int sum = 0; if(n < 0) { return -1; } for(int i=0; i<=n; i++) { sum += i; } return sum; }

Par rapport à la récursivité, l'approche itérative pourrait potentiellement donner de meilleures performances. Cela étant dit, l'itération sera plus compliquée et plus difficile à comprendre que la récursivité, par exemple: traverser un arbre binaire.

Faire le bon choix entre la récursivité de la tête, la récursivité de la queue et une approche itérative dépendent tous du problème et de la situation spécifiques.

3. Exemples

Maintenant, essayons de résoudre certains problèmes de manière récursive.

3.1. Trouver la N-ième puissance de dix

Supposons que nous ayons besoin de calculer la n- ième puissance de 10. Ici, notre entrée est n. En pensant de manière récursive, nous pouvons d'abord calculer la (n-1) -ème puissance de 10, et multiplier le résultat par 10.

Ensuite, pour calculer la (n-1) -ème puissance de 10 sera la (n-2) -ème puissance de 10 et multipliez ce résultat par 10, et ainsi de suite. Nous continuerons ainsi jusqu'à ce que nous arrivions à un point où nous devons calculer la (nn) -ème puissance de 10, qui est 1.

Si nous voulions implémenter cela en Java, nous écririons:

public int powerOf10(int n) { if (n == 0) { return 1; } return powerOf10(n-1) * 10; }

3.2. Recherche du N-ième élément de la séquence de Fibonacci

Commençant par 0 et 1 , la séquence de Fibonacci est une séquence de nombres où chaque nombre est défini comme la somme des deux nombres le suivant : 0 1 1 2 3 5 8 13 21 34 55

Donc, étant donné un nombre n , notre problème est de trouver le n- ième élément de la séquence de Fibonacci . Pour implémenter une solution récursive, nous devons déterminer la condition d'arrêt et l' appel récursif .

Heureusement, c'est vraiment simple.

Appelons f (n) la n- ième valeur de la séquence. Ensuite, nous aurons f (n) = f (n-1) + f (n-2) (l' appel récursif ) .

Pendant ce temps, f (0) = 0 et f (1) = 1 ( condition d'arrêt) .

Ensuite, il est vraiment évident pour nous de définir une méthode récursive pour résoudre le problème:

public int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); }

3.3. Conversion de décimal en binaire

Considérons maintenant le problème de la conversion d'un nombre décimal en binaire. La condition est d'implémenter une méthode qui reçoit une valeur entière positive n et renvoie une représentation String binaire .

Une approche pour convertir un nombre décimal en nombre binaire consiste à diviser la valeur par 2, à enregistrer le reste et à continuer à diviser le quotient par 2.

Nous continuons à nous diviser comme ça jusqu'à ce que nous obtenions un quotient de 0 . Ensuite, en écrivant tous les restes dans l'ordre de réserve, nous obtenons la chaîne binaire.

Par conséquent, notre problème est d'écrire une méthode qui retourne ces restes dans l'ordre de réserve:

public String toBinary(int n) { if (n <= 1 ) { return String.valueOf(n); } return toBinary(n / 2) + String.valueOf(n % 2); }

3.4. Hauteur d'un arbre binaire

La hauteur d'un arbre binaire est définie comme le nombre d'arêtes de la racine à la feuille la plus profonde. Notre problème est maintenant de calculer cette valeur pour un arbre binaire donné.

Une approche simple serait de trouver la feuille la plus profonde puis de compter les bords entre la racine et cette feuille.

Mais en essayant de penser à une solution récursive, nous pouvons reformuler la définition de la hauteur d'un arbre binaire comme la hauteur maximale de la branche gauche de la racine et de la branche droite de la racine, plus 1 .

Si la racine n'a ni branche gauche ni branche droite, sa hauteur est égale à zéro .

Voici notre implémentation:

public int calculateTreeHeight(BinaryNode root){ if (root!= null) { if (root.getLeft() != null || root.getRight() != null) { return 1 + max(calculateTreeHeight(root.left), calculateTreeHeight(root.right)); } } return 0; }

Par conséquent, nous voyons que certains problèmes peuvent être résolus avec la récursivité d'une manière très simple.

4. Conclusion

Dans ce tutoriel, nous avons introduit le concept de récursivité en Java et l'avons démontré avec quelques exemples simples.

La mise en œuvre de cet article est disponible à l'adresse over sur Github.