Re: Avoiding use of the stack

On 2004 November 18 Thursday 06:15, [email protected] wrote:
> how to write recursive functions
> so that they don't eat up stack space, and instead behave more like while
> loops (I think you had to convert them to tail-recursive forms?).

> testR2 :: Integer -> Integer
> testR2 n = testR2' 0 n
> testR2' :: Integer -> Integer -> Integer
> testR2' a 0 = a
> testR2' a n = testR2' (a+n) (n-1)

You're on the right track.  This is properly tail recursive. The remaining 
problem is that the argument (a+n) does not get evaluated during the 
processing of testR2'.  So each successive call to testR2' is passed a larger 
expression such as
    testR2' (((((0+10)+9)+8)+7)+6) (6-1)
Pattern matching causes the second argument to be evaluated.
To ensure that the first argument is processed, you can use the $! operator.
    testR2' a n = (testR2' $! (a+n)) (n-1)
which evaluates (a+n) before passing it to testR2'.

Where you see stack overflow, it's actually a stack of + opeations rather than 
a stack of testR2' calls.