Rekurze v imperativních jazycích

[dl]

 (...) In imperative languages, recursion always raises the specter of stack overflows (too many recursive calls) and performance issues (...)

Jaký je rozdíl mezi správně naprogramovanou rekurzivní funkcí (pokud neudělám nějakou nekonečnou smyčku) např. v C namísto nějakého funcionálního jazyka?

[Reklama]

[ded.kenedy]

To jsou nehezka sluvka a veticky. Viz http://en.wikipedia.org/wiki/Tail_recursion

Tail calls are significant because they can be implemented without adding a new stack frame to the call stack.

Traditionally, tail call elimination is optional. However, in functional programming languages, tail call elimination is often guaranteed by the language standard, and this guarantee allows using recursion, in particular tail recursion, in place of loops

Vetsina dnesnich prekladacu imperativnich jazyku dela eliminaci tail-callu, ergo vyse zmineny citat neni pravdivy.

[Sten]

Sám jste si odpověděl, i když to nevíte Ve funkcionálních jazycích není problém mít nekonečnou rekurzi, oblíbená bývá funkce vracející celou Fibonacciho posloupnost, program používá lazy evaluation a výpočet provádí, až když je potřeba, a jen do potřebné hloubky. V imperativních jazycích to nepůjde (pokud si na to explicitně nenapíšete funktor), program by se tu posloupnost pokusil vypočítat rovnou.

[perceptron]

napr. java [jazyk] tail-call-optimization nerobi, rovnako ani clojure, groovy 2.3+ umoznuje dodat anotaciu a pomoct kompilatoru

[eMko]

Clojure má konstrukci loop-recur (případně se používá trampoline) právě pro to, že JVM neumožňuje tail-call optimalizaci. Na druhou straunu překladač Scaly, která taky běží nad JVM, to "umí" - tím, že z toho udělá cyklus.

Jestli je to možné u C# 5, to se přiznám, že nevím - překladač verze 4 to neumí byť .Net to podporuje. C/C++ u novějších překladačů (jak Microsoft tak GCC) to umí a nedávno jsem to viděl i u free pascalu. Nicméně často se musí explicitně zapnout.

Každopádně i když rekurze je ve funkcionálních (a logických) jazycích celkem často k vidění, v imperativních jazycích není až tak potřeba - stejně je většinou pohodlnější tu danou věc zapsat cyklem než rekurzí.

[Reklama]

[dl]

@Sten
Děkuju, to mne vlastně ani nenapadlo. To je odpověď hodná lišky
@ded.kenedy
Díky za připomínku.

[Ondra Satai Nekola]

http://llvm.org/docs/Passes.html#tailcallelim-tail-call-elimination

[Ttxman]

Jestli je to možné u C# 5, to se přiznám, že nevím - překladač verze 4 to neumí byť .Net to podporuje.

v C# to nejde vnutit (jazyk to neumi) a ani si nemuzete byt uplne jisti, ze neco bude tail call. Ale jak pises, tak .NET to umi a JIT compiler pouziva tail call optimalizace. Takze rekurzivni funkce v release konfiguraci je dost casto tail call optimalizovana a stack neplni.

(Na coz jsem prisel kdyz se mi v release kofiguraci zacyklilo vlakno a v logach nic nebylo. Jenom v nekterejch vicemene nahodnejch situacich diky blbe napsany rekurzi pribyl 1 worker thread co nikdy nezkoncil a sezral 1 CPU. Prijit na to proc server zpomaluje a zpomaluje dalo diky absenci chyb celkem praci. Zase me to naucilo davat vsude timeouty )

[Někdo]

Asi jsem už moc starý, ale za mých mladých let jsme si takový luxus jako je "tail recursion optimalization" nemohli užívat, takže jsme se museli naučit přemýšlet a rekurzi psát jen tam kde jsme si nemohli vystačit s jinými, efektivnějšími přístupy. Napsat počítání faktoriálu nebo Fibonacciho posloupnosti pomocí rekurze bylo považováno za hrubou chybu. Mimochodem, mám pocit že zrovna ta Fibonacciho posloupnost se automaticky optimalizovat nebude ani dnes - že by tedy nastal čas opět u programování přemýšlet? Ale abych odpověděl k původnímu tématu - imperativní jazyky obvykle nedělají optimalizaci v případě že rekurzivní volání je poslední v rekurzivně volané metodě, což modernější jazyky umějí optimalizovat - ale to ani zdaleka nepokrývá všechny druhy rekurze! A vězte že metoda se nemusí volat rekurzivně sama, může jít o více metod které se rekurzivně volají navzájem - a tam podle mě už nezbývá než doopravdy hodně dobře přemýšlet, zatím jsem neviděl jazyk který by toto dokázal optimalizovat...

[student]

takže jsme se museli naučit přemýšlet a rekurzi psát jen tam kde jsme si nemohli vystačit s jinými, efektivnějšími přístupy.

Rekurzia sa da vzdy prepisat inak, aj ked je na to niekedy treba premyslat.

Každopádně i když rekurze je ve funkcionálních (a logických) jazycích celkem často k vidění, v imperativních jazycích není až tak potřeba - stejně je většinou pohodlnější tu danou věc zapsat cyklem než rekurzí.

Naopak - pri netrivialnych problemoch byva pohodlnejsie "rozdel a panuj", co vedie priamociaro na rekurziu. Ta sa sice da prepisat na iterativny postup, ale to potom nebyva take prehladne.

Navrh pomocou rozdel a panuj ma pri aspon trochu rozumnom navrhu 1 velku vyhodu - chova sa to lepsie ku cache a teda to zvykne fungovat rychlejsie.

[Natix]

Mimochodem, mám pocit že zrovna ta Fibonacciho posloupnost se automaticky optimalizovat nebude ani dnes - že by tedy nastal čas opět u programování přemýšlet?

Ona ta tail optimalizace není zadarmo, daná metoda musí splňovat určité požadavky. Musí jít o lineární rekurzi tzn. že metoda sama sebe volá pouze jednou a toto volání musí být poslední výraz v ní. Triviální fibonacci nesplňuje ani jedno z toho, takže je třeba ho přepsat do podoby s akumulátorem, která už není tak elegantní.

[podlesh]

že by tedy nastal čas opět u programování přemýšlet?

Pro úplnost bych doplnil, že cílem optimalizace tail recursion není a nikdy nebylo programování bez přemýšlení. Spíš naopak.

[eMko]

Ona ta tail optimalizace není zadarmo, daná metoda musí splňovat určité požadavky [...]

Což vyplývá z definice "tail call optimization" - optimalizuje se pouze poslední výraz.

Rekurze s akumulátorem je možná o trochu méně elegantní, ale zrovna v tomto případě stále lépe čitelná než imperativní přístup se změnou hodnot proměnných v cyklu.

[Natix]

Tady ještě jak to konkrétně vypadá ve Scale:

Kód: [Vybrat]

@tailrec
private def fibonacciTail(n: Int, acc: (BigInt, BigInt)): BigInt = {
    val (x, y) = acc

    if (n == 0 || n == 1) y
    else fibonacciTail(n - 1, (y, x + y))
}

def fibonacci(n: Int) = fibonacciTail(n, (1, 1))
Kompilátor aplikuje tail call optimalizace automaticky, @tailrec anotace pouze zajistí kontrolu, že daná metoda opravdu tail rekurzivní je (jinak compile error).

[Radek Miček]

Kompilátor aplikuje tail call optimalizace automaticky, @tailrec anotace pouze zajistí kontrolu, že daná metoda opravdu tail rekurzivní je (jinak compile error).

Bohužel tail call optimalizace se ve Scale u řady tail callů neaplikuje.