Rekurze v imperativních jazycích

Karel

Re:Rekurze v imperativních jazycích
« Odpověď #15 kdy: 06. 05. 2014, 11:10:56 »
Rekurze, pokud nemá omezenou hloubku, skutečně dokáže přeplnit zásobník. V devadesátých letech to ale nebyl problém, protože programátoři věděli, kdy použít rekurzi a kdy iteraci. Jenže dnes se asi všechno řeší metodou hrubé síly a tak se spíše optimalizuje rekurze, než aby se použila iterace. Přitom před 20 lety se běžně učilo na úlohách typu "přepište následující část programu z rekurze na iteraci".


Sten

Re:Rekurze v imperativních jazycích
« Odpověď #16 kdy: 06. 05. 2014, 13:29:42 »
Rekurze, pokud nemá omezenou hloubku, skutečně dokáže přeplnit zásobník. V devadesátých letech to ale nebyl problém, protože programátoři věděli, kdy použít rekurzi a kdy iteraci. Jenže dnes se asi všechno řeší metodou hrubé síly a tak se spíše optimalizuje rekurze, než aby se použila iterace. Přitom před 20 lety se běžně učilo na úlohách typu "přepište následující část programu z rekurze na iteraci".

Ani iterace s neomezenou hloubkou nebude v imperativních jazycích to pravé ;)

Natix

Re:Rekurze v imperativních jazycích
« Odpověď #17 kdy: 06. 05. 2014, 13:49:30 »
Přitom před 20 lety se běžně učilo na úlohách typu "přepište následující část programu z rekurze na iteraci".

Scheme umí tail call optimalizaci už skoro 40 let.

Franta <xkucf03/>

Re:Rekurze v imperativních jazycích
« Odpověď #18 kdy: 06. 05. 2014, 13:59:10 »
Ani iterace s neomezenou hloubkou nebude v imperativních jazycích to pravé ;)

Co je hloubka u iterace? Můžu klidně iterovat přes „nekonečný“ vstup a třeba sčítat hodnoty nebo transformovat data a posílat je na výstup a nebude v tom problém.

Karel

Re:Rekurze v imperativních jazycích
« Odpověď #19 kdy: 06. 05. 2014, 14:14:50 »
Přitom před 20 lety se běžně učilo na úlohách typu "přepište následující část programu z rekurze na iteraci".

Scheme umí tail call optimalizaci už skoro 40 let.

To nepopírám. Já tvrdím, že před 20 lety to byl zajímavý bonus, zatímco dnes to díky stylu programování občas představuje životní nutnost. Ve chvíli, kdy pak z nějakého důvodu tail call neuspěje, jsou mladí chlapci často bezradní, protože díky všelijakým funkcionálním jazykům nezvládají klasické imperativní iterace.


Karel

Re:Rekurze v imperativních jazycích
« Odpověď #20 kdy: 06. 05. 2014, 14:23:15 »
Ani iterace s neomezenou hloubkou nebude v imperativních jazycích to pravé ;)

Neomezená hloubka nepředstavuje pro iterace žádný problém. Možná jste si to spletl s podobně vypadajícím výrazem "nekonečná". To ano, nekonečné iterace obvykle nekončí. Ale jakmile je hloubka konečná, tak to prostě jednou dopočítá. Lazy evaluation to v obecné rovině žádným způsobem nezlepší. Je to jen syntaktický cukr, který za vás opodmínkuje, zda se má výpočet vůbec provést nebo ne, případně omezí hloubku výpočtu. To můžete i v imperativních jazycích, jen se víc napíšete.

v

Re:Rekurze v imperativních jazycích
« Odpověď #21 kdy: 06. 05. 2014, 15:10:42 »
mě by taky zajímalo co je to ta "Neomezená hloubka iterace" a "nekonečná" a proč je to problém

Karel

Re:Rekurze v imperativních jazycích
« Odpověď #22 kdy: 06. 05. 2014, 17:55:38 »
mě by taky zajímalo co je to ta "Neomezená hloubka iterace" a "nekonečná" a proč je to problém

Rekurzivní volání vytváří záznamy na zásobníku. Kupříkladu VBA vám v závislosti na nastavení může omezit hloubu zásobníku na 100 volání. Pokud budete mít funkci, která vám rekurzivně počítá například nejmenšího společného dělitele, tak vám to NSD(2, 100) spočítá, protože se zanoří cca 50x. Jenže pokud zavoláte NSD(2,1000), tak už je to cca 500 volání a to je problém.

A teď k omezená / neomezená. Pokud já nějakým způsobem omezím množinu, nad kterou se funkce používá, tak také omezím počet rekurzivních volání. Tedy hloubku zanoření. Pokud funkce NSD bude jen pro čísla od 1 do 100, tak je to omezení dostatečně přísné na to, abych se nemusel zabývat limitem technologie. Pokud ale ten limit nebude, nebo bude mnohem vyšší, pak mohu na problémy technologie narazit. Mohu vyčerpat volnou paměť, narazit na nějaký limit stránkování atd.

Funkce s neomezenou hloubkou rekurze je tedy funkce, u které z povahy dat může být nutná hloubka jakákoliv. Ale je tam, někde se zastaví. Pokud budu počítat NSD(2,200000000), tak ta hloubka bude cca 100 milionů vnoření. To je na zásobník příliš mnoho, ale přesto je to číslo, u kterého se to zastaví.

No a nekonečná hloubka je taková, kdy se to prostě nezastaví. Na první pohled je zřejmé, že volání nekonečné funkce je problém. Jenže tomu tak být nemusí, protože díky lazy evaluation nakonec vůbec k volání funkce nemusí dojít a program doběhne přesto, že tam to volání zjevně napsané je.

Co tím autor myslel v případě iterací si nejsem jistý, ale přepokládal jsem, že to měla být analogie právě k hloubce rekurze. Zatímco vnořit se do funkce 100 milionkrát je pro zásobník problém, tak mít cyklus, který se 100 milionkrát zopakuje, to už problém není. U iterace tudíž existence limitu vstupních hodnot nemá vliv na to, zda to fungovat bude nebo ne. Má to vliv jen na to, zda to doběhne v rozumné době. U rekurze je neexistence limitu risk, protože program může spadnout.

Obecně se proto doporučuje odhadovat hloubku rekurze a buď do ní uměle limit přidat, nebo ji nahradit iterací. Výše zmíněné "tail call" je technika, kdy specifickým způsobem zapsané rekurzivní volání může překladač nebo interpretter převést na iteraci za vás. Skutečností je, že úprava rekurzivní funkce na tail call není snadnější, než její přepsání na iteraci. Kolikrát spíše naopak. Přiznávám, že tail call se trochu lépe čte.

v

Re:Rekurze v imperativních jazycích
« Odpověď #23 kdy: 06. 05. 2014, 18:01:39 »

děkuji za vyčerpávající odpověď na otázku, kterou jsem nepoložil

podlesh

Re:Rekurze v imperativních jazycích
« Odpověď #24 kdy: 07. 05. 2014, 12:22:40 »
To nepopírám. Já tvrdím, že před 20 lety to byl zajímavý bonus, zatímco dnes to díky stylu programování občas představuje životní nutnost. Ve chvíli, kdy pak z nějakého důvodu tail call neuspěje, jsou mladí chlapci často bezradní, protože díky všelijakým funkcionálním jazykům nezvládají klasické imperativní iterace.
Zajímavé tvrzení. Jsou pro to nějaké (byť jen minimální) podklady?
Nebo jak říkají mladí chlapci: [Citation needed]


eMko

  • ****
  • 456
    • Zobrazit profil
    • E-mail
Re:Rekurze v imperativních jazycích
« Odpověď #25 kdy: 07. 05. 2014, 17:47:13 »
Mě se jeden ostřílený borec zeptal co je "unique_ptr" v C++ - po odpovědi "náhrada za auto_ptr" se zeptal "co je to auto_ptr". Místo, aby si všiml, že před 14 lety přibyla šablona auto_ptr do standardní knihovny jazyka, raději řešil memory leaky a bordel na haldě. Podobný dotaz položil k výrazu "builder pattern".

Mám to snad po vzoru Karla také tak debilně generalizovat na větu:

Já zas vidím spoustu ostřílených zkušených borců, co díky všemožným asemblerům, Cčkům, Pascalům a Fortranům nezvládají základní objektové návrhové vzory, C# po nich vypadá jako brainfuck (teda sorry, COBOL) a díky ignoraci nových věcí v základní knihovně jejich hlavního jazyka nezvládají základní práci s pamětí?

belzebub

Re:Rekurze v imperativních jazycích
« Odpověď #26 kdy: 07. 05. 2014, 21:28:18 »
To nepopírám. Já tvrdím, že před 20 lety to byl zajímavý bonus, zatímco dnes to díky stylu programování občas představuje životní nutnost. Ve chvíli, kdy pak z nějakého důvodu tail call neuspěje, jsou mladí chlapci často bezradní, protože díky všelijakým funkcionálním jazykům nezvládají klasické imperativní iterace.
To je skutecne roztomiloucke tvrzeni. Ano, setkal jsem se s mladymi i starymi "chlapci", co byli bezradni, kdyz po nich nekdo chtel i velmi trivialni veci napsat funkcionalne. Fold pro ne byla cerna magie a veci jako "write-only" promenne brali jako satanovo prokleti. Ale s tim, ze by nejaky "chlapec" libovolneho veku, ovladajici nejaky funkcionalni jazyk, mel "problem s klasickou imperativni iteraci", tak to ne, s tim jsem se tedy opravdu nesetkal.

asfasdfasf

Re:Rekurze v imperativních jazycích
« Odpověď #27 kdy: 08. 05. 2014, 00:01:00 »
Mě se jeden ostřílený borec zeptal co je "unique_ptr" v C++ - po odpovědi "náhrada za auto_ptr" se zeptal "co je to auto_ptr". Místo, aby si všiml, že před 14 lety přibyla šablona auto_ptr do standardní knihovny jazyka, raději řešil memory leaky a bordel na haldě. Podobný dotaz položil k výrazu "builder pattern".
Nic proti nikomu, ale programoval ten borec v C++?
Znam par lidi, co dle jejich slov programuji v C++, ale pritom je to C se special structama se jmenem "class", co obsahuje funkce a dokonce jista navesti public a private, ktera maji specialni vyznam. A abych nezapomel, misto malloc a free se pouzivaji new a delete.

jOseph

Re:Rekurze v imperativních jazycích
« Odpověď #28 kdy: 08. 05. 2014, 00:33:15 »
To je skutecne roztomiloucke tvrzeni. Ano, setkal jsem se s mladymi i starymi "chlapci", co byli bezradni, kdyz po nich nekdo chtel i velmi trivialni veci napsat funkcionalne. Fold pro ne byla cerna magie a veci jako "write-only" promenne brali jako satanovo prokleti. Ale s tim, ze by nejaky "chlapec" libovolneho veku, ovladajici nejaky funkcionalni jazyk, mel "problem s klasickou imperativni iteraci", tak to ne, s tim jsem se tedy opravdu nesetkal.

"write-only" promenne? K cemu je to dobry?

Sten

Re:Rekurze v imperativních jazycích
« Odpověď #29 kdy: 08. 05. 2014, 02:48:23 »
To je skutecne roztomiloucke tvrzeni. Ano, setkal jsem se s mladymi i starymi "chlapci", co byli bezradni, kdyz po nich nekdo chtel i velmi trivialni veci napsat funkcionalne. Fold pro ne byla cerna magie a veci jako "write-only" promenne brali jako satanovo prokleti. Ale s tim, ze by nejaky "chlapec" libovolneho veku, ovladajici nejaky funkcionalni jazyk, mel "problem s klasickou imperativni iteraci", tak to ne, s tim jsem se tedy opravdu nesetkal.

"write-only" promenne? K cemu je to dobry?

Taky mě to překvapilo, protože to je Satanovo prokletí :) Write-only proměnné jsou úplně k ničemu. Ale možná si to autor spletl s write-once proměnnými, ty jsou ve funkcionálních jazycích (a nejen tam) docela běžné.