Despre recursire și trambulina

Știați că recursiunea poate fi optimizată folosind un concept care funcționează similar modului în care sărim pe o trambulină.

Permiteți-mi să detaliez, în recursivitate o funcție se autoinvocă fără a-și termina propria execuție. Deoarece execuția nu poate fi terminată până când următorul apel de funcție revine (sau execuția terminată) și aceasta continuă pentru apeluri de funcție ulterioare. Acest lucru creează o stivă de apeluri de funcții neterminate și, din cauza constrângerilor de memorie, poate exista doar o anumită limită de apeluri de funcție permise într-o stivă. Dar situațiile cu un număr mare de apeluri recursive în javascript nu duc la depășirea stivei, javascript împiedică atingerea acelei limite prin aruncarea unei erori de interval.

Luați în considerare acest exemplu,

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

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

Dacă rulați codul de mai sus, acesta va intra în blocul catch destul de curând. Pe un macbook air 2k19, a atins maxim aproximativ 10K. Asta înseamnă că a existat o stivă depășită.

Ei bine, în exemplul de mai sus, funcția incrementse apelează în instrucțiunea return, aceasta adaugă la stivă încă un apel de funcție la incrementși acest apel se va adăuga din nou la mai stivuiți un apel de funcție la incrementareși acest lucru continuă până când ajunge la condiția de bază, când initialValuedevine mai mare de 1000000, dar asta niciodată se întâmplă.

Dar aici, dacă observați că apelul recursiv este un apel de coadă. Un apel de coadă este atunci când un apel recursiv are loc doar la sfârșitul funcției într-o instrucțiune return.

De ce trebuie să ne preocupăm de apelul de coadă și cum contează?

Tehnica trambulinei pe care suntem pe cale să o învățăm funcționează doar atunci când avem recursiunea definită ca un apel de coadă. Acest lucru va deveni mai clar odată ce ne uităm la trambulină, să urcăm la ea.

Tramploine of recursion’ este dat de Kyle Simpson. O trambulină nu este altceva decât un înveliș în jurul funcției noastre recursive. În recursivitate, numim o funcție din interiorul unei funcții. Într-o recursivitate trambulină, apelăm o funcție care, la rândul ei, returnează o funcție (nu un apel de funcție și, prin urmare, completează execuția curentă a funcției), iar această funcție returnată apelează din nou funcția noastră recursivă.

Este puțin confuz, știu, dar citiți-l din nou, sunt sigur că îl veți înțelege. Iată cum arată învelișul trambulinei,

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

Funcția de trambulină de mai sus, ia o funcție ca argument și returnează o funcție numită închide, o puteți numi orice doriți.

Pentru a folosi wrapper-ul de mai sus, trebuie să ne modificăm puțin funcția recursivă.

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

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

Ați observat diferența, ne-am modificat apelul de coadă, returnând în schimb o funcție anonimă. Astfel că nu mai este un apel de funcție, dar returnează o funcție care apelează funcția noastră recursivă care este incrementîn acest caz.

Acum, dacă trecem funcția de mai sus în ambalajul nostru de trambulină, codul nostru va arăta astfel.

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

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

console.log(trampolinedIncrement(1));

Când rulați codul de mai sus, nu va exista nicio eroare de interval și veți obține 1000000001ca rezultat. Codul de mai sus a durat aproximativ 20 de secunde pe un Macbook Air.

Dar ce tocmai sa întâmplat?

Codul nostru tocmai a intrat pe o trambulina, LOL! Aici este întregul cod,

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));

Când am trambulinat funcția increment, am primit definiția funcției encloseîn trampolinedIncrementcu ffiind funcția increment. Așa că acum, când numim trambulinedIncrement

funcția cu argumente inițiale, apelează fși rezultatul execuției respective este o funcție anonimă care este stocată în rezultat em>. Apoi continuăm să apelăm funcția rezultat până când returnează o funcție typeofși la sfârșit va returna rezultatul.