Salut et bienvenue dans ce nouvel épisode du podcast de Code Garage,
je m'appelle Nicolas Brondin Bernard et aujourd'hui on va reprendre une des bases de la programmation.
Si vous l'avez déjà vu en cours pendant votre formation,
eh bien ça sera sûrement juste un petit rappel,
mais il se peut que si vous avez appris la programmation par vous même,
ou voilà sur une plateforme de formation en ligne,
peut-être que vous êtes passé à côté de ce concept,
et ce concept c'est la récurcivité.
Alors la récurcivité c'est une technique de programmation,
ou simplement une fonction va s'appeler elle-même pour résoudre un problème.
Ça permet de diviser un problème complexe en sous problème plus simple,
jusqu'à atteindre un cas, qu'on appelle un cas de base,
qui est une situation où la fonction peut simplement retourner une solution sans s'appeler elle-même à nouveau.
Alors quand on utilise des boucles,
parce que le concept de récurcivité ça fait évidemment quand même appel au concept de boucle,
dans les boucles on parle de condition d'arrêt,
et en récurcivité on va plutôt appeler ça un cas de base.
Alors comme je l'ai dit, la fonction récurcive,
elle va en fait avoir deux parties essentielles.
Le cas de base, dont on vient de parler,
c'est à condition qui met fin à la récursion,
sans cas de base vous doutez,
la fonction elle entrerait dans une espèce de boucle infini,
en tout cas un appel infini d'elle-même,
donc là ça pose de gros problèmes,
et la deuxième partie essentielle c'est l'appel récursif.
C'est l'invocation de la fonction à l'intérieur d'elle-même
pour s'approcher progressivement du cas de base.
Alors un des exemples classiques de récurcivité,
c'est par exemple le calcul de la factorial d'un nombre.
La factorial d'un nombre, par exemple nombre N,
c'est le produit de tous les entiers de 1 à N.
Alors ne partez pas, parce que même si ça fait peur comme ça,
c'est un concept très très simple en mathématiques.
Par exemple, la factorial du nombre 5,
le calcul équivalent c'est simplement 1 x 2 x 3 x 4 x 5,
ce qui nous donne le résultat 120.
Voilà ce qui est une factorial,
et donc l'utilisation de la récursivité
s'est utilisée pour résoudre plein de problèmes mathématiques,
et notamment la factorial,
c'est quelque chose qui simplement très bien grâce à une fonction récursive.
Donc par exemple, pour prendre un exemple d'un pseudo-code
d'une fonction récursive pour résoudre la factorial d'un nombre,
on va créer une fonction, comme on va appeler par exemple factorial,
qui prend par un maître N un entier positif.
Et là, on va avoir une condition divisée en deux.
D'abord, on va avoir si N est égal à 0 ou 1,
alors on va retourner 1, ça c'est notre cas de base,
et sinon, là ça va être l'appel récursif,
sinon on va retourner N multiplié par un appel à la fonction factorial,
donc elle-même, avec entre parenthèses en passant N-1,
et ensuite on termine simplement notre fonction.
Donc par exemple, si on prend un appel simple,
si on fait appel à factorial de 3,
et bien on va ensuite retourner, cette fonction va retourner un appel à N
multiplié par factorial de N-1, donc ça va être tout simplement 3x factorial de N-1,
c'est 2, qui va ensuite elle-même retourner plutôt 2x factorial de 1-1, etc.
Et ensuite, quand on atteint le cas de base où N est égal à 0 ou à 1,
on va retourner 1 et donc chaque fonction va pouvoir retourner,
et donc on va remonter, on va dépiler la pile d'appel de fonction.
Alors juste un petit point, c'est parce qu'en par convention, en mathématiques,
la factorial de 0, c'est 1, ça c'est une convention,
il n'y a pas besoin de le comprendre spécifiquement,
mais c'est juste pour vous expliquer pourquoi est-ce que le cas de base,
c'est si N est égal à 0 ou à 1, c'est simplement pour prendre en compte cette convention.
Donc ça, c'était juste pour vous donner un exemple d'un appel récursif,
on a la fonction factorial qui s'appelle elle-même,
mais évidemment avec un paramètre différent à chaque fois,
un paramètre qui va décroître jusqu'à ce que ce paramètre soit égal à l'une des valeurs
qui correspond au cas de base. Alors pour l'implementer par exemple en JavaScript,
ce serait exactement pareil, on ferait function factorial N, le paramètre,
et ensuite on ferait if N égal égal 0 ou N égal égal 1,
alors on return 1 et sinon, on return N fois factorial de N moins 1.
Et ensuite, on a simplement appelé cette fonction-là et ça va fonctionner exactement la même manière.
Évidemment, vous l'aurez peut-être compris,
on peut résoudre ce problème de factorial avec une boucle.
On aurait pu faire par exemple la fonction factorial en JavaScript toujours,
aurait pu être factorial N, on va faire un let result equal 1,
et ensuite on va faire while N donc supérieur à 1,
alors result fois N, et ensuite on fait N moins 1 et on return le result.
En fait, cette boucle-là va faire avoir exactement le même effet que ce qu'aurait eu notre fonction récurcive.
Et donc simplement la vraie différence qu'il y a entre ces deux implementations pour résoudre le même problème,
c'est que la version récurcive, on n'a pas besoin d'une variable result, comme on avait la variable intermédiaire.
Alors du coup, ça nous amène à une question, pourquoi utiliser la récurcivité ?
En réalité, la récurcivité, ça permet principalement de rédiger un code plus épuré et plus élégant,
mais attention, il y a un vrai désavantage, c'est qu'une solution récurcive est souvent plus lente qu'une solution iterative.
Une solution iterative, c'est une boucle.
Donc hormis pour certains langages compilés,
parce que certains langages compilés ont des optimisations,
et notamment pour la récurcivité, c'est une optimisation de la résolution du cas de base,
ça c'est quelque chose qui se fait automatiquement par le compilateur.
Et donc en réalité, hormis pour ces points très spécifiques,
et sinon il y a quelques cas d'usage où la récurcivité est intéressante en termes de syntaxe,
comme le parcours d'arbre, le parcours de liste chaînée,
ou généralement quand un problème peut être divisé en sous-problème très facilement.
Mais il faut faire très attention, parce qu'il y a quelque chose dont on n'a pas parlé,
mais qui est la profondeur de la récursion,
parce qu'à chaque fois que vous appelez une fonction,
surtout si une fonction récurcive qui s'appelle elle-même,
et bien ça va faire grossir la pile d'appels.
C'est quelque chose qui stockent tous les appels de fonction,
et donc elle peut se remplir, et l'exécution de votre programme peut s'arrêter complètement
si jamais cette pile d'appels est remplie.
On parle de dépassement de piles ou aussi de stack overflow.
Donc est-ce qu'il faut utiliser une fonction récurcive ?
Non, pas forcément, justement quand vous avez une fonction qui marche bien avec une boucle par exemple,
l'appel et une boucle sera souvent plus efficace et vous éviterez un problème de dépassement de piles.
Maintenant vous trouverez plein de codes où il y a une solution récurcive qui est utilisée,
et donc c'est important à connaître.
Et parfois très sincèrement, surtout quand vous n'avez pas un nombre de récursions trop élevés,
ça donne des solutions vraiment élégantes et vraiment plus faciles à lire,
quand on connaît évidemment la récursivité.
Alors si jamais vous voulez aller encore un petit peu plus loin dans la compréhension des avantages
et des inconvénients justement sur la récurcivité,
je vous mettrai un article en lien dans les notes de l'épisode.
Alors c'est un article en anglais, mais vous avez, voilà, on va encore un petit peu plus loin dans la compréhension.
En tout cas, de mon côté, j'espère vraiment que ça vous aura apporté quelque chose.
Si vous ne connaissiez pas le concept de récurcivité,
et bien au moins maintenant vous comprenez, j'espère, le concept de base.
Et si vous connaissiez déjà, et bien savoir parler un petit peu des performances
et des cas problématiques, ça vous a peut-être aidé.
Moi je vous donne rendez-vous la semaine prochaine pour un prochain épisode du podcast
ou directement sur coteirigarage.fr pour retrouver tous les épisodes du podcast,
tous les articles de blogs, on en sort évidemment un par semaine.
Et surtout, tous nos cours complets pour apprendre le HTML, le CSS, le JavaScript, le PHP.
Et car oui, je vous l'annonce, le cours PHP sort très très vite.
Et il y a plein d'autres choses, on peut apprendre à devenir freelance,
à apprendre à mieux se faire recruter pour son premier emploi.
Il y a énormément de cours complets.
Allez voir sur coteirigarage.fr et vous pouvez aussi partager vos projets.
Voilà, vous créez un profil public pour envoyer au recruteur
et avec vraiment une belle interface et tout ce que vous avez besoin
pour mettre en avant vos compétences.
Donc ça, c'est accessible juste avec un compte gratuit évidemment.
Donc voilà, n'hésitez pas à venir faire un tour, coteirigarage.fr.
Et moi, je vous donne rendez-vous la semaine prochaine pour un prochain épisode.
Salut !