Tail Recursion in Haskell

Question

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?

Thanks!

Solution 1

There are two issues here. One is tail recursion in general, and the other is how Haskell handles things.

Regarding tail recursion, you seem to have the definition correct. The useful part is, because only the final result of each recursive call is needed, earlier calls don't need to be kept on the stack. Instead of "calling itself" the function does something closer to "replacing" itself, which ends up pretty much looking like an iterative loop. This is a pretty straightforward optimization that decent compilers will generally provide.

The second issue is lazy evaluation. Because Haskell only evaluates expression on an as-needed basis, by default tail recursion doesn't quite work the usual way. Instead of replacing each call as it goes, it builds up a huge nested pile of "thunks", that is, expressions whose value hasn't been requested yet. If this thunk pile gets big enough, it will indeed produce a stack overflow.

There are actually two solutions in Haskell, depending on what you need to do:

• If the result consists of nested data constructors--like producing a list--then you want to avoid tail recursion; instead put the recursion in one of the constructor fields. This will let the result also be lazy and won't cause stack overflows.

• If the result consists of a single value, you want to evaluate it strictly, so that each step of the recursion is forced as soon as the final value is needed. This gives the usual pseudo-iteration you'd expect from tail recursion.

Also, keep in mind that GHC is pretty darn clever and, if you compile with optimizations, it will often spot places where evaluation should be strict and take care of it for you. This won't work in GHCi, though.

Solution 2

You should use the built-in mechanisms, then you don't have to think about ways to make your function tail-recursive

fac 0 = 1
fac n = product [1..n]

Or if product weren't already defined:

fac n = foldl' (*) 1 [1..n]

(see http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 about which fold... version to use)

Comments

[rsenna]

+1: I would only add that tail-call optimization is fundamental, for obvious reasons, on pure functional languages like Haskell (but kind of pointless in mixed or pure imperative languages like C# or Python).

[C. A. McCann]

@rsenna: I wouldn't call it pointless, just easier to work around when the optimized version of the simplest case is a language primitive. TCO is still strictly superior, in that you can e.g. have two functions tail-calling each other or something more complicated.

[rsenna]

@camccann: Don't get me wrong, I'm very fond of functional languages... I'm guess what I'm trying to say is that, in languages that do have imperative looping, the presence of TCO would just make things more confusing... Even not being a Python programmer myself, I do agree with the Zen of Python, especially "There should be one -- and preferably only one -- obvious way to do it". Let tail-call be used only on languages that require recursion as the only looping construct, that's all what I'm saying.

[C. A. McCann]

@rsenna: Er, I'm really not seeing how leaving out a compiler optimization will make a language less confusing? And the "only one way to do it" thing is hard to take seriously, since if we're picking a single iteration technique, general recursion is a much better choice than the random assorted flavors of loops most languages have.

[rsenna]

@camccann: it can, and it's easy to see why: TCO looping and imperative looping are equivalent, which means that both strategies are able to achieve the same objectives. But if I allow both ways, both ways will be used. That translates in a maintenance nightmare: so many different styles that becomes very hard to a programmer to easily understand another programmers style. You seem to be a very academical individual, which is fine btw. But on real world scenarios, it's better to have just one way to do it (being it functional or imperative).

[Matt Ellen]

That hardly seems the point of the question. The question is about what tail recursion is. -1

[John L]

@rsenna: I'm not entirely sure what you're advocating. Are you saying that imperative language compilers shouldn't implement TCO because the performance hit will discourage users from writing recursive functions, or do you think that imperative languages shouldn't allow recursive functions at all? Or something else?

[Landei]

There is already a good, sufficient answer by camccann. I don't know how you see this, but I'm always happy if I get both my question answered, and some additional information, considerations or critique. And instead of down-voting, why don't you simply write a more helpful answer?

[C. A. McCann]

@rsenna: I'm not an academic in any sense. I don't do research, I just write programs to get things done. I learn new abstract concepts because they expand my ability to think about the structure of programs, and I use tools to automate anything I can. You seem to be saying that ignoring abstractions and crippling tools is... somehow better for the "real world"? I really don't understand.

[C. A. McCann]

You realize that without optimizations, foldl will cause stack overflows on large lists, right? Seems a bit ironic in context.

[Landei]

@camccann: Thanks for the hint, I always forget which one to use. Corrected.

[C. A. McCann]

Here's a rule of thumb: foldl is almost never the one to use.

[CoR]

@Landei: Answering a question is good. Pointing to the next step is teaching! +1 from me :)

[Björn Lindqvist]

The reason Python doesn't do tco is because it trashes the stack frames. Without tco, you can reconstruct the control flow in self-recursive functions quite easily. With tco, you can't do that since all the calls have vanished.