Optimisation de la récursivité de la queue JavaScript

Bonjour lecteur.

Parfois, pour résoudre le problème, vous devez utiliser Recursion , qui a ses avantages et ses inconvénients. J'ai rencontré un problème de débordement de pile.

La profondeur de récursivité maximale est limitée par le moteur JavaScript. Vous pouvez compter avec précision sur 10 000 appels imbriqués, certains interprètes en autorisent davantage, mais pour la plupart d'entre eux, 100 000 appels dépassent le cadre des capacités. Il existe des optimisations automatiques qui aident à éviter de déborder la pile des appels («optimisation de la récursivité de queue»), mais elles ne sont pas encore prises en charge partout et ne fonctionnent que pour les cas simples.

Un exemple de fonction récursive:

function sum(n) { return n === 0 ? 0 : n + sum(n - 1) } sum(5) // 1 + 2 + 3 + 4 + 5 = 15 sum(100000) // Error: Maximum call stack size exceeded. 

La récursivité de queue permet d'optimiser les appels par le compilateur et est déjà dans la norme ES6 , mais la prise en charge du navigateur laisse beaucoup à désirer .

Un exemple de fonction récursive de queue:

 function sum(number, s = 0){ return number === 0 ? s : sum(number - 1, s + number) } 

Mais, sans prise en charge du navigateur, nous serons confrontés au même problème: le débordement de pile. Nous pouvons essayer d'utiliser avec Trampolining .

Nous allons écrire un décorateur qui prendra une fonction récursive modifiée (étape suivante) et l'exécutera en boucle, sans augmenter la profondeur d'appel.

 function trampoline(fn) { return function(...args) { let result = fn.apply(fn.context, args) while (typeof result === 'function') { result = result() } return result } } 

Maintenant, notre fonction récursive devrait retourner une fonction qui sera immédiatement exécutée par le décorateur. De cette façon, nous créerons conditionnellement un tableau de fonctions et les exécuterons tour à tour. Mais puisque nous renvoyons une nouvelle fonction anonyme à chaque fois, ce code fonctionnera un peu plus lentement.

 function sum(number, s = 0) { return number === 0 ? s : () => sum(number - 1, s + number) } 

Nous utilisons:

 const trampolineSum = trampoline(sum) trampolineSum(100000) // 5000050000 

Ceci est mon premier article. J'ai essayé de ne pas relire les concepts et j'ai fourni un lien vers les sources. Le sujet n'est pas unique et existe depuis longtemps sur les sites anglophones, malheureusement je ne l'ai pas trouvé en russe.

Merci de votre attention. Passez une bonne journée :)

Mettre à jour
Performances:

# 1 récursivité




# 2 Itération




# 3 Récursion de la queue et trampoline




# 4 Récursion de la queue et trampoline (un grand nombre)




Selon les résultats, nous constatons que notre décorateur, bien qu'il nous permette d'éviter l'erreur de débordement de pile, mais il fonctionne plus lentement que la version récursive et itérative. Cette méthode ne doit donc être utilisée que si vous ne pouvez pas remplacer la récursivité par l'itération ou si vous avez peur des débordements de pile lors de l'exécution de votre fonction récursive.