That distinction between algorithms and implementa...

2012-01-01T04:57:10.061+05:30

That distinction between algorithms and implementations is actually a good one. I've never thought of it that way, and I guess the word "computation" hides the difference.

Your point about stack space being independent of input size not being equivalent to it being constant is not something I follow. Assuming tail call optimization, I don't see why your program wouldn't take constant stack space (if x is arbitrary-precision then presumably the stack would only have a reference to it).

I've always thought of tail-call optimization ...

2011-12-31T01:26:47.980+05:30

I've always thought of tail-call optimization as a mechanism to convert a recursive *algorithm* into an iterative *implementation*.

I guess there are fundamentally unoptimizable recursive algorithms, recursive algorithms which are optimizable via tail call elimination, and recursive algorithms which are or are not optimizable to constant stack space in language X version Y.

Then there are iterative implementations and recursive implementations, by which I mean implementations that use stack space that is constant or not.

Is that equivalent to the amount of stack space being independent of the input size? I suppose not -- I would say a straightforward implementation of fun f(x) = rand() > 0.5 ? x : f(x*2) would be described as recursive, not iterative.

Note that language X could legally translate that to something similar to x << rand(sizeof(int)), which would almost certainly produce an iterative or at least non-recursive implementation.

Comments on defunct: So, what *is* recursion?

That distinction between algorithms and implementa...

I've always thought of tail-call optimization ...

Comments on defunct: So, what is recursion?