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.