TCO (ang. Tail Call Optimization), czyli optymalizacja wywołań ogonowych, to technika stosowana w wywołaniach rekurencyjnych w celu optymalizacji zużycia pamięci i zmniejszenia rozmiaru stosu wywołań. 

Żeby jednak zrozumieć jej działanie, musimy wiedzieć, czym jest rekurencja, do czego się przydaje i kiedy powinniśmy z niej skorzystać. Jeżeli ta wiedza nie jest Ci obca, to pierwszą część artykułu możesz pominąć, gdyż skupiam się w niej na wyjaśnieniu podstaw działania rekurencji.

Rekurencja to technika, w której funkcja wywołuje samą siebie. Na pierwszy rzut oka może to przypominać nieskończoną pętlę, dlatego kluczowym elementem każdej funkcji rekurencyjnej jest zdefiniowanie przypadku bazowego (ang. base case), czyli warunku, po którego spełnieniu funkcja nie jest wywoływana kolejny raz. Zazwyczaj wewnątrz takiego warunku umieszcza się instrukcję odpowiedzialną za zwrócenie jakiejś wartości.

Zatem każda poprawnie skonstruowana funkcja rekurencyjna musi zawierać dwa elementy:

• Wywołanie rekurencyjne samej siebie.

• Przypadek bazowy, czyli warunek kończący rekurencję.

Możesz teraz zapytać: po co używać rekurencji, skoro mamy do dyspozycji pętle? I nie będzie to pytanie bezpodstawne. 

Okazuje się, że każdy problem, który można rozwiązać za pomocą rekurencji, można również rozwiązać iteracyjnie, używając pętli for czy while. Co więcej, niewłaściwe użycie rekurencji może prowadzić do skomplikowania kodu i, co ważniejsze, do znacznie większego zużycia pamięci - każde kolejne wywołanie funkcji musi zostać dodane do stosu wywołań (ang. call stack), a to z kolei może skutkować jego przepełnieniem lub po prostu obniżoną wydajnością aplikacji.

Istnieją jednak sytuacje, w których rekurencja jest preferowanym rozwiązaniem, głównie ze względu na czytelność i prostotę kodu. Rekurencja świetnie sprawdza się w algorytmach operujących na strukturach danych o charakterze drzewiastym, takich jak listy połączone, drzewa binarne czy struktura DOM w przeglądarce. Oczywiście zastosowań jest znacznie więcej, a te które wymieniłem, to tylko wierzchołek góry lodowej.

Zazwyczaj rekurencję przedstawia się na podstawie przykładu obliczającego silnię, ale moim zdaniem jest on wyjątkowo niepraktyczny i nieżyciowy, dlatego zdecydowałem się przedstawić ją na przykładzie drzewa:

To, że użyliśmy rekurencji, nie oznacza, że nie możemy zastosować pętli do wykonania tego samego zadania. Jednak w tym przypadku kod jest zdecydowanie mniej czytelny.

Rekurencja jest zatem sposobem na poprawę czytelności i przejrzystości naszego kodu. Odradzam jednak wybieranie jej jako domyślnego sposobu implementacji danego algorytmu bez wcześniejszego sprawdzenia rozwiązania iteracyjnego (z wykorzystaniem pętli). Wykorzystanie rekurencji nie jest magicznym sposobem na poprawę czytelności kodu i wielu przypadku może okazać się, że pętla jest nie tylko wydajniejsza ale także łatwiejsza do odczytania i zrozumienia.

Jeżeli nie masz jeszcze doświadczenia w stosowaniu rekurencji i nie do końca wiesz, gdzie i kiedy ją zastosować, to poniższa lista zawiera kilka ogólnych przypadków, w których zazwyczaj wybór rekurencyjnego rozwiązania okaże się czytelniejszy:

• Dane hierarchiczne: do przechodzenia przez zagnieżdżone struktury, takie jak drzewa czy obiekty JSON, gdzie rekurencja w naturalny sposób odzwierciedla formę danych.

• Generowanie permutacji i kombinacji: gdy tworzymy wszystkie możliwe układy lub podzbiory kolekcji, rozwiązanie rekurencyjne jest często znacznie prostsze niż iteracyjne.

• Algorytmy typu "Dziel i zwyciężaj": w przypadku algorytmów takich jak sortowanie przez scalanie (Merge Sort), które działają poprzez dzielenie problemu na mniejsze, identyczne podproblemy.

• Backtracking (algorytmy z nawracaniem): w scenariuszach, które wymagają badania różnych ścieżek i powrotu, jeśli któraś z nich nie prowadzi do rozwiązania, jak np. przy rozwiązywaniu labiryntu.

