Comprenez le principe de récursivité
Dans ce chapitre, vous allez apprendre l'un des concepts fondamentaux de la programmation : la récursivité.
Souvenez-vous des mathématiques factorielles
Commençons par regarder la récursivité dans le contexte des mathématiques factorielles. Vous vous souvenez de ce qu'est une factorielle ?
5! = 5 x 4 x 3 x 2 x 1
4! = 4 x 3 x 2 x 1
3! = 3 x 2 x 1
En fait, la façon dont fonctionne une factorielle nous donnera un bon exemple de la récursivité dans Java. Une autre façon plus abstraite de l'écrire serait :
N! = N x (N-1)!
En utilisant des chiffres, cela donne :
5! = 5 x (5-1)! , c'est-à-dire 5! = 5 x (4)! , et au final 5! = 5 x 4! .
Mais, suivant cette formule, nous pouvons également écrire 4! comme 4 x (4-1)! , ce qui nous donne 4 x 3! . Nous pouvons ainsi revenir à 5! = 5 x 4! pour obtenir : 5! = 5 x (4 x 3!) .
Une minute ! En regardant notre nouvelle version, 3! peut également utiliser cette formule ! Ce qui va finalement nous donner : 5! = 5 x 4 x (3 x 2!) . Nous pouvons recommencer avec 2! .
Même si vous n'êtes pas très doué en maths, vous pouvez voir ici que la formule factorielle est utilisée à plusieurs reprises.
Appliquez le principe en langage Java
Du point de vue du code, vous pouvez créer une fonction qui s'exécute de façon répétée, comme ici, jusqu'à ce que vous ayez une réponse complète.
Comment écrire une factorielle en langage Java en utilisant des opérateurs ?
Essayons :
// définissez des classes
class RecursionInJava {
public static int factorial(int n) {
n = n * factorial (n-1);
}
}Attention, le code ci-dessus ne fonctionne pas ! Vous pouvez tester pour voir. C'est un exemple qu'on va améliorer juste après !
Si vous regardez attentivement la ligne n = n * factorial(n-1) , vous constaterez que la méthode factorielle est appelée à l'intérieur d'elle-même. C'est ce qu'on appelle la récursivité, parce que la méthode fonctionne en continu en s'appelant elle-même.
Vous vous souvenez des instructions conditionnelles comme if/else ? Elles permettent à une instruction de s'appliquer à l'infini jusqu'à l'arrêt de la méthode pour une raison donnée. Pourquoi voudriez-vous arrêter cette méthode ? Lorsque vous effectuez une équation factorielle, elle se termine à 1. En transposant à la programmation, vous devez créer une instruction conditionnelle qui mettra fin à la récursion quand n sera égal à 1.
Ceci fera deux choses :
Cela arrêtera la méthode factorielle quand n sera égal à 1.
Si le numéro d'origine est 1, l'instruction renvoie simplement 1.
Voyons à quoi ça ressemble :
// Définissez des classes
class RecursionInJava {
// La méthode corrigée
public static int factorial(int n) {
if (n == 1) return 1;
else return n * factorial (n-1);
}
}Revenons maintenant à l'exemple du livre. Si vous voulez compter les livres dans chaque catégorie, chaque sous-catégorie, et ainsi de suite, vous devez vous assurer que vous prenez en compte toutes les différentes couches. Puis, une fois terminée, cette fonction s'appellera elle-même, mais cette fois en fonctionnant avec les sous-catégories de l'une des catégories d'origine. Cette itération ira plus loin et s'appellera elle-même à nouveau pour traiter des sous-catégories. Et ainsi de suite, jusqu'à ce qu'il n'y ait plus de sous-catégories. De cette façon, vous pouvez aller jusqu'au tout dernier sous-niveau de chaque catégorie d'origine. Et si une catégorie n'a pas de sous-catégories, votre fonction reviendra à votre point de départ.
Voici à quoi ressemble le code qui implémente cela en Java :
class BookStore {
public static Categories categories;
// Définissez une fonction récursive
public static int countBooks(Categories categories) {
int c = 0;
for (Category category : categories) {
c += category.numberOfBooks;
c += countBooks(category.subCategories);
}
return c;
}
public static void main(String[] args) {
// Appelez cette fonction récursive
Category c1 = new Category();
c1.numberOfBooks = 3;
Category c2 = new Category();
c2.numberOfBooks = 2;
Category c3 = new Category();
c3.numberOfBooks = 10;
Categories subc1 = new Categories();
subc1.add(c3);
c1.subCategories = subc1;
categories = new Categories();
categories.add(c1);
categories.add(c2);
int numberOfBooks = countBooks(BookStore.categories);
System.out.println("The bookstore has " + numberOfBooks + " books");
}
}
---------------
import java.util.ArrayList;
class Categories extends ArrayList<Category> {
}
---------------
public class Category {
public int numberOfBooks;
public Categories subCategories = new Categories();
}Très efficace, n'est-ce pas ?
En termes techniques, la récursion est une action qui s'initialise à l'intérieur d'elle-même. Elle continue de descendre couche après couche, jusqu'à ce qu'une condition soit remplie, puis remonte jusqu'à la première couche.
La récursivité est l'un des concepts fondamentaux de tout langage de programmation !
En résumé
La récursivité est une action qui s'initialise à l'intérieur d'elle-même.
Les méthodes récursives servent à passer des structures en couches.
Passons au chapitre suivant pour apprendre comment les erreurs et les exceptions permettent de gérer les comportements inattendus.
