• 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 23/07/2020

Découvrez la récursivité : l'appel de fonctions à l'intérieur d'elles-mêmes

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

Une fonction qui s'appelle elle-même

Une fonction récursive est une fonction qui s'appelle elle-même d'une façon ou d'une autre.

Prenons l'exemple que je décris dans la vidéo de ce chapitre : la recherche binaire.

Le but de l'exercice : chercher un élément dans un array trié pour savoir s'il s'y trouve.

Une approche basique (et plutôt lente) serait la suivante :

const findElement(array, thingToFind) {
for (let element of array) {
if (element === thingToFind) {
return true;
}
}
return false;
}

On avance, élément par élément, dans le tableau. Si on trouve un élément qui correspond à ce que l'on recherche, la fonction renvoie  true. Si on arrive à la fin du tableau sans l'avoir trouvé, on passe à la ligne suivante et la fonction renvoie  false.

C'est plutôt clair comme approche, mais c'est lent ! Le temps pris pour chaque recherche se prolonge de manière linéaire avec des listes plus longues !

Imaginons une autre approche.

const binarySearch = (array, thingToFind, start, end) => {
}

On sait que le tableau est trié, donc on peut savoir, pour un élément donné, si ce que l'on recherche risque de se trouver plus haut ou plus bas dans la liste. Par exemple, si on recherche le nombre 42 et que l'on tombe sur 32, on sait qu'il faudra chercher plus bas.

Du coup, commençons par analyser l'élément médian de la liste. On peut faire la somme de l'index de début et l'index de fin et diviser par deux pour trouver cet élément (arrondissons vers le bas pour nous assurer de trouver un nombre entier :

const binarySearch = (array, thingToFind, start, end) => {
let mid = Math.floor((start + end) / 2);
}

Mais pourquoi utiliser les index de début et de fin plutôt que la propriété  length  du tableau ? 

Utiliser les index nous permettra de réutiliser le même code sur des sélections de plus en plus petites du tableau, comme vous allez vite le découvrir !

Maintenant que l'on a l'élément médian du tableau, vérifions si, par chance, on est tombé juste.

const binarySearch = (array, thingToFind, start, end) => {
let mid = Math.floor((start + end) / 2);
if (array[mid] === thingToFind) {
return true;
}
}

La fonction retournera  true  si on a trouvé l'élément.

Si on n'a pas eu de chance, ce n'est pas grave : puisque le tableau est trié, on sait dans quelle moitié du tableau chercher ! Du coup, on a juste à exécuter exactement la même fonction sur la partie en question ! Il suffit de modifier soit l'index de fin (pour chercher dans la première moitié) soit l'index de début (pour chercher dans la deuxième moitié) :

const binarySearch = (array, thingToFind, start, end) => {
let mid = Math.floor((start + end) / 2);
if (array[mid] === thingToFind) {
return true;
}
if (thingToFind < array[mid]) {
// il faut rechercher dans la première moitié
return binarySearch(array, thingToFind, start, mid - 1); // on utilise (mid - 1) car on sait que l'on n'a pas besoin de l'élément mid, il a déjà été vérifié !
} else {
// il faut rechercher dans la deuxième moitié
return binarySearch(array, thingToFind, mid + 1, end);
}
}

La fonction continuera à s'appeler elle-même jusqu'à trouver ce que l'on recherche. Mais il manque quelque chose ! Qu'est-ce qui se passe si ce que l'on recherche n'existe pas dans le tableau ? Il faut ce que l'on appelle un casde base, ou base case, pour dire à la fonction de s'arrêter.

Quel est le base case dans cet algorithme ?

On saura que l'algorithme est arrivé au bout si on a essayé de l'appeler avec un index de début qui est supérieur à l'index de fin.

Pourquoi ? Eh bien parce que peu à peu, on divise le tableau, encore et encore, jusqu'à tomber sur une sélection d'un seul élément : on aura donc  start = mid = end. Du coup, quand la fonction se rappellera encore, elle utilisera soit  start = mid + 1, soit  end = mid - 1, selon notre recherche. On aura donc  start > end, et la fonction peut retourner  false, car on sait qu'elle est arrivée au bout sans trouver ce que l'on recherche.

On met donc ce base case au début de la fonction pour vérifier s'il s'agit du dernier appel :

const binarySearch = (array, thingToFind, start, end) => {
if (start > end) {
return false;
}
let mid = Math.floor((start + end) / 2);
if (array[mid] === thingToFind) {
return true;
}
if (thingToFind < array[mid]) {
return binarySearch(array, thingToFind, start, mid - 1);
} else {
return binarySearch(array, thingToFind, mid + 1, end);
}
}

Et voilà ! Une fonction récursive, qui s'appelle elle-même, qui effectue une recherche d'élément dans un tableau trié, et qui renvoie  true  si l'élément s'y trouve, ou  false  s'il ne s'y trouve pas (grâce au base case) !

Cet algorithme s'appelle la recherche binaire, et il s'agit d'un exercice qui est souvent demandé en entretien d'embauche, donc vous venez de faire un pas de plus vers votre premier emploi de développeur !

En résumé

Dans ce chapitre, vous avez vu :

  • que les fonctions récursives sont des fonctions qui s'appellent elles-mêmes ;

  • vous avez vu qu'une fonction récursive a besoin d'un cas de base, ou base case, pour qu'elle puisse savoir quand son travail est terminé ;

  • vous avez vu un exemple de fonctionnement du code.

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