15 komentářů k článku Jak nejlépe spočítat faktoriál v JavaScriptu?:

  1. Ondřej Žára

    Stack overflow a TCO
    Otázka přetečení zásobníku volání je ještě krapet komplikovanější, protože ES6 předepisuje TCO, tedy Tail Call Optimization — podporu pro to, aby jisté formy rekurze nezpůsobovaly narůstání velikosti zásobníku.

    Tedy ukázka s triangularNumber například v Chrome 71 způsobí skutečně výjimku, zatímco ve Firefoxu 64 vrátí 5000050000. To samo o sobě není důkazem TCO, ale konstatováním, že zmiňované chování se může napříč implementacemi dost lišit.

    1. Ondra KučeraAutor příspěvku

      Re: Stack overflow a TCO
      Přemýšlel jsem, jestli zabíhat do „ocasní rekurze“, ale zdálo se mi to už i tak dost dlouhé. :-) Nicméně nevěděl jsem, že to dokonce nařizuje specifikace, takže to jsem se rád přiučil. Jinak ukázky jsem si pouštěl v Node.js. A popravdě řečeno když jsme u toho, chovalo se to tam docela divně: nejednou se mi stalo, že se stejně velkým argumentem to občas doběhlo a jindy upadlo. Původně jsem chtěl najít vysloveně tu hranici, na kterém čísle to ještě projde a na kterém už to upadne, ale ukázalo se, že ta hranice se v čase mění …

      1. Ondřej Žára

        Re: Stack overflow a TCO
        Celá ta věc pěkně smrdí. ES6 sice o TCO mluví, ale v praxi se k podpoře má málokdo — v Node.js jednu dobu byla pod nějakým experimentálním flagem, ale tato hotová naprogramovaná věc byla následně zcela odstraněna. Fór je v tom, že TCO je geniální konstrukt pro funkcionální programování (také strojovou dokazatelnost a podobně), ale mizí tím možnost inspekce zásobníku. Takže chyby pak nemají tracebacky (nebo je mají chybně) a podobně. Proto je nejisté, zda-li se TCO v JS vůbec uchytí — specifikace nespecifikace.

        Co se týče nepředvídatelného chování, osobně bych to tipnul tak, že hloubka zásobníku není omezena číselnou konstantou, ale množstvím nějakého kusu paměti, kterou má interpret zrovna k dispozici. Takže podle aktuální nálady GC to může pokaždé dopadnout různě.

        1. Jarin

          Re: Stack overflow a TCO
          Ono to neni ani tak podle nalady GC jako spis podle toho, kdy virtualni masina skonci s optimalizacema. Interpreter a optimalizovany kod maji ruzne velikosti zaznamu na zasobniku, takze zasobnik pretece ruzne (hloubka zasobniku je omezena ciselnou konstantou).

          Co se tyka TCO, je to opravdu problem s inspekci zasobniku ve vyjimkach – TCO nici zaznamy na zasobniku, a tak jsou obavy, ze by to rozhodilo ruzne logovaci nastroje.

          (Pro uplnost, pracuji v Chrome/v8 teamu.)

  2. R.Th

    Definícia nie je rekurzívna!
    Trochu bokom, ale nedá mi to:
    Citovaná definícia vôbec nehovorí o rekurzii, prečo ju teda factorialFromDefinition() používa?!

    1. Martin Hassman

      Re: Definícia nie je rekurzívna!

      To je hodně kuriozní otázka a také hodně nesrozumitelná. Takže, co vlastně čekáte za odpověď?

      1. Vladimir L

        Re: Definícia nie je rekurzívna!
        Ja tomu porozumel tak, ze podle R.Th. se neshoduje rekurzivni definice s Ondrou uvedenou „soucin cisel od 1 do n a v pripade nuly je napevno 1“. Nitpicking, rekurzivni definice faktorialu je taky pekna, ale komentar naznacuje, ze se funkce mela jmenovat v kontextu clanku factorialRecursive a myslim, ze ocekava autorovo vysypani si popela na hlavu :).

  3. FilipJirsak

    Žádná definice matematického jevu nebo problému nemluví o rekurzi. Rekurze je jenom jeden z možných způsobů implementace. A řekl bych, že v případě článku je vztah integrálu a použití rekurze opačný, než to na první pohled vypadá – sice je to napsané tak, že autor chtěl spočítat faktoriál, tak použil rekurzi, ale spíš to bude opačně, že chtěl psát o rekurzi, a k tomu se často jako příklad používá právě faktoriál. Protože samotná implementace je triviální a neodvádí tak pozornost čtenáře od podstaty, kterou je rekurze, nikoli nějaký výpočet.

      1. Martin Hassman

        Re:

        Celé se to komplikuje tím, že slovo rekurze může mít dle kontextu více významů, viz třeba https://cs.wikipedia.org/wiki/Rekurze S příchodem více lidí a komentářů (tj. typicky krátkých textů, kde je kontext jasný spíše hůře nebo vůbec) se diskuse stává obtížnou ne-li nemožnou.

  4. bofteam

    Někdy používám funkcionální zápis ve smyslu níže, i když to možná není uplně čisté.

    const f = (n) => ((n > 1) ? Array.from({length: n}).reduce((a, v, i) => (a * (i + 1)), 1) : 1);
    
  5. fortran1986

    TCO varianta
    Pekný článok ďakujem autorovi… len ma udivuje keď sa ľudia snažia programovať funkcionálne v imperatívnom jazyku ako JS, ktorý nemá ani podporu TCO (aj keď dá sa doplnmiť pomocou trampoline funkcie) ani podporu curried funkcií bez ktorých je funkcionálne programovanie IMHO peklo.

    Moja rekurzívna funkcia v F#: https://tinyurl.com/factorial-f má 3 riadky (dala by sa skrátiť aj na jeden ale to už by bolo neprehľadné). F# kód sa kompiluje sa do JS. To Mko za číslicami znamená literál pre typ decimal. Predtým som tam mal integer ale ten veľmi rýchlo pretiekol. Zvolil som decimal lebo ten má najmenej obmedzení. BigInt by som asi použil skôr, ale ten je objektový a to by už potom nemalo taký elegantný zápis.

Napsat komentář

Tato diskuse je již příliš stará, pravděpodobně již vám nikdo neodpoví. Pokud se chcete na něco zeptat, použijte diskusní server Devel.cz

Zdroj: https://www.zdrojak.cz/?p=22162