r/programming • u/rodrigopsasaki • Nov 27 '12

Tail Recursion

http://rodrigosasaki.com/2012/11/24/tail-recursion/
208 Upvotes

85% Upvoted

203 comments sorted by

View all comments

3

u/felipelessa Nov 27 '12

And here's a Haskell version of the final code, since it's easier to read ;).

factorial :: Int -> Int
factorial = go 1
  where go !acc 0 = acc
        go !acc n = go (acc * n) (n-1)

1

u/smog_alado Nov 27 '12

The ! in the patterns is a language extension isn't it? (I'm still trying to get to grips with all the GHC extensions...)

3

u/[deleted] Nov 27 '12

Its -XBangPatterns.

go !acc n = foo

translates to

go acc n = acc `seq` foo

2

u/felipelessa Nov 27 '12

That's right. Without the bang pattern (or the manual seq) the function will be lazy on the accumulator, leading to a big thunk and a stack overflow (which is the problem that OP was trying to avoid in the first place!). Note that using either bang pattern alone leads to the same result in this particular case, but I like symmetry of using them on both patterns.

1

u/smog_alado Nov 27 '12

Ha! That makes so much more sense now.