‏بازگشت در جاوااسکریپت: چرا Tail Call به دردت نمی‌خوره؟

ری‌کرژن (تابعی که خودش رو صدا می‌زنه) برای مسائلی مثل پیمایش درخت یا الگوهای تقسیم‌و‌غلبه خیلی خوانا و طبیعیه. ولی یه محدودیت فیزیکی داره: هر فراخوانی یه فریم جدید روی call stack می‌ذاره، و با ورودی‌های بزرگ به RangeError: Maximum call stack size exceeded می‌رسیم. این مشکل ربطی به درستی منطق کد نداره؛ صرفاً محدودیت سخت‌افزاری رانتایمه.

راه‌حل کلاسیک اینه که تابع رو به شکل tail-recursive بنویسیم — یعنی فراخوانی بازگشتی آخرین کاری باشه که تابع انجام می‌ده، بدون هیچ محاسبه معلقی بعدش. این به رانتایم اجازه می‌ده همون فریم رو دوباره استفاده کنه به جای اینکه فریم جدید بسازه. مفهوم این بهینه‌سازی به اسم TCO (Tail Call Optimization) شناخته می‌شه.

مشکل اینجاست که ECMAScript 2015 هرچند TCO رو در حالت strict mode استاندارد کرد، ولی اکثر موتورهای جاوااسکریپت هرگز اون رو به‌درستی پیاده‌سازی نکردن. V8 (موتور Chrome، Node.js و Deno) اصلاً TCO نداره. SpiderMonkey فایرفاکس هم همینطور. JavaScriptCore سافاری یه بار پیاده‌سازی کرد و بعد عقب‌نشینی کرد. نتیجه: نمی‌شه در پروداکشن به TCO تکیه کرد.

function sumTR(n, acc = 0) {
  if (n === 0) return acc;
  return sumTR(n - 1, acc + n);
}

sumTR(100000); // ممکنه هنوز RangeError بده!

این تابع کاملاً tail-recursive نوشته شده، ولی در V8 همچنان stack overflow می‌ده چون موتور فریم جدید می‌سازه.

امن‌ترین راه‌حل برای پروداکشن اینه که کد رو iterative بنویسیم — یعنی با حلقه به جای فراخوانی بازگشتی. اگه هم خواستیم ساختار ذهنی بازگشتی رو حفظ کنیم، می‌تونیم از الگوی trampoline استفاده کنیم؛ این الگو یه حلقه‌ست که تا وقتی تابع یه تابع دیگه برمی‌گردونه اون رو اجرا می‌کنه و به این شکل stack رو دور می‌زنه.

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

function sumTrampoline(n, acc = 0) {
  if (n === 0) return acc;
  return () => sumTrampoline(n - 1, acc + n);
}

trampoline(() => sumTrampoline(100000)); // بدون stack overflow

trampoline یه سربار اضافه از ساخت توابع داره، پس برای مسیرهای حساس به پرفورمنس بهتره مستقیم iterative بنویسیم. ولی وقتی خوانایی کد مهم‌تره، گزینه خوبیه.

نکته مهم دیگه: مثال فیبوناچی معمولی (fib(n-1) + fib(n-2)) علاوه بر مشکل stack، یه مشکل جداگانه هم داره — پیچیدگی زمانی نمایی O(2ⁿ). این دو مشکل از بیرون شبیه هم به نظر می‌رسن (مرورگر هنگ می‌کنه)، ولی علت و راه‌حلشون کاملاً متفاوته.

نکات کلیدی:

• هر فراخوانی بازگشتی یه فریم روی stack می‌ذاره و با ورودی بزرگ crash می‌کنه
• TCO در اکثر رانتایم‌های جاوااسکریپت (V8، SpiderMonkey) پیاده‌سازی نشده
• tail-recursive بودن کد، امنیت stack رو تضمین نمی‌کنه
• برای ورودی‌های نامعلوم یا بزرگ، iterative بنویس یا از trampoline استفاده کن
• ری‌کرژن رو برای عمق‌های کوچک و کنترل‌شده نگه دار