Warto pamiętać, że w programowaniu nie ma nic za darmo. Rekurencja nierzadko poprawia czytelność (stosuje w naturalny sposób podejście “divide and conquer”) ale zawsze jest bardziej kosztownym (pod względem zużycia zasobów) rozwiązaniem niż iteracja, dlatego stosuj ją z rozwagą. Jeżeli wydajność kodu jest priorytetem, to może się okazać, że pomimo większej czytelności algorytmu rekurencyjnego, lepiej jest zastosować wersję iteracyjną. 

Wraz ze wzrostem doświadczenia zaczynamy także intuicyjnie zauważać, kiedy możemy zastosować rekurencję, a kiedy zdecydowanie lepiej sprawdzi się iteracja. Nadal jednak warto kierować się zasadą stosowania iteracyjnego podejścia, jako punktu wyjścia, a po rekurencję sięgnąć dopiero wtedy, gdy uznamy, że nasz kod może zyskać na czytelności, dzięki jej zastosowaniu.

Żeby w pełni zrozumieć główny temat artykułu, musimy poruszyć jeszcze jedną kwestię, o której wspomniałem w kilku słowach przy okazji opisywania działania samej rekurencji - zużycie zasobów.

Rekurencyjna wersja algorytmu zawsze zużywa więcej zasobów sprzętowych (takich jak RAM) niż jej iteracyjny odpowiednik. Dzieje się tak dlatego, że każde kolejne wywołanie funkcji, musi zostać dodane do stosu wywołań i tym samym przechowane w pamięci. W przypadku iteracyjnego podejścia, wywołanie funkcji jest tylko jedno i to w nim zawarte są wszystkie obliczenia. 

Jeżeli podstawowe struktury danych nie są Ci obce, to z pewnością wiesz, że stos zachowuje konkretną kolejność dodawania i usuwania elementów: 

• dodawać elementy możemy jedynie na “górę” (na wierzch stosu)

• usunąć można jedynie element znajdujący się na samej górze, a więc ten, który został dodany jako ostatni

Zasady, którymi kieruje się stos doczekały się swojej własnej nazwy: LIFO (ang. Last In First Out) - ostatni dodany element jest jednocześnie pierwszym w kolejności do usunięcia.

Działanie stosu jest kluczowe w kontekście TCO, ponieważ jego pojemność nie jest nieograniczona i zależy od konkretnego silnika JavaScript (dla V8 jest to około 12500 elementów). Ponieważ każde kolejne wywołanie funkcji dokłada na “wierzch” stosu kolejny element, który musi na nim pozostać aż do momentu zakończenia wszystkich zagnieżdżonych wywołań. Dzieje się tak, ponieważ konieczne jest, by funkcja nadrzędna wykonała jeszcze jakieś operacje po powrocie z wywołania rekurencyjnego. Interpreter musi więc pamiętać adres powrotu, aby dokończyć jej wykonanie.

W przypadku rekurencji, dość łatwo możemy doprowadzić do sytuacji, w której miejsce na stosie się skończy, a my otrzymamy błąd RangeError: Maximum call stack size exceeded. Ten problem widział również zespół odpowiedzialny za specyfikację języka i zdecydował się na wprowadzenie mechanizmu, który mógłby go rozwiązać.

Skoro wiemy już, czym jest i  jak działa rekurencja, a także rozumiemy problem związany ze stosem wywołań, to jesteśmy gotowi na sedno artykułu. Czym jest TCO i dlaczego jest tak ważne?

TCO to stosowana w rekurencji technika, dzięki której kompilator lub interpreter jest w stanie zoptymalizować wywołanie funkcji, jeśli jest ono ostatnią operacją wykonywaną w danej funkcji (tzw. wywołanie ogonowe). W takiej sytuacji środowisko wykonawcze rozumie, że nie ma już żadnych dodatkowych operacji do wykonania w bieżącej funkcji i, zamiast dokładać nowe wywołanie na stos, może ono po prostu zastąpić bieżącą ramkę stosu nową, oszczędzając w ten sposób pamięć. Mechanizm ten można znaleźć nie tylko w JavaScript, ale także w kilku innych językach programowania, na przykład w Haskell, Clojure, C oraz C++.

Kluczowy jest fakt, że wywołanie rekurencyjne musi być ostatnią instrukcją w danej funkcji. Przykład, który wykorzystałem wcześniej, spełnia ten warunek (rekurencyjne wywołanie znajduje się na samym końcu), co oznacza, że nie spowoduje przepełnienia stosu.

Wydawać by się mogło, że TCO rozwiązuje wszelkie problemy związane z rekurencją i nie posiada żadnych wad. Niestety, jak to zwykle bywa, tak i w tym przypadku jest to pewien kompromis.

Cofnijmy się do roku 2015. W tym właśnie roku ogłoszono nową specyfikację języka ECMAScript (ES6) i zawarto w niej także funkcjonalność o nazwie PTC (ang. Proper Tail Call), która jest nierozerwalnie powiązana z głównym tematem artykułu.

