Comprendre la récursivité en 7 min

La récursivité est un concept fondamental, utilisé absolument partout. Ça paraît compliqué au début, mais en fait c’est très simple. Si pour toi la récursivité est un concept inconnu, ou tout simplement complexe, je te parie qu’en 5 minutes t’auras plus jamais à galérer dessus.

C’est quoi la récursivité ?

La récursivité c’est quand une fonction s’appelle elle-même jusqu’à atteindre une condition d’arrêt. Elle arrête alors de s’appeler elle-même. Le résultat de chaque fonction enfant est retourné dans les fonctions parent, jusqu’à retourner à la fonction originale. Cette explication est peut-être pas tout à fait claire tout de suite, mais ça va le devenir!

Le concept même de la récursivité est relativement simple en vérité. C’est l’implémentation qui fait buger beaucoup de développeurs. Pour débloquer tout ça, on va commencer tout de suite par faire un premier schéma high level du concept.

Je veux que tu aies une image mentale de ce dont on parle avant même de commencer à regarder du code.

Je veux que tu intègres tout de suite un concept clef dans la récursivité : quand une fonction s’appelle elle-même, la fonction enfant fait partie de l’exécution de la fonction parent. Autrement dit, l’exécution de chaque fonction est imbriquée de plus en plus profondément à chaque appel.

Et là, tu commences à comprendre pourquoi sans condition d’arrêt, ça devient très vite un problème.

Maintenant qu’on a bien cette idée de fonction qui s’appelle soit même de manière imbriquée, on peut commencer à regarder du code.

La version simplifiée

La première fois qu’on m’a expliqué la récursivité, on m’a tout de suite donné en exemple la célèbre suite Fibonacci. Je voulais faire pareil aujourd’hui et puis je me suis rappelé à quel point j’avais trouvé ça compliqué comme introduction. À cause de ça, utiliser de la récursivité m’a impressionné pendant longtemps. Je trouvais ça limite surréaliste comme concept.

On va t’éviter cette enfer. On va regarder des exemples plus poussés après, mais d’abord on va regarder l’exemple le plus simple auquel je puisse penser. On va compter à l’envers en partant de 2. Oui je sais, on fait trop les fifous, attention les yeux, c’est parti.

Python (3.8.2)

def count_down(number):
  if number <= 0:
    return

  print(number)
  count_down(number - 1)

count_down(2)
#2
#1

Test et joue avec le code en live ici ! –> https://repl.it/@jesuisundev/recursion-count-down-python

Javascript (NodeJS 12.16.1)

function countDown (number) {
  if (number <= 0) {
    return
  }

  console.log(number)
  countDown(number - 1)
}

countDown(2)
//2
//1

Test et joue avec le code en live ici ! –> https://repl.it/@jesuisundev/recursion-count-down-node

Alors oui, le "problème" de cet exemple devrait être réglé de façon itérative avec une simple boucle, mais on s'en fout en fait là. Comprenons d'abord le concept avant de s'attaquer à des problèmes qui nécessitent vraiment de la récursivité.

Pour faire ça, on va détailler chaque étape de cet algorithme. Il y a trois grandes étapes pour chaque algorithme récursif.

1. La condition d'arrêt
2. La résolution du problème
3. L'appel récursif

On va se baser sur le bout de code en Javascript pour l'explication :

---

• Condition d'arrêt (ligne 2)

Quand tu écris une fonction récursive, le premier truc que tu veux faire c'est de vérifier si la récursivité doit s’arrêter. Autrement dit, si la fonction ne doit plus s’appeler soit même. Cette condition est obligatoire ! Sans elle, ça va être le bordel très vite.

Ici, c'est très simple, notre cas d'arrêt c'est quand le chiffre dont on fait le décompte arrive à 0 ou en dessous. Si le chiffre courant est à 0, notre décompte est fini et on arrête la récursivité en sortant tout de suite de la fonction courante avec un return (ligne 3).

---

• Résolution du problème (ligne 6)

