I am trying to understand tail-recursion in Haskell. I think I understand what it is and how it works but I'd like to make sure I am not messing things up.
Here is the "standard" factorial definition:
factorial 1 = 1
factorial k = k * factorial (k-1)
When running, for example,
factorial 3, my function will call itself 3 times(give it or take). This might pose a problem if I wanted to calculate factorial 99999999 as I could have a stack overflow. After I get to
factorial 1 = 1 I will have to "come back" in stack and multiply all the values, so i have 6 operations (3 for calling the function itself and 3 for multiplying the values).
Now I present you another possible factorial implementation:
factorial 1 c = c
factorial k c = factorial (k-1) (c*k)
This one is recursive, too. It will call itself 3 times. But it doesn't have the problem of then still having to "come back" to calculate the multiplications of all the results, as I am passing already the result as argument of the function.
This is, for what I've understood, what Tail Recursion is about. Now, it seems a bit better than the first, but you can still have stack overflows as easily. I've heard that Haskell's compiler will convert Tail-Recursive functions into for loops behind the scenes. I guess that is the reason why it pays off to do tail recursive functions?
If that is the reason then there is absolutely no need to try to make functions tail recursive if the compiler is not going to do this smart trick -- am I right? For example, although in theory the C# compiler could detect and convert tail recursive functions to loops, I know (at least is what I've heard) that currently it doesn't do that. So there is absolutely no point in nowadays making the functions tail recursive. Is that it?