Présentation de la récursion

La récursion est un concept que les développeurs apprennent tôt et utilisent pendant des années. Si l'étape récursive est simple et le cas de base est correct, le code semble propre et sûr.

La récursion est élégante pour une raison : de nombreux problèmes sont naturellement récursifs, et le code reflète souvent la logique telle que nous l'expliquons à haute voix. Pour les parcours d'arbres, les structures imbriquées et les modèles de division et de conquête, la récursion peut être plus facile à lire que les boucles explicites.

Limites physiques de la récursion

Mais il y a un piège : les limites physiques. Même avec un cas de base correct et une logique saine, chaque appel récursif consomme encore de l'espace sur la pile. À une certaine profondeur, vous rencontrez une erreur de débordement de pile.

Pour illustrer cela, considérons une fonction récursive simple qui calcule la somme de tous les entiers de 1 à n : 

function sum(n) { if (n === 0) return 0; return n + sum(n - 1); }

Lorsque nous appelons cette fonction avec une grande valeur de n, nous obtenons une erreur de débordement de pile : 

sum(100000); // RangeError ou InternalError : trop de récursion dans la plupart des runtime JavaScript

Optimisation des appels de queue

La prochaine étape habituelle est l'optimisation des appels de queue. L'idée est simple : faire en sorte que l'appel récursif soit la dernière chose que la fonction fasse, afin que le runtime puisse réutiliser le même cadre au lieu d'en pousser un nouveau.

Cependant, même avec une structure de récursion correcte, de nombreux runtime JavaScript n'implémentent pas toujours l'optimisation des appels de queue de manière fiable. Cela signifie que vous ne pouvez pas supposer que la récursion est sûre pour la pile dans le code JavaScript de production, même si le code est correctement structuré pour l'optimisation des appels de queue.

Itération et trampolines

Chaque fonction récursive peut être réécrite de manière itérative, ce qui est souvent le choix le plus sûr en production lorsque la profondeur de l'entrée peut augmenter. L'itération ne repose pas sur les optimisations de runtime pour la sécurité de la pile, car elle ne consomme pas de cadres de pile par étape.

Vous pouvez également utiliser un trampoline : une boucle qui appelle répétitivement une fonction qui retourne soit un résultat final, soit une autre fonction à appeler. Cela permet de conserver la structure récursive tout en évitant la croissance de la pile : 

function trampoline(fn) { let result = fn; while (typeof result === 'function') { result = result(); } return result; }

Ces techniques permettent de conserver la structure récursive tout en évitant les limites physiques de la pile, ce qui est particulièrement utile lorsque la profondeur de l'entrée peut augmenter.