Jak nejlépe spočítat faktoriál v JavaScriptu?

Nedávná diskuse na Facebooku mě přiměla, abych toto téma prozkoumal do větších detailů, než mi umožňovaly tamní komentáře. Tato otázka totiž kupodivu nemá jednoduchou odpověď. Když o ní začnete více přemýšlet, ponoříte se do některých zajímavějších oblastí JavaScriptu, které možná ne všichni znají.

Celý článek

Vezměme to od začátku. Všichni známe matematickou definici faktoriálu: „faktoriál nezáporného celého čísla n je roven součinu všech kladných celých čísel menších nebo rovných n“. Navíc aby se některé výpočty zjednodušily (a naše implementace zkomplikovala), faktoriál nuly je definován jako 1.

Pokud jste někdy studovali programování, první ukázka, kterou jste viděli v rámci výuky rekurze, byl nejspíš právě výpočet faktoriálu. Učebnicová implementace by mohla vypadat takto:

function factorialFromDefinition(n) {
    if (n == 0) return 1;
    return n * factorialFromDefinition(n - 1);
}

for (let i = 0; i < 8; i++) {
    console.log("factorial(" + i + ") = " + factorialFromDefinition(i));
}

Když tuto ukázku spustíme, dostaneme očekávaný výstup.

factorial(0) = 1
factorial(1) = 1
factorial(2) = 2
factorial(3) = 6
factorial(4) = 24
factorial(5) = 120
factorial(6) = 720
factorial(7) = 5040

Pokud použijeme tzv. šipkovou notaci funkcí a navíc přepíšeme příkaz if na podmínkový ternární operátor, změní se naše funkce na následující jednořádkový zápis.

const factorialFromDefinitionArrow =
    n => n == 0 ? 1 : n * factorialFromDefinitionArrow(n - 1);

Máme krátké a zároveň čitelné řešení; je to tedy vše? Naopak, spíše začínáme.

Potíže s rekurzí

Naše řešení obsahuje dva problémy, které se nemusejí projevit u tak triviálních úloh, jako je počítání faktoriálů, ale mohou nás snadno nemile překvapit při složitějším použití rekurze:

• Volání funkcí je obecně vzato pomalé. Tady mi budete muset věřit, protože řádná demonstrace by sama o sobě byla poměrně komplikovaná.
• Existuje určité maximální množství zanoření volání jednotlivých funkcí, které vám programovací jazyk (resp. běhové prostředí, které váš program spouští) dovolí. Pokud toto množství překročíte, narazíte na tak nechvalně známou chybu, že podle ní byl pojmenován mezi programátory velmi populární web.

Bohužel ani tento druhý problém nejde v JavaScriptu předvést na faktoriálech, protože ty rostou tak rychle, že brzy dosáhneme nekonečna:

factorial(170) = 7.257415615307994e+306
factorial(171) = Infinity

Pokud ovšem naši funkci trochu pozměníme a necháme ji počítat trojúhelníkové číslo, snadno vyvoláme chybu typu „stack overflow“.

const triangularNumber =
    n => n == 1 ? 1 : n + triangularNumber(n - 1);

Zatímco volání triangularNumber(10000) vrátí 50005000, volání triangularNumber(100000) způsobí chybu RangeError: Maximum call stack size exceeded.

Iterativní řešení

Vraťme se k faktoriálům. Přestože naše řešení přesně následuje matematickou definici, evidentně má své slabiny (přinejmenším v teoretické rovině). Jak je můžeme vylepšit?

Jestliže problém spočívá v rekurzi, můžeme se jí zbavit. Naštěstí lze faktoriály snadno počítat pomocí cyklu.

const factorialIterative = function(n) {
    if (n == 0) return 1;
    let result = 1;
    for (let i = 2; i <= n; i++) result *= i;
    return result;
}

Jediným nedostatkem tohoto řešení je, že nevypadá úplně funkcionálně, a my přece všichni zbožňujeme funkcionální programování, zvláště v JavaScriptu, že?

Funkcionální řešení bez rekurze

Zkusme to tedy funkcionálně, ale bez rekurze. Můžeme totiž vygenerovat pole čísel od 0 do n a následně použít funkci reduce pro provedení patřičných násobení.

Existuje několik způsobů, jak takové pole vytvořit, ale pokud chcete předvést své pokročilé znalosti JavaScriptu, použijete pochopitelně funkci Array.from: Array.from({length: n + 1}, (_, i) => i). Takto ji použijeme později, nicméně nyní si to trochu usnadníme a použijeme pole od 1 do n. Následným použitím funkce reduce získáme novou jednořádkovou verzi výpočtu faktoriálu.

