[Haskell-cafe] Debunking tail recursion

[Albert Y. C. Lai]

Jules Bean wrote:
> A conversation on #haskell just showed that it's quite hard to explain 
> (at least it is for me) to people attached to tail recursion why that is 
> a red herring in Haskell.

What is tail recursion?

Suppose

(1)    x = f y x

A participant of the said conversation classified this to be not tail 
recursion.

Suppose further

(0)    f y x = x

Is (1) a tail recursion now?

Eager evaluation says, to evaluate x, call x and y first, then there is 
still f to call, so x is hardly the tail call.

Lazy evaluation says, to evaluate x, call f first, then x is the last 
call. I have problem regarding this not tail recursion, but I seem to be 
alone.

Define

(2)    cs = 'c' : cs

Is (2) a tail recursion?

Use it with

(3)    putStr cs

Lazy evaluation together with putStr's forcing order says, to evaluate 
cs, get to the cons cell first, then evaluate 'c', then cs is the last call.

Or use it with

(4)    putStr [cs !! 5, cs !! 3]

Then cs is not the last call: for some n, the nth recursive call to cs 
happens before evaluating the nth 'c'.

I no longer understand what other people mean by tail recursion. Am I 
attached to tail recursion? I am certainly attached to some recursion, 
which I consider to be tail recursion, but other people say it is not, 
and under some exotic usage it is indeed not. Perhaps I am attached to 
what they consider init recursion or middle recursion. Is tail recursion 
a red herring? "Tail recursion considered a red herring"? "(Tail 
recursion considered a red herring) considered a red herring"?