Blog ENI : Toute la veille numérique !
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
  1. Livres et vidéos
  2. Machine Learning et Deep Learning
  3. La récursivité
Extrait - Machine Learning et Deep Learning Des bases à la conception avancée d'algorithmes (exemples en Python et en JavaScript)
Extraits du livre
Machine Learning et Deep Learning Des bases à la conception avancée d'algorithmes (exemples en Python et en JavaScript)
1 avis
Revenir à la page d'achat du livre

La récursivité

Introduction

La récursivité est une notion qui peut être troublante pour des apprentis développeurs. Il s’agit d’un concept qui fait appel à lui-même. On le retrouve dans l’art, avec la mise en abîme, ou dans les mathématiques, au travers des objets fractals. Le sigle ’’pip’’ fait également appel à ce concept, en ce sens qu’il contient le mot ’’pip’’ dans sa forme développée : pip installs packages. Ce qui engendre une mise en abîme de ce genre : pip (pip (pip (pip installs packages) installs packages) installs packages) installs packages… On peut continuer comme ça à l’infini.

images/10RI01.png

Figure géométrique récursive

La récursivité est utilisée lorsqu’un algorithme ou une fonction fait appel ou référence à lui-même. Voyons deux exemples d’algorithmes récursifs connus.

Une factorielle récursive

Pour rappel, la factorielle d’un entier naturel n est une opération mathématique qui demande de multiplier entre eux tous les entiers de 1 à n compris. Par exemple, la factorielle de 5, ou 5! est égale à 1 * 2 *3 * 4 * 5, ce qui peut se décomposer de cette façon :

  • 1 * 2 = 2

  • 2 * 3 = 6

  • 6 * 4 = 24

  • 24 * 5 = 120

5! est donc égal à 120.

Passons au pseudo-code :

Algorithme : Factorielle d'un nombre 
Fonction factorielle (entier : n)  
Variables : 
entier : r 
Début 
     r  1 
     Pour i allant de 1 à n avec un pas de 1 
          r  r*i 
     Retourner r 
  Fin 

Nous initialisons la variable r à 1. Ensuite, nous bouclons de 1 jusqu’au nombre n, qui est la valeur finale de la factorielle, 5 ici. La boucle Pour fait donc un nombre de tours égal à n, donc 5 dans notre exemple. Lors du premier tour, la valeur initiale de r est 1 et la valeur de l’incrémenteur i pour la boucle Pour est 1, donc l’opération r*i donne 1=*, et 1 * 1 = 1. La valeur 1 écrase l’ancienne valeur de la variable r. Lors du deuxième tour, i vaut 2 (puisque la boucle avance de 1 à 10 avec un pas de 1), r vaut 1, par conséquent le calcul donne 1 * 2 = 2. La valeur 2 remplace la valeur précédente de r. Lors du troisième tour, r vaut 2 et i vaut...

Fibonacci récursif

La suite de Fibonacci, du nom du mathématicien italien Leonardo Fibonacci, est une suite d’entiers naturels dans laquelle chaque terme est le résultat de la somme des deux entiers naturels qui le précèdent. Les dix premiers nombres de Fibonacci (certains font commencer la suite par 0 et d’autres par 1) sont donc : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

Écrivons l’algorithme de la suite de Fibonacci.

Algorithme : Fibonacci récursif 
Fonction suite de Fibonacci(entier : n) 
entier : nombre1, nombre2, nombre3 
nombre1  0 
nombre2  1 
Début 
     Pour i allant de 0 à n-1 avec un pas de 1 
           nombre3  nombre1 + nombre2 
           nombre1  nombre2 
           nombre2  nombre3 
Retouner nombre2 
Fin 

L’algorithme retourne la valeur de nombre2, c’est-à-dire la valeur calculée par la suite de Fibonacci.

Que donne cet algorithme pour la valeur 10 ? Commençons au niveau de la boucle Pour. Elle itère de 0 à n-1, c’est-à-dire 9. Elle fait donc 10 tours. Lors du premier tour, le résultat stocké dans nombre3 est 1. Puisque...