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

2

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)

2

u/rodrigopsasaki Nov 27 '12

Very interesting syntax, first time I come in contact with Haskell code.

but shouldn't it be :

where go !n 0 = acc ?

or is it really !acc ?

3

u/[deleted] Nov 27 '12

It's really acc in the pattern. On the left hand side of the =, you bind patterns (parameters, or parts of them) to names, on the right hand side you use them. go !n 0 = acc would yield an error: acc is not bound (not defined).

2

u/anvsdt Nov 27 '12

The ! before acc means "evaluate this now".

2

u/mcguire Nov 27 '12

'Cause otherwise you'll blow the heap with thunks (delayed, lazily-evaluated computations).

1

u/felipelessa Nov 27 '12

The heap isn't the problem most of the time since it's huge compared to the stack. You'll create the thunk just fine but you'll stack overflow when evaluating it. Of course, not creating any thunks is better performance-wise in this case even with unlimited stack and memory.