Comprendre les fonctions récursives

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.

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
}

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

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

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.

Le secret pour maitriser les fonctions récursives, c'est de pratiquer. Vous pouvez vous procurer la Fiche d'entraînement : Fonctions récursives en achat unique sur la boutique.