PTC pozwala interpreterowi na optymalizowanie rekurencyjnych wywołań, które stosują TCO. W praktyce oznacza to, że kompilator lub interpreter może użyć ponownie ostatniego elementu (ang. stack frame) ze stosu wywołań. Dzięki temu stos zachowuje ten sam rozmiar i nie rośnie wraz z każdym kolejnym wywołaniem funkcji rekurencyjnej. Oznacza to, że PTC to funkcjonalność języka, która jest niezbędna do działania TCO. 

Twórcy silników przeglądarkowych zaczęli implementować nowy standard i już na początku roku 2016, większość głównych przeglądarek wspierało PTC i tym samym TCO. Zaczęły się jednak pojawiać pierwsze głosy krytyki ze strony zespołu odpowiedzialnego za Firefoxa oraz Edge’a. Okazało się, że to, co na papierze wyglądało na rozwiązanie pozbawione wad, w praktyce powoduje wiele problemów.

Głównymi zarzutami kierowanymi w stronę PTC było między innymi pogorszenie DX (ang. developer experience), czyli jakości i komfortu pracy programistów, a także znaczące utrudnienie debugowania. Krytycy skupili się także na kilku innych kwestiach:

• Nieużyteczny ślad stosu (ang. stack trace): właściwość error.stack, stanowiąca podstawę raportowania błędów w języku JavaScript, stałaby się niemal bezużyteczna. W śladach stosu brakowałoby wielu ramek, co niezwykle utrudniłoby zrozumienie sekwencji wywołań, która doprowadziła do błędu. To z kolei znacznie utrudniłoby debugowanie kodu.

• Zepsute narzędzia: niemal cały ekosystem narzędzi produkcyjnych – w tym usługi telemetryczne, platformy do agregacji błędów (takie jak Sentry czy Bugsnag) oraz narzędzia do analizy post-mortem, opierają się na wspomnianej wcześniej właściwości error.stack w celu dostarczania raportów. Niespójne lub niekompletne ślady stosu zepsułyby te narzędzia lub uczyniły je znacznie mniej użytecznymi.

• Dezorientacja deweloperów: programista, który nie jest dogłębnie zaznajomiony z optymalizacją wywołań ogonowych (PTC), mógłby nieświadomie napisać kod zawierający takie wywołanie. Gdyby ten kod zawiódł, "magiczne" zniknięcie ramki stosu byłoby głęboko mylące, prowadząc do straty czasu i frustracji.

Te wątpliwości doprowadziły do rozłamu. Część zespołów odpowiedzialnych za silniki JS w przeglądarkach, zdecydowała się nie implementować specyfikacji ES6 w pełni i nie wspiera PTC. Problem polega na tym, że druga część postanowiła w pełni trzymać się oficjalnej specyfikacji. W efekcie to, czy możemy wykorzystać TCO, czy nie, zależy od tego w jakim środowisku nasz kodu zostanie uruchomiony. 

Tabela poniżej przedstawia, które z silników JavaScript (oraz ich główni odbiorcy) obecnie wspierają TCO:

Obecnie wsparcie trudno uznać za zadowalające. Wykorzystywanie TCO w przeglądarkach jest niezwykle ryzykowne i w niektórych przypadkach może skutkować tym, że nasza aplikacja nie będzie działać poprawnie u niektórych użytkowników. Nieco inaczej wygląda sytuacja w środowisku backendowym - Bun w pełni wspiera TCO i, jeśli wykorzystujemy go do tworzenia kodu serwerowego, to nic nie stoi na przeszkodzie, by korzystać z dobrodziejstw PTC i TCO.

Niestety na pełne wsparcie PTC w przeglądarkach przyjdzie nam jeszcze trochę poczekać. Kiedy w 2021 roku powstał Bun i zdecydował się wykorzystać JavaScriptCore, a nie V8, tak, jak robi to Node, presja na zespoły odpowiedzialne za silniki V8 oraz SpiderMonkey znacznie wzrosła. Stało się tak dlatego, że do tej pory żadne środowisko uruchomieniowe dla serwerowej części JavaScriptu nie wspierało PTC. Po tym, jak Bun ujrzał światło dzienne, niespójności stały się znacznie bardziej zauważalne i odczuwalne, a wielu programistom przypomniały się dni, kiedy każda przeglądarka implementowała rzeczy na swój sposób, co znacznie utrudniało pracę. Środowisko zaczęło domagać się uspójnienia działania TCO pomiędzy przeglądarkami i wywierać wpływ na zespoły odpowiedzialne za V8 oraz SpiderMonkey.

Jeżeli jednak nie chcesz czekać, aż wszystkie przeglądarki zaczną w pełni implementować (o ile kiedyś do tego dojdzie) PTC, to już dzisiaj możesz skorzystać z WASM, który posiada wsparcie dla tej funkcjonalności od 2023 roku. Na natywne wsparcie przyjdzie nam jednak jeszcze poczekać.