La récursivité

Niveau:

Aujourd’hui nous allons parler d’un concept très utile en programmation, car il est au cœur de plusieurs algorithmes très utiles. Je parle bien entendu de la récursivité. Ce tutoriel est un peu plus corsé que celui sur les fonctions ou sur le tri à bulles, c’est pourquoi je te recommande de te préparer deux cafés ! Mais avant de faire parler la caféine, commençons déjà par répondre à cette question …

C’est quoi la récursivité ?

Voici la définition que Wikipédia donne d’un algorithme récursif:

Un algorithme récursif est un algorithme qui résout un problème en calculant des solutions d’instances plus petites du même problème. L’approche récursive est un des concepts de base en informatique. Les premiers langages de programmation qui ont autorisé l’emploi de la récursivité sont LISP et Algol 60.

…Mais qu’est-ce que ça veut dire ? Nous avons déjà vu ensemble qu’un algorithme est une suite d’étapes logiques, exécutées les unes à la suite des autres et qui ont pour but de répondre à un problème donné. Et bien un algorithme récursif est un algorithme qui décompose un problème en sous parties de lui-même et qui résout l’ensemble de ces sous parties pour résoudre le problème entier …

Le laisser passer A38 !

Ouais ça ne nous aide pas beaucoup non plus, il nous faut un exemple !

La suite de Fibonacci

Nous allons étudier un problème qui peut être facilement résolu à l’aide de la récursivité, et ce problème, c’est la suite de Fibonacci.

La suite de Fibonacci est une suite d’entiers dans laquelle chaque terme est la somme des deux termes qui le précèdent. Elle commence généralement par les termes 0 et 1 (parfois 1 et 1) et ses premiers termes sont : 0, 1, 1, 2, 3, 5, 8, 13, 21

La suite de Fibonacci est donc une suite de nombres dont chacun des nombres se calcule en additionnant deux autres nombres … Et comment les obtient-on, ces deux nombres ? En allant les chercher dans la suite de Fibonacci pardi, nous sommes donc bien face à un problème qui se résout à l’aide de sous parties de lui-même ! En effet on démarre la suite à l’aide des nombres 0 et 1, seuls nombres qui ne sont pas calculés mathématiquement mais donnés dès le départ. Essayons de calculer le 4ème nombre de la suite de Fibonacci !

4ème nombre = 3ème nombre + 2ème nombre

On connaît déjà le 2ème nombre, il s’agit de 1 ( les deux premiers nombres sont donnés ), mais on ne connaît pas le 3ème nombre qu’à cela ne tienne:

3ème nombre = 2ème nombre + 1er nombre
3ème nombre = 1 + 0 = 1

Maintenant que l’on a le 3ème nombre, on peut calculer le 4ème :

4ème nombre = 3ème nombre + 2ème nombre
4ème nombre = 1 + 1 = 2

Il s’agit donc bien d’un problème qui peut se résoudre en résolvant des sous parties de lui-même. Bien entendu il y a toujours une limite de profondeur à partir de laquelle on est obligé de s’arrêter ( trouver une solution ), ici cette limite consiste à fournir les deux premiers nombres, ceux qui démarrent la suite. Si l’on essaie de rédiger l’algorithme en bon français, voilà ce que ça donnerait:

  • Notre algorithme se nomme « Fibo » et prend un paramètre « n » correspondant à la position du nombre dans la suite de Fibonacci.
  • Si « n » vaut 2, retourner la valeur 1 et stopper l’algorithme.
  • Sinon si « n » vaut 1 retourner la valeur 0 et stopper l’algorithme.
  • Sinon si « n » est inférieur à 1, retourner la valeur 0 et stopper l’algorithme.
  • Sinon
  • Créer une valeur nommée « result » et initialiser sa valeur à 0.
  • Créer une valeur nommée « a » et initialiser sa valeur à Fibo(n-1)
  • Créer une valeur nommée « b » et initialiser sa valeur à Fibo(n-2)
  • Stocker dans « result » la valeur correspondant à « a + b »
  • Retourner la valeur contenue dans « result ».

… Fiou mais à quoi ça sert ?

Et bien contrairement à ce que l’on pense, la récursivité, si elle n’est pas omniprésente en programmation, est quand même très présente. Son application va du calcul de fractales à la génération de labyrinthe en passant par les jeux vidéos.

Une fois la récursivité maîtrisée, la génération de labyrinthe n’aura plus de secrets pour vous !

Si tu veux voir de quoi il en retourne tu peux te rendre sur la page Wikipédia suivante et sur ce dépôt github où tu trouveras un exemple d’implémentation de la suite de Fibonacci ainsi qu’un algorithme récursif de génération de labyrinthe. Ce tutoriel est désormais terminé j’espère qu’il t’as plu, je te dis à bientôt devant un petit café !

1 commentaire pour “La récursivité

  1. En effet, c’est pas évident à comprendre de suite mais du coup faut relire plusieurs fois jusqu’à que ça rentre dans la tête 😇

    Hâte de voir la suite 👌

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *