Comprendre les fonctions récursives

Cet article est libre d'accès pour tous grâce à la générosité des abonnés de Mindsers Blog qui soutiennent notre blog indépendant. Si vous appréciez le contenu que je propose, je vous invite à vous abonner dès aujourd'hui.

Les fonctions récursives font partie de mes techniques de développement préférées. Il ne s'agit pas de quelque chose de compliqué. Bien au contraire, ce ne sont que des fonctions utilisées différemment.

Lorsque nous apprenons la récursion, et plus largement, l'itération en programmation, nous nous arrêtons toujours sur les structures classiques d'itération, les boucles. Mais, elles n'ont pas le monopole de l'itération ! Dans cet article, je vais rapidement vous parler d'une autre structure de récursion.

😅
J'ai longtemps cru que j'avais écrit un article ici sur les fonctions récursives. Je découvre aujourd'hui que ce n'est pas le cas alors je corrige ça.

La récursion et les boucles

Lorsque nous parlons de récursion, nous parlons généralement de répéter des choses. En informatique, il s'agit de la capacité à faire se répéter une quantité définie d'instructions.

Comme nous l'avons dit, la méthode classique consiste à utiliser les boucles pour cela. Les langages de programmation proposent généralement plusieurs types de boucles :

  • les boucles while
  • les boucles do...while
  • les boucles for

Mais, il en existe encore d'autres. En JavaScript, par exemple, nous pouvons rajouter celles-ci à la liste :

  • les boucles for...in
  • les boucles for...of

Généralement, les boucles ajoutées par les langages, en plus des trois premières, ne sont finalement que des déclinaisons particulières des trois premières boucles.

Je ne vais pas vous expliquer les boucles ici. Elles pourraient faire l'objet d'un article à elles toutes seules. Ce qu'il faut retenir ici, c'est que les boucles sont des structures itératives offertes par un langage pour permettre de répéter un ensemble d'instructions.

const list = ['one', 'two', 'three']

for(const element of list) {
  // tout ce qui se trouve entre les deux accolades 
  // sera répété autant de fois qu'il y a d'element 
  // dans list
}
Exemple de boucle en JavaScript

La récursion et les fonctions

Contrairement aux boucles, les fonctions ne sont pas des structures itératives en tant que telles. Elles permettent de séparer une suite d'instructions du reste du code pour pouvoir les exécuter à nouveau plus tard, à la demande.

Cette dernière phrase ressemble un peu à une structure itérative, mais voici les principales différences que l'on peut noter :

  • Une fonction définie peut n'être appelée qu'une fois, voire même jamais.
  • S'il y a répétition (exécution plusieurs fois), elle ne sera ni immédiate ni linéaire contrairement à une boucle.

Une fonction n'est donc pas une structure itérative prévue par le langage. Ce qui va rendre une fonction récursive, et donc permettre l'itération, c'est l'utilisation que va en faire le développeur.

Voyons comment rendre une fonction récursive.

function addOne(base, times = 1) {
    let result = base
    
    for (let i = 0; i < times; i++) {
        result += 1
    }
    
    return result
}

addOne(5, 3) // === 8
Fonction qui utilise l'itération grâce à une boucle

Cette fonction n'est pas récursive. Elle ajoute 1 à un nombre donné en paramètre autant de fois que spécifiées par la variable times.

Comment faire maintenant, pour avoir le même résultat sans les boucles ?

function addOne(base, times = 1) {
    if (times <= 0) return base
    
    const result = base + 1
    return addOne(result, times - 1) // tout se passe ici
}

addOne(5, 3) // === 8
Fonction qui utilise l'itération grâce à la récursion

La fonction récursive ne change pas de signature. Elle prend toujours en paramètres les variables base et times. Elle retourne toujours un nombre.

Ce qui change ici : la fonction s'appelle elle-même. C'est tout.

Reprenons les étapes avec les paramètres base = 5 et times = 3 pour bien comprendre :

  1. Est-ce que times est inférieur ou égale à 0 ? Non, elle est égale à 3, on continue.
  2. result est égale à base plus 1, soit 5 + 1, soit 6.
  3. On passe le result et times - 1 à la fonction addOne et on retournera directement sa valeur de retour.
  4. Est-ce que times est inférieur ou égale à 0 ? Non, elle est égale à 2, on continue.
  5. result est égale à base plus 1, soit 6 + 1, soit 7.
  6. On passe le result et times - 1 à la fonction addOne et on retournera directement sa valeur de retour.
  7. Est-ce que times est inférieur ou égale à 0 ? Non, elle est égale à 1, on continue.
  8. result est égale à base plus 1, soit 7 + 1, soit 8.
  9. On passe le result et times - 1 à la fonction addOne et on retournera directement sa valeur de retour.
  10. Est-ce que times est inférieur ou égale à 0 ? Oui, on retourne base, qui est égale à 8.

En le faisant par étape, nous comprenons mieux comment une fonction récursive peut remplacer complément une structure d'itération comme la boucle.

☝️
Aucune solution n'est meilleure entre la fonction récursive et les boucles. Tout dépend de la situation. Voyez-le comme un outil supplémentaire que vous pourrez utiliser pour certains algorithmes particuliers.

Le secret pour maitriser les fonctions récursives, c'est de pratiquer. Ci-dessous, vous trouverez quelques exercices que je vous ai préparés pour vous permettre de progresser sur le sujet 👇

Vous pouvez également vous procurer la Fiche d'entraînement : Fonctions récursives en achat unique sur la boutique.

This free post contains additional content for Full Mindsers Blog and Friend of Mindsers Blog members only

Join the 100+ developers and entrepreneur, premium members of our community and get full access to our library of private posts and additional content.

Become a member

Already a member? Log in