# Help: Stack-overflow and tail-recursive functions

Hal Daume t-hald@microsoft.com
Wed, 18 Jun 2003 17:36:28 -0700

```Note that there is essentially no difference between f1 and f2.  When
you \$! in f2, all it does is ensure that the argument isn't undefined.
It doesn't evaluate any of the list.  Try \$!! from the DeepSeq module or

For me, the following works:

f1 0 l =3D l
f1 n l =3D f1 (n-1) \$!! (take 3 \$ l ++ [0,1])

f \$!! x =3D force x `seq` f x
where force [] =3D ()
force (x:xs) =3D x `seq` force xs

whereas it doesn't without the \$!!.

--
Hal Daume III                                   | hdaume@isi.edu
"Arrest this man, he talks in maths."           | www.isi.edu/~hdaume

> -----Original Message-----
> Sent: Wednesday, June 18, 2003 5:18 PM
> Subject: Help: Stack-overflow and tail-recursive functions
>=20
>=20
> Hi
>=20
> I've written a function that is tail-recursive and takes
> a list(queue) as one of its arguments.
> However the function fails because of
> "Stack space overflow"(GHC) or "ERROR - Garbage collection=20
> fails to reclaim sufficient space"(hugs).
>=20
> For example (simplified), both of these results in=20
> stack-overflow: f1 100000 [0,1,2], and even f2 100000 [0,1,2],
>=20
> where,
> f1 0 l =3D l
> f1 n l =3D f (n-1) \$ take 3 \$ l ++ [0,1]
>=20
> f2 0 l =3D l
> f2 n l =3D f2 (n - 1) \$! (take 3 \$ l ++ [0,1])
>=20
> Why f2 overflows?
>=20
> How to avoid this stack-overflow?
>=20
> _______________________________________________