# [Haskell-cafe] Criteria for determining if a recursive function can be implemented in constant memory

Steffen Schuldenzucker sschuldenzucker at uni-bonn.de
Mon Jul 5 08:23:20 EDT 2010

```Dear Cafe,

since a little discussion with my tutor I am wondering how the following
problem can be solved and if it is decidable:

Given the definition of a recursive function f in, say, haskell,
determine if f can be implemented in O(1) memory.

First I thought the solution would be "check if f is tail-recursive".
However, consider the following definition:

> -- for the sake of uniformity
> if' c t e = if c then t else e
>
> f :: (Num a) => a -> a -> a
> f x y = if' (x <= 0) y \$
>    if' (x >= 2) (f (x-2) (y+1)) (f (x-1) y)

(I don't really care what this function computes as long as it
terminates, which is obvious)

Although ghc will probably not perform this optimization, f can be
realized in O(1) mem:

// trying to duplicate f's structure as closely as possible
double f( double x, double y )
{
START:
if ( x <= 0 )
return y;
else
{
if ( x >= 2 )
{
x = x - 2;
y = y + 1;
goto START;
}
else
{
x = x - 1;
y = y;
goto START;
}
}
}

It is crucial that (the second) if' does not use both of its last two
arguments, but only one. If we replace the second if' by, say

> g :: (Num a) => c -> a -> a -> a
> g c t e = if' c (t + e) (t - e)

, then we have to compute *both* (f (x-2) (y+1)) and (f (x-1) y), and x
and y have to be kept in memory during the call to (f (x-2) (y+1)),
therefore f cannot be implemented in constant memory. (read: I haven't
found a way which does not radically alter f's structure).

So, does someone know how to solve this or can prove that it can't be
solved?

Best regards,

Steffen

```