[clean-list] Memory usage in recursion

[Jerzy Karczmarczuk]

F.S.A.Zuurbier@inter.nl.net wrote:
> 
> Eddy wrote:
> ==========================
> ... Usually you don't know in
> advance what the 'size' of the data will be and you don't know exactly how
> deep the recursion will be. As a result of this, a 'stack overflow' 
> can occur.
> Is this also the case in Clean or is the data storage during recursion
> handled in a different way?
> Kind regards
> Eddy
> ========================

> Clean and other functional programming languages would not be useful if this problem had not been solved. Indeed, it has been solved. So called tail-recursion can usually (if not always) by compiled in such a way that a stack-frame is not needed.
> 
> Regards Erik Zuurbier

+++

Well, the tail recursion is useful where applicable.
There are plenty of cases where it isn't, and Clean finds itself
in the same trap as other languages. The 'depth' recursion *must*
use the stack, and no miracle is possible. The possibility to allocate
the stack on the heap, as observed by Richard A. O'Keefe, is another
story.

R.A.K. quotes:

> >Is this also the case in Clean or is the data storage during 
> >recursion handled in a different way?

> You don't need to know.  There isn't any special problem.


Weeelll, <<cum grano salis>>...

We have also the laziness. The definition

integs = ig 0 where
  ig n = [n : ig (n+1)]

is *not* tail-recursive, and in a strict language it would explode.
But if the result is used *incrementally*: consume the head and
pass the rest to another stage without ever keeping the entire
list in memory, then this recursion becomes an iteration, and the stacks
are safe.

About EZ phrase: "usually (if not always)..."
Not always. (And not only because the compilers of, say, C++ are lousy).
In Prolog or other Logic Programming Languages the calls often must
leave something on the "trail" in order to enable the backtracking.
So, even the tail calls may overflow internal data structures, unless
the user is conscious and "cuts" the backtrack points.

Jerzy Karczmarczuk
Caen, France