const factorialArrayReduce = n => Array.from({length: n}, (_, i) => i + 1)
    .reduce((accumulator, currentValue) => accumulator * currentValue);

Nedostatkem je to, že tato varianta neumí spočítat faktoriál nuly, ale když ji trochu rozšíříme, poradíme si i s tímto:

const factorialArrayReduceBetter =
    n => Array.from({length: n + 1}, (_, i) => i)
        .reduce((acc, curr) => acc * (curr == 0 ? 1 : curr), 1);

Použití generátoru

Pokud toto řešení porovnáte s předchozí funkcí factorialIterative, měli byste se zamračit. Za prvé většina lidí uzná, že je to sice hezké, jednořádkové a funkcionální, ale zároveň hůře čitelné než iterativní varianta.

Za druhé je tu ono volání Array.from. Pokud jste to při předchozím čtení přehlédli, toto volání skutečně vytvoří pole všech těch čísel přesně tak, jak jsme požádali. V případě jiné úlohy by takovéto řešení mohlo vést ke skutečně velmi velkému poli (které předně bude zabírat spoustu paměti a za druhé bude i trvat ho vytvořit). Když se nad tím zamyslíme, my je ale vlastně celé vůbec nepotřebujeme – zpracováváme jeho prvky jeden po druhém. Pokud jste někdy slyšeli o generátorech, víte, kam mířím. Pokud ne, uslyšíte o nich nyní.

Generátory jsou objekty schopné postupně vracet (tedy generovat) sekvence hodnot. Pokud jste příznivci jednořádkových zápisů, budete bohužel zklamáni, jelikož pro generátory neexistuje v JavaScriptu nějaký zkrácený zápis obdobný šipkové notaci pro funkce.

Horší je ale to, že přestože přes hodnoty poskytované generátorem můžeme snadno iterovat, pro generátory aktuálně bohužel neexistují obdoby takových metod, jako je třeba reduce; ty jsou definovány pouze pro pole. To znamená, že pro přepsání předchozího řešení si musíme sami implementovat i funkci reduce.

Opět máme dvě varianty řešení (ta jednodušší nezvládne spočíst faktoriál nuly).

function* sequenceGenerator(start, count) {
    let current = start;
    for (let i = 0; i < count; i++) yield current++;
}

const reduce = (iterable, reducer, initialValue) => {
    let accumulator = initialValue;
    for (let current of iterable) accumulator = reducer(accumulator, current);
    return accumulator;
}

const factorialGeneratorReduce =
    n => reduce(sequenceGenerator(1, n), (acc, curr) => acc * curr, 1);

const factorialGeneratorReduceBetter =
    n => reduce(
        sequenceGenerator(0, n + 1),
        (acc, curr) => acc * (curr == 0 ? 1 : curr),
        1
    );

Zapamatování předchozích výsledků

Ještě bychom si měli položit jednu otázku. Co se stane, když v nějakém místě programu zavoláme factorialIterative(100) a později zavoláme factorialIterative(101)? V tu chvíli budeme počítat faktoriál čísla 101 úplně od začátku, přestože kdybychom si předtím zapamatovali faktoriál té stovky, postačilo by nám vynásobit jej číslem 101. Pokud by náš program neustále počítal nějaké faktoriály, mohlo by to vést k výkonnostním potížím.

Tím se dostáváme (konečně) k poslednímu řešení. V něm zavedeme cache pro všechny faktoriály, které jsme v minulosti spočetli. Pokud jsme požádáni o faktoriál nějakého čísla, nejdříve zkontrolujeme, jestli jsme tento faktoriál už v minulosti nepočítali. Pokud ano, okamžitě vrátíme známý výsledek. Pokud ne, spočítáme a uložíme si faktoriály všech čísel až do vstupního parametru a poté vrátíme nově spočtenou hodnotu.

const factorialCached = function() {
    const cache = [1];
    return function(n) {
        if (n >= cache.length) {
            for (let i = cache.length; i <= n; i++) {
                cache[i] = cache[i - 1] * i;
            }
        }
        return cache[n];
    }
}();

Závěr

Jak jsem zmiňoval hned na začátku: otázka „nejlepší“ implementace faktoriálu není tak jednoduchá, jak by se mohla zdát. I implementace jedné z nejjednodušších matematických funkcí má řadu různých řešení a každé z nich má své výhody a nevýhody.