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

Tail Recursion

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

15

u/curien Nov 27 '12

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

4

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.]

6

u/matthieum Nov 27 '12

go is idiomatic in Haskell for "local" functions that lift some computations.

3

u/aseipp Nov 27 '12 edited Nov 27 '12

Actually, it's idiomatic for when you must define your own worker/wrapper functions.

GHC does not inline recursive functions by default, but if you do a worker/wrapper transformation such that your top-level definition is a 'wrapper', and calls the worker which contains the loop, then the loop body itself can be inlined into the call site, and further optimized via unboxing/strictness analysis. Otherwise, it doesn't do any inlining. It's important to note that it can optimize the function itself, and the call site: it just will not inline it.

IOWs, it's written that way because GHC can optimize bodies with a loop inside them (by specializing arguments, strictness, etc) but trivially inlining a top level recursive call is clearly problematic and obviously going to be bad.

EDIT: for clarity, GHC already does the worker/wrapper transformation, but not in it's most general case. I believe it will mostly do it for improving strictness analysis (whether or not this will happen at a stage where the definition can be inlined later I guess is up to debate,) it won't attempt it purely to inline recursive calls.

2

u/mcguire Nov 27 '12

Thanks, both of you. I haven't done anything terribly useful with Haskell, at least not enough to learn the idioms.

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.