On va en parler plus dans la partie d’après, mais le principal principe de la récursivité c'est de réduire le problème à sa plus petite forme. Cette résolution via sous-problème va régler le problème de façon récursive.

Ici notre problème est simple : on veut juste afficher le chiffre courant. On le fait de façon nonchalante à la ligne 6 avec un console.log.

---

• L'appel récursif (ligne 7)

Pour que la récursivité fonctionne, le cœur du concept c'est que la fonction s'appelle elle-même pendant son exécution. C'est exactement ce qu'on fait ici à la ligne 7.

Il est important également de comprendre que c'est là qu'on soustrait une unité au nombre dont on fait le décompte (dans le paramètre de l'appel de la fonction). Si on le fait pas, non seulement on va afficher le même nombre à chaque fois, mais surtout on va le faire à l'infini! !

Pour bien que tu comprennes ce qui se passe dans cette fonction je vais reprendre le schéma high level plus haut. Mais cette fois, je vais appliquer ce qu'on vient de voir dans le bout de code pour faire le décompte.

Normalement avec tout ça tu devrais commencer à bien percuter ce qui se passe dans le code, et donc le fonctionnement de la récursivité. Si c'est pas le cas, prends ton temps, relis les exemples, joue avec le code via Repl. Ne passe pas à la partie suivante sans bien comprendre cet exemple sinon ça va plus t'embrouiller qu'autre chose.

Comment ça marche ?

Jusqu'ici, on a vu le fonctionnement high level de la récursivité et comment le concept se comporte dans la partie visible. Mais comment ça marche en vrai derrière ? Comment la machine comprend et gère ce concept d’imbrication d'exécution de fonction ? Comment elle garde le bon ordre d’exécution de tout ça ?

Pour le savoir, on doit regarder plus profondément.

Cette partie ne va pas être claire si tu ne connais pas l'une des structures de données fondamentales en informatique : la pile (ou stack). Si tu ne la connais pas, pas de panique, j'ai fait un article sur le sujet ou je t'explique tout ce que tu dois savoir.

La récursivité utilise ce qu'on appelle la pile d'exécution pour son fonctionnement. La pile d'exécution a le même fonctionnement qu'une pile traditionnelle, sauf qu'elle gère les fonctions actives du programme. Autrement dit, quand un programme appelle une fonction, cette fonction va au-dessus de la pile d'appels.

Et donc, comme le fonctionnement d'une pile l'impose, la fonction au top de la pile sera la première à être exécutée. C'est à dire que la dernière fonction appelée sera celle exécutée. Faisons un dessin reprenant l'exemple d'avant pour que ça soit plus clair.

La fonction counDown(2) est appelée et s’exécute normalement jusqu'à appeler countDown(1). countDown(1) passe donc au top de la pile et s'exécute alors avant que countDown(2) ne finisse. C'est alors que countDown(1) appelle countDown(0). countDown(0) passe alors première dans la pile d'exécution et s'exécute donc avant tout le monde.

Une fois que countDown(0) finit son exécution elle est alors sortie de la pile d'exécution. La machine regarde alors quel est la fonction suivante au top de la pile. C'est au tour de countDown(1) de continuer son exécution là où elle s'est arrêtée. Et la même chose arrivera pour countDown(2) ensuite.

C'est ainsi que le bon fonctionnement et l'ordre d'exécution de la récursivité est garanti! Maintenant que t'as tout compris comment ça fonctionnait de l'extérieur à l'intérieur, regardons sur quel genre de questions tu risques de tomber en entretien.

Ce que tu vas voir en entretien

Car oui, l'exemple hyper simple de compter de 2 à 1, c'est pas ça qu'on va te demander. C'est bien pour comprendre ce qui se passe, mais dans la vraie vie ça sert à rien. Pendant un entretien on va te poser des problèmes qui hurlent récursivité quand tu lis l'énoncé.

À mon premier travail, je me souviens qu'il avait un test technique bien spécial pour accepter ou refuser une jeune recrue. Les stagiaires et premiers emplois passaient tous par ce fameux test. Ça peut paraître futile pour un développeur un peu plus expérimenté, mais pour un jeune c'est vite complexe.

---

Nous avons un dossier rempli de chat que nous aimons beaucoup. Avec l'export JSON de l’arborescence de ce dossier donnée ci-dessous, écrivez une fonction qui permet de récupérer tous les noms de chat dans un tableau.

[
    {
        'type': 'folder',
        'name': 'cats',
        'children': [
            {
                'type': 'image',
                'name': 'Buffy'
            },
            {
                'type': 'image',
                'name': 'Gizmo'
            },
            {
                'type': 'folder',
                'name': 'small-cat',
                'children': [
                    {
                        'type': 'image',
                        'name': 'Fluffy'
                    },
                    {
                        'type': 'image',
                        'name': 'Harry'
                    },
                    {
                        'type': 'folder',
                        'name': 'black-cat',
                        'children': [
                            {
                                'type': 'image',
                                'name': 'Daisy'
                            },
                            {
                                'type': 'image',
                                'name': 'Toby'
                            }
                        ]
                    },
                    {
                        'type': 'folder',
                        'name': 'white-cat',
                        'children': [
                            {
                                'type': 'image',
                                'name': 'Minnie'
                            },
                            {
                                'type': 'image',
                                'name': 'Lucy'
                            }
                        ]
                    }
                ]
            },
            {
                'type': 'folder',
                'name': 'future-cat',
                'children': []
            }
        ]
    }
]

L'ordre, le nombre et les niveaux de sous dossiers sont fréquemment changés, nous souhaitons donc une solution qui s'adapte à ces changements.

---

Côté réponse candidat, y'avait que deux scénarios. Ceux qui ne connaissaient pas ou ne savaient pas appliquer la récursion. Ils faisaient des espèces de solutions de fous avec des boucles dans tout les sens. Ils n'étaient pas rappelés.

Et tu avais ceux qui connaissaient et savaient appliquer la récursivité. Leur solution ressemblait à ça.

Javascript (NodeJS 12.16.1)

const dump = [
    {
       ...
    }
]

const catNamesArray = []

function catNames(folder) {
    for(object of folder) {
        if(object.type === 'image') {
            catNamesArray.push(object.name)
        } else if(object.type === 'folder') {
            catNames(object.children)
        }
    }
}

catNames(dump)
console.log(catNamesArray)
//['Buffy', 'Gizmo', 'Fluffy', 'Harry', 'Daisy', 'Toby', 'Minnie', 'Lucy']

Test et joue avec le code en live ici ! –> https://repl.it/@jesuisundev/folder-recursion-node

Python (3.8.2)

dump = [
    {
       ...
    }
]

cat_names_array = []

def cat_names(folder):
    for object in folder:
        if object['type'] == 'image':
            cat_names_array.append(object['name'])
        elif object['type'] == 'folder':
            cat_names(object['children'])

cat_names(dump)
print(cat_names_array)
#['Buffy', 'Gizmo', 'Fluffy', 'Harry', 'Daisy', 'Toby', 'Minnie', 'Lucy']

Test et joue avec le code en live ici ! –> https://repl.it/@jesuisundev/folder-recursion-python

Pour bien comprendre, n'hésite pas à prendre papier/stylo et refaire les schémas que j'ai fait plus haut, mais avec cet algorithme là. Il faut que tu passes par cette phase de concentration et compréhension pour pouvoir appliquer facilement la récursivité dans le futur. Je peux pas t'aider plus sur ce point-là, c'est à toi de prendre le temps pour.

En tout cas, à mon premier travail, ceux qui avaient pris le temps de la bonne compréhension étaient rappelés pour une proposition. Tu veux faire partie de ces gens-là. Et de toute façon, tu vas avoir de la récursivité partout, autant bien s'y préparer.

Épilogue

La récursivité permet de réduire un problème à sa plus petite forme pour simplifier la solution. Une solide compréhension de ce concept est ABSOLUMENT obligatoire en tant que développeur. Pour aller plus loin, je te conseille mon article sur les algorithmes de tri, les deux derniers algorithmes (merge sort, quick sort) ont une utilisation avancée de la récursivité.