• 15 heures
  • Facile

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 19/05/2021

Entrez dans les détails grâce à la récursivité

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Qu'est-ce que la récursivité ?

Dans ce chapitre, vous allez apprendre l'un des concepts fondamentaux de la programmation : la récursivité. 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

Vous vous souvenez maintenant ? Eh bien, 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. Du point de vue du codage, 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 pouvez-vous é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 :

  1. Cela arrêtera la méthode factorielle quand n sera égal à 1.

  2. 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 figurant dans la vidéo. 📚 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 la faisant fonctionner avec les sous-catégories de l'une des catégories d'origine. Cette itération irait plus loin et s'appellerait 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 reviendrait à 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.

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.

Exemple de certificat de réussite
Exemple de certificat de réussite