[clean-list] Memory usage in recursion

Richard A. O'Keefe ok@atlas.otago.ac.nz
Tue, 21 Nov 2000 11:46:01 +1300 (NZDT)


	As I understand from the Clean tutorial "Functional programming in Clean",
	Clean uses quite a lot of recursion to implement certain functions.

Any good book about functional programming will make clear the difference
between "body" calls and "tail" calls; tail calls are effectively jumps.

	What I know from other languages is that recursion usually makes
	extensive use of the stack.  When the code is assembled you
	usually see a number of 'pushes' and 'pops' to store and
	retrieve data on the stack.

There need not be any stack at all; Simula 67 put "stack frames" on the
garbage collected heap, and at least some functional languages do that to
this day (which makes it easier to implement concurrency).  Even those
language implementations that do use a stack do NOT commonly use pushes
or pops for that purpose.  C compilers don't.  The Quintus Prolog compiler
certainly didn't.

	As you all know the danger is that the depth of recursion
	depends on the data to be processed by the function in question.
	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.

Danger?  In the case of tail recursion, the depth of recursion could be
a hundred million million billion and the stack depth could still be zero.
But if data _do_ have to be saved on the stack, they have to be saved
_somewhere_.  Why is running out of stack space thought to be worse
than running out of space anywhere else?  It's only language implementations
such as old MS-DOS C compilers that artificially limited the stack size to
64 kB that had any special problem with this.  If you have 64MB of data to
store and 64MB of memory to put it in, why should you *care* whether the
place it's put is called "stack", "heap", or something else?  For what it's
worth, the stack is probably the cheapest place to put anything, because
it's likely to be reclaimed quickly and cheaply.
	
	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.