Optimización de recursión de cola de JavaScript

Hola lector

A veces, para resolver el problema, debe usar Recursion , que tiene sus ventajas y desventajas. Me encontré con un problema de desbordamiento de pila.

La profundidad máxima de recursión está limitada por el motor de JavaScript. Puede contar con precisión con 10,000 llamadas anidadas, algunos intérpretes permiten más, pero para la mayoría de ellas 100,000 llamadas están fuera del alcance de las capacidades. Existen optimizaciones automáticas que ayudan a evitar el desbordamiento de la pila de llamadas ("optimización de recursión de cola"), pero aún no son compatibles en todas partes y funcionan solo para casos simples.

Un ejemplo de una función recursiva:

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 recursividad de cola permite optimizar las llamadas del compilador y ya está en el estándar ES6 , pero el soporte del navegador deja mucho que desear .

Un ejemplo de una función recursiva de cola:

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

Pero, sin el soporte del navegador, enfrentaremos el mismo problema: desbordamiento de pila. Podemos intentar usarlo junto con Trampolining .

Escribiremos un decorador que acepte la función recursiva modificada (siguiente paso) y la ejecute en un bucle, sin aumentar la profundidad de la llamada.

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

Ahora nuestra función recursiva debería devolver una función que será ejecutada inmediatamente por el decorador. De esta manera, condicionalmente haremos una serie de funciones y las ejecutaremos a su vez. Pero dado que devolvemos una nueva función anónima cada vez, este código funcionará un poco más lento.

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

Utilizamos:

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

Este es mi primer artículo. Intenté no volver a contar los conceptos y proporcioné un enlace a las fuentes. El tema no es único y ha existido durante mucho tiempo en sitios en inglés, desafortunadamente no lo encontré en ruso.

Gracias por su atencion Que tengas un buen día :)

Actualización
Rendimiento:

# 1 recursividad




# 2 iteración




# 3 Recurrencia de cola y trampolín




# 4 Recurrencia de cola y trampolín (un gran número)




Según los resultados, vemos que nuestro decorador, aunque nos permite evitar el error de desbordamiento de la pila, funciona más lentamente que la versión recursiva e iterativa. Por lo tanto, este método debe usarse solo si no puede reemplazar la recursividad con la iteración, o si tiene miedo del desbordamiento de la pila al ejecutar su función recursiva.