Les mille et un mystères du récursif

Tentative de vulgarisation et démystification du code récursif.

C’est quoi et surtout ça sert à quoi ?

Par “code récursif” j’entends une fonction ou une méthode de classe qui s’appelle elle-même.

On a souvent besoin de ça en programmation, ça permet notamment de parcourir une arborescence complète ou encore de faire des calculs mathématiques.

Arborescence ?

En fait, la plupart du temps on ne connaît pas la profondeur ($depth) de ce qu’on tente de lister.

Si on prend des cas WordPress, il vient tout de suite :

  • lister toute la hiérarchie d’une taxonomie (termes, sous-termes, etc)
  • lister toute la hiéarchie des pages (pages, sous-pages, etc) ou tout autre contenu hiérarchique

De manière plus globale, on peut en avoir besoin par exemple pour lister les répertoires et sous-répertoires d’un serveur.

remarque : il y a bien d’autres exemples évidemment

Ça reste compliqué en soi

Rassurez-vous si vous galérez un peu avec le récursif. Cela s’apprend avec l’expérience, il est assez rare qu’on y arrive du premier coup. Les exemples qui vont suivre sont volontairement simplifiés dans un premier temps.

Je ne pense absolument pas que nos métiers de développeurs consistent à tout savoir instantanément, bref à être des génies pour qui tout serait facile. Je ne suis d’ailleurs pas sûr que si tel était le cas, on ferait ce métier mais c’est un autre débat.

Bien au contraire, le jeu consiste à se confronter à la difficulté et à trouver comment en venir à bout.

Un exemple natif php

Prenez array_merge_recursive(), il s’agit d’un array_merge(), donc un mélange de tableaux php mais de manière récursive. Cela veut dire que, quelque soit le niveau de profondeur dans un ou plusieurs des tableaux qu’on souhaite mélanger, tout sera fusionné.

C’est impossible avec un array_merge() classique :

<?php
$arr1 = [111, "pill" => ["favorite" => "red"]];
$arr2 = [73, "pill" => ["favorite" => "blue"]];
$result1 = array_merge($arr1, $arr2);
$result2 = array_merge_recursive($arr1, $arr2);
print_r($result1);
print_r($result2);
?>

Affichera pour le cas array_merge() classique :

Array
(
    [0] => 111
    [pill] => Array
        (
            [favorite] => blue
        )

    [1] => 73
)

Alors que array_merge_recursive() affichera :

Array
(
    [0] => 111
    [pill] => Array
        (
            [favorite] => Array
                (
                    [0] => red
                    [1] => blue
                )

        )

    [1] => 73
)

Source

À un moment, dans sa propre déclaration, la fonction s’appelle elle-même pour réaliser cette fusion complète.

Pas mal de fonctions php natives utilisent ce principe.

Un exemple en javaScript

Y a que le php qui est concerné ?

Non. La récursivité est présente partout, dans tous les langages ou presque.

Tout Internet met en avant l’exemple avec factoriel, ici je vous parlerai de Fibonacci. Il s’agit d’une théorie mathématique qu’on retrouve dans de nombreux phénomènes naturels. On l’applique à la croissance des végétaux comme à celle des populations car dans cette suite mathématique tout nombre vaut la somme des deux précédents.

Concrètement :

1, 1, 2, 3, 5, 8, 13, 21, …etc

Pour simuler cet algo en js on ferait schématiquement :

function Fibonacci(integer) {
  if (integer < 2) {
    return 1;
  }
  return Fibonacci(integer - 1) + Fibonacci(integer - 2);
}

Éviter les pièges

Si on veut le voir autrement, faire un code récursif revient à décomposer un problème en dizaines, centaines, milliers de petits problèmes.

Cela va donc nous faciliter, en théorie, le débug. En pratique, cela s’avère très efficace la plupart du temps mais il faut savoir éviter certains pièges.

La boucle infinie

Une fonction récursive est une boucle infinie qui s’arrête.

What ?!!

Si je parcours l’arborescence d’un serveur, mieux vaut qu’elle soit finie sinon ma fonction recursive va tourner tant qu’elle trouve des éléments et ça peut durer longtemps comme ça…

Tu veux faire planter ton navigateur ?

<?php
while(1==1) {
	echo 'I am in...';
}
?>

En haut ou en bas ?

Connaître et avoir connaissance, pas vraiment la même chose. Je parlais d’expérience plus haut, une majeure partie du temps, les dévs vont s’appuyer sur des cas connus.

En gros :

j’ai déjà vu ce cas, il faut faire une récursion

Ce n’est pas une mauvaise chose, si le cas est déjà connu, on perdra le minimum de temps dessus.

Cependant il y a plusieurs types de récursion. On peut parler de récursion par le haut, et de récursion par le bas.

Récursion par le bas

La plus courante. La récursion arrive après qu’un premier cas, qu’on ne souhaite pas, a été éliminé. C’est ce que j’ai fait plus haut avec :

function Fibonacci(integer) {
  if (integer < 2) {
    return 1;
  }
  return Fibonacci(integer - 1) + Fibonacci(integer - 2);
}

Récursion par le haut

Et si on faisait :

function Fibonacci(integer) {
   if (integer > 1) {
     return Fibonacci(integer - 1) + Fibonacci(integer - 2);
   }
   return 1;
 }

après tout, quelle différence ?

Ici un avantage majeure à faire plutôt par le bas que la haut : une bien meilleure lisibilité.

Je me demande aussi s’il n’y aurait pas une optimisation de perf à la compilation. Mais vu que je n’ai pas fait le test ici et que je ne connais pas bien les implications, à savoir, est-ce que cela serait de la micro-optimisation ou un gain concret, je laisse cet argument de côté.

Un bon code est un code lisible.

Stack overflow

Et oui c’est le piège ahaha… 🙂

Pour faire simple, prenons javaScript, on va avoir ce qu’on appelle une call stack. Cette pile d’exécution garde la trace de vos fonctions 🙂

Or, c’est toujours la même chose, une pile c’est un espace fini. Si votre récursion est trop forte (trop profonde) vous allez excéder la pile et planter le système et c’est assez vite atteint !

Vous aurez alors “overflow” la “stack” !

Conclusion

La récursion c’est un peu chiant mais il serait surprenant que vous ne la rencontriez jamais dans votre métier de dév. Alors accrochez-vous. Ce n’est pas grave, c’est même normal d’avoir un peu de mal au début et même après.

À force d’en faire, et, j’espère, après avoir lu ce billet, vous éviterez les pièges classiques et vous construirez des labyrinthes merveilleux :