אופטימיזציית זנב הרקורסיה ב JavaScript ב 2024

04/06/2024

לפני 6 שנים כתבתי על אופטימיזציית זנב הרקורסיה בדפדפנים:

https://www.tocode.co.il/blog/2018-09-javascript-tco

מאז הרבה קרה בדפדפן אבל דווקא הפיצ'ר הזה נשאר מאחור. ספארי, כרום וגם פיירפוקס לא מצליחים לחשב רקורסיבית מספרים גדולים.

אבל נקודת אור אחת כן הצטרפה בעולם של JavaScript בצד שרת מהכיוון של bun (נוד ודינו, כמו הדפדפנים עדיין לא תומכים באופטימיזציה זו).

הנה התוכנית:

function factors_of(number, i=2) {
    if (number < i) {
          return [];
        }

    if (number % i === 0) {
          return [i, ...factors_of(number / i, i)];
        }

    return factors_of(number, i+1);
}

console.log(factors_of(909090909090909090909090));

והרצה בצד שרת ב node:

node a.js
/Users/ynonp/tmp/a.js:1
function factors_of(number, i=2) {
                   ^

RangeError: Maximum call stack size exceeded
    at factors_of (/Users/ynonp/tmp/a.js:1:20)
    at factors_of (/Users/ynonp/tmp/a.js:10:12)
    at factors_of (/Users/ynonp/tmp/a.js:10:12)
    at factors_of (/Users/ynonp/tmp/a.js:10:12)
    at factors_of (/Users/ynonp/tmp/a.js:10:12)
    at factors_of (/Users/ynonp/tmp/a.js:10:12)
    at factors_of (/Users/ynonp/tmp/a.js:10:12)
    at factors_of (/Users/ynonp/tmp/a.js:10:12)
    at factors_of (/Users/ynonp/tmp/a.js:10:12)
    at factors_of (/Users/ynonp/tmp/a.js:10:12)

Node.js v21.7.1

ב Deno:

deno run a.js
error: Uncaught (in promise) RangeError: Maximum call stack size exceeded
function factors_of(number, i=2) {
                   ^
    at factors_of (file:///Users/ynonp/tmp/a.js:1:20)
    at factors_of (file:///Users/ynonp/tmp/a.js:10:12)
    at factors_of (file:///Users/ynonp/tmp/a.js:10:12)
    at factors_of (file:///Users/ynonp/tmp/a.js:10:12)
    at factors_of (file:///Users/ynonp/tmp/a.js:10:12)
    at factors_of (file:///Users/ynonp/tmp/a.js:10:12)
    at factors_of (file:///Users/ynonp/tmp/a.js:10:12)
    at factors_of (file:///Users/ynonp/tmp/a.js:10:12)
    at factors_of (file:///Users/ynonp/tmp/a.js:10:12)
    at factors_of (file:///Users/ynonp/tmp/a.js:10:12)

ורק bun מפתיע לטובה:

$ bun a.js
[
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  71, 101, 251, 401, 9384251
]