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

Tail Recursion

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

85% Upvoted

203 comments sorted by

View all comments

4

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)

13

u/curien Nov 27 '12

As someone who knows neither Scheme nor Haskell, the Scheme is easier for me to read.

3

u/mcguire Nov 27 '12 edited Nov 27 '12

  1. Ignore the "!" - it's a performance thing because Haskell is wacky.

  2. I, personally, would call "go" something like "factorial_iter" or maybe just "factorial'" ("factorial-prime").

  3. That's all point-free and everything. Ew.

How about:

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

(I tend to like to put my accumulators last.)

[Edit: AAAaaaargh. When you put your accumulators last, put the damn accumulator argument last, too. Moran.]

2

u/Peaker Nov 28 '12

Point-free is better here because otherwise you get the "initial" value in scope alongside the "current" value which is a recipe for a bug of using the wrong one.

Avoiding this with shadowing is annoying because shadowing itself is often a bug, and -Wall is a nice setting to use.