O rekurencji i trampolinach

Czy wiesz, że rekurencję można zoptymalizować za pomocą koncepcji, która działa podobnie do sposobu, w jaki skaczemy na trampolinie.

Pozwólcie, że wyjaśnię, w rekurencji funkcja wywołuje samą siebie bez kończenia własnego wykonywania. Ponieważ wykonywanie nie może zostać zakończone, dopóki nie powróci następne wywołanie funkcji (lub nie zakończy wykonywania) i dzieje się to w przypadku dalszych wywołań funkcji. Tworzy to stos niedokończonych wywołań funkcji, a ze względu na ograniczenia pamięci na stosie może być dozwolony tylko określony limit wywołań funkcji. Ale sytuacje z dużą liczbą wywołań rekursyjnych w javascript nie prowadzą do przepełnienia stosu, javascript zapobiega osiągnięciu tego limitu, zgłaszając błąd zakresu.

Rozważ ten przykład,

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

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

Jeśli uruchomisz powyższy kod, wkrótce trafi on do bloku catch. Na MacBooku Air 2k19 osiągnął maksimum około 10 tys. Oznacza to, że nastąpiło przepełnienie stosu.

Cóż, w powyższym przykładzie funkcja inkrementacja wywołuje samą siebie w instrukcji return, co dodaje do stosu jeszcze jedno wywołanie funkcji inkrementacji i to wywołanie ponownie doda do stos jeszcze jednego wywołania funkcji w celu zwiększenia i trwa to aż do osiągnięcia warunku podstawowego, kiedy wartośćpoczątkowastanie się większa niż 1000000, ale to nigdy dzieje się.

Ale tutaj, jeśli zauważysz, że wywołanie rekurencji jest wywołaniem ogonowym. Wywołanie ogona ma miejsce wtedy, gdy wywołanie rekurencji następuje tylko na końcu funkcji w instrukcji return.

Dlaczego musimy się martwić o ogon i jakie ma to znaczenie?

Technika trampoliny, której się wkrótce nauczymy, działa tylko wtedy, gdy mamy rekurencję zdefiniowaną jako wezwanie ogona. Stanie się to bardziej jasne, gdy spojrzymy na trampolinę, wskoczmy na nią.

Tramploina rekurencji” podaje Kyle Simpson. Trampolina to nic innego jak opakowanie naszej funkcji rekurencyjnej. W rekurencji wywołujemy funkcję z poziomu funkcji. W rekurencji trampolinowanej wywołujemy funkcję, która z kolei zwraca funkcję (nie wywołanie funkcji, a tym samym zakończenie bieżącego wykonywania funkcji), a ta zwrócona funkcja ponownie wywołuje naszą funkcję rekurencyjną.

Wiem, że to trochę zagmatwane, ale przeczytaj jeszcze raz, jestem pewien, że zrozumiesz. Tak wygląda opakowanie na trampolinę,

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

Powyższa funkcja trampoliny przyjmuje funkcję jako argument i zwraca funkcję o nazwie enclose, możesz ją nazwać jak chcesz.

Aby skorzystać z powyższego opakowania, musimy nieco zmodyfikować naszą funkcję rekurencyjną.

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

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

Czy zauważyłeś różnicę? Zmodyfikowaliśmy nasze wywołanie końcowe, zwracając zamiast tego funkcję anonimową. Zatem nie jest to już wywołanie funkcji, ale zwraca funkcję wywołującą naszą funkcję rekurencyjną, która w tym przypadku jest inkrementacją.

Teraz, jeśli przekażemy powyższą funkcję do naszego opakowania trampoliny, nasz kod będzie wyglądał następująco.

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

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

console.log(trampolinedIncrement(1));

Po uruchomieniu powyższego kodu nie wystąpi błąd zakresu, a jako wynik otrzymasz 1000000001. Powyższy kod zajął około 20 sekund na Macbooku Air.

Ale co się właśnie stało?

Nasz kod właśnie wylądował na trampolinie, LOL! Oto cały 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));

Kiedy trampolinowaliśmy funkcję inkrementacji, otrzymaliśmy definicję funkcji enclose w trampolinedInkrementacjigdzie fjest funkcją przyrostu. A więc teraz, kiedy wywołamy trampolinedInkrement

z początkowymi argumentami, wywołuje funkcję f, a wynikiem tego wykonania jest anonimowa funkcja przechowywana w wyniku. Następnie wywołujemy funkcję result, aż zwróci ona funkcję typeof i na koniec zwróci wynik.