Rekursiya va Trampolin haqida

Bilasizmi, rekursiyani trambolinda qanday sakrashimizga o'xshash kontseptsiya yordamida optimallashtirish mumkin.

Batafsilroq aytib beraman, rekursiyada funktsiya o'z bajarilishini tugatmasdan o'zini chaqiradi. Keyingi funktsiya chaqiruvi qaytmaguncha (yoki bajarilish tugallanmaguncha) bajarishni tugatib bo'lmaydi va bu keyingi funksiya chaqiruvlari uchun davom etadi. Bu tugallanmagan funksiya qo'ng'iroqlari to'plamini yaratadi va xotira cheklovlari tufayli stekda faqat ma'lum bir funktsiya chaqiruvi chegarasi bo'lishi mumkin. Ammo JavaScript-da ko'p sonli rekursion qo'ng'iroqlar bo'lgan holatlar stekning to'lib ketishiga olib kelmaydi, JavaScript diapazon xatosi orqali ushbu chegaraga erishishni oldini oladi.

Ushbu misolni ko'rib chiqing,

function increment(test) {
  try {
    if (test > 1000000) return test;

    return increment(++test);
  } catch {
    console.log("test===>", test);
  }
}

Agar siz yuqoridagi kodni ishga tushirsangiz, u tez orada catch blokiga kiradi. Macbook air 2k19-da u 10K atrofida maksimal darajaga etdi. Ya'ni, stek to'lib ketgan.

Yuqoridagi misolda o'sishfunktsiyasi qaytish bayonotida o'zini chaqiradi, bu stekga ko'paytirishga yana bitta funktsiya chaqiruvini qo'shadi va bu qo'ng'iroq yana qo'shiladi. incrementga yana bitta funktsiya chaqiruvini to'plang va bu initialValue1000000 dan kattaroq bo'lganda, u asosiy holatga kelguncha davom etadi, lekin bu hech qachon amalga oshirilmaydi. sodir bo'ladi.

Ammo bu erda siz rekursiya qo'ng'irog'i quyruq chaqiruvi ekanligini sezsangiz. Quyruq chaqiruvi - bu rekursiya chaqiruvi faqat qaytish bayonotida funksiya oxirida sodir bo'lganda.

Nima uchun biz quyruq chaqiruvi bilan o'zimizni tashvishlantirishimiz kerak va bu qanday ahamiyatga ega?

Biz o'rganmoqchi bo'lgan trambolin texnikasi faqat bizda quyruq chaqiruvi sifatida belgilangan rekursiya mavjud bo'lganda ishlaydi. Bu trambolinga qaraganimizdan keyin aniqroq bo'ladi, keling, unga o'taylik.

Rekursiya tramploini' Kayl Simpson tomonidan berilgan. Trambolin bizning rekursiv funktsiyamiz atrofidagi o'rashdan boshqa narsa emas. Rekursiyada biz funksiyani funksiya ichidan chaqiramiz. Trambolinli rekursiyada biz oʻz navbatida funktsiyani qaytaradigan funktsiyani chaqiramiz (funktsiya chaqiruvi emas va shuning uchun joriy funktsiyani bajarishni yakunlaydi) va bu qaytarilgan funksiya yana bizning rekursiv funksiyamizni chaqiradi.

Bu biroz chalkash, bilaman, lekin yana bir bor o'qing, ishonchim komilki, siz buni olasiz. Trambolin o'rami qanday ko'rinishga ega:

function trampoline(f) {
  return function enclose(...args) {
    let result = f(...args);
    while (typeof result === "function") {
      result = result();
    }
    return result;
  };
}

Yuqoridagi trambolin funksiyasi argument sifatida funktsiyani oladi va enclose deb nomlangan funktsiyani qaytaradi, siz uni xohlaganingizcha chaqirishingiz mumkin.

Yuqoridagi o'ramdan foydalanish uchun biz rekursiv funksiyamizni biroz o'zgartirishimiz kerak.

function increment(test) {
  try {
    if (test > 1000000000) return test;

    return () => increment(++test);
  } catch {
    console.log("test===>", test);
  }
}

Farqni sezdingizmi, uning o'rniga anonim funktsiyani qaytarish orqali quyruq chaqiruvimizni o'zgartirdik. Shunday qilib, u endi funktsiya chaqiruvi emas, balki bizning rekursiv funktsiyamizni chaqiradigan funktsiyani qaytaradi, bu holda o'sish.

Endi, agar biz yuqoridagi funktsiyani trambolin o'ramiga o'tkazsak, bizning kodimiz shunday ko'rinadi.

const trampolinedIncrement = trampoline(function increment(test) {
  try {
    if (test > 1000000000) return test;

    return () => increment(++test);
  } catch {
    console.log("test===>", test);
  }
});

console.log(trampolinedIncrement(1));

Yuqoridagi kodni ishga tushirganingizda, diapazonda xato bo'lmaydi va siz 1000000001ni olasiz. Yuqoridagi kod Macbook Air da taxminan20 soniyani oldi.

Lekin nima bo'ldi?

Bizning kodimiz hozirgina trambolinga tushdi, LOL! Mana butun kod,

function trampoline(f) {
  return function enclose(...args) {
    let result = f(...args);
    while (typeof result === "function") {
      result = result();
    }
    return result;
  };
}

const trampolinedIncrement = trampoline(function increment(test) {
  try {
    if (test > 1000000000) return test;

    return () => increment(++test);
  } catch {
    console.log("test===>", test);
  }
});

console.log(trampolinedIncrement(1));

Bizincrementfunktsiyasini trampolin qilganimizda, biztrampolinedIncrement daenclosefunktsiyasining ta'rifini oldik. >fffo‘sishfunksiyasi bo‘lgan holda. Shunday qilib, endi biz chaqirganimizdatrampolinedIncrement