Been thinking about tail recursion lately. I think compilers should automatically make function definitions like this tail recursive:

fac 0 = 1
fac n | n > 0 = n * fac (n-1)

They can do this by noting, each time they recur, that the only thing to do after returning from this recursion is to multiply, or on the second recursion, to multiply twice. On the second recursion, these two multiplications can be simplified into one, right then and there. Like this:

fac 4:       (fac 4 = 4 * fac 3) =>
        (4*) (fac 3 = 3 * fac 2) =>
 (4*) . (3*) (fac 2 = 2 * fac 1) =>
       (12*) (fac 2 = 2 * fac 1) =>
(12*) . (2*) (fac 1 = 1 * fac 0) =>
       (24*) (fac 1 = 1 * fac 0) =>
(24*) . (1*) (fac 0 = 1)         => 24

This can compute factorials of arbitrarily large n while using constant stack space. The big deal here is that the compiler has to know when it's able to simplify two composed functions into one; in this case, it has to know that a*(b*c) = (a*b)*c, i.e. * is associative. Comments?

Ugh...

Okay. An iterative loop:

while (x) {

do y;

} (hold memory in z for next iteration)

Now, since you're using a bounded amount of space for z, you can imagine that all the information in z is held in a struct.

Tail recursion:

function tail (input, z) {

if (done) return answer;
else tail (input for next iteration, z for next iteration)
}

When you do the recursive call, all the information required is in the arguments, and you can drop everything else, thus using the same stack area.

Oh, and if you want to be pedantic about the matter, there is no such thing as O(1) space, because you need log N bits to hold the pointer to the input in memory.