Comprendre la récursivité en 7 min

En dehors du titre, le générique masculin est utilisé sans aucune discrimination et uniquement dans le but d'alléger le texte.

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.



récursivité


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.



arret


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.



récursivité


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.



condition


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.



récursivité


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.



deeper


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.



récursivité


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.



récursivité




É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é.

Qui me parle ?

jesuisundev
Je suis un dev. En ce moment je suis Backend Développeur / DevOps à Montréal. Le dev est l'une de mes passions et j'écris comme je parle. Je continue à te parler quotidiennement sur mon Twitter. Tu peux m'insulter à cet e-mail ou le faire directement dans les commentaires juste en dessous. Y'a même une newsletter !

4 commentaires sur “Comprendre la récursivité en 7 min”

  1. Toujours aussi bien expliqué, génial !
    Et puis, rien à voir avec le dev, mais j’ai remarqué que tu avais de bons goûts cinématographique ^^

  2. Alors moi j’ai juste une remarque, c’est que la condition d’arrêt, c’est quelque chose que l’on fait généralement sur les boucles. Mais dans la vraie vie, sur des vraies utilisations, on met rarement une condition d’arrêt dans la récursion, mais plutôt une condition de récursion. Ce que je veux dire par là, c’est que la récursion est rarement un comportement par défaut qu’il faut arrêter, mais plutôt un comportement qu’on ne va avoir que sous certaines conditions. Comme dans l’exemple des noms de chat, en fait.

    C’était une simple remarque, parce que je trouve que la condition d’arrêt, c’est un peu perturbant comme vision par rapport à mon utilisation de la récursion.

T'en penses quoi ?

Your email address will not be published. Required fields are marked *