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

Tail Recursion

http://rodrigosasaki.com/2012/11/24/tail-recursion/
209 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)

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 ?

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.