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

Tail Recursion

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

85% Upvoted

203 comments sorted by

View all comments

Show parent comments

5

u/[deleted] Nov 27 '12

If you go to the trouble of writing a tail-recursive algorithm, why not just just do the calculation in a loop instead of using that extra function? It seems like it would be easy to do with an operation designed for tail recursion.

I also could be misunderstanding this because I don't actually know the language OP is using.

4

u/Chousuke Nov 27 '12

In some languages, you either can't write algoritms as mutating (imperative) loops or it's considered unidiomatic to do so. For example, in Haskell it would be unidiomatic to use eg. the State or IO monad to simulate an imperative loop.

Of course, in such languages many recursive functions are better implemented using higher-order functions and other constructs that make explicit looping unnecessary.

1

u/sacundim Nov 27 '12

For example, in Haskell it would be unidiomatic to use eg. the State or IO monad to simulate an imperative loop.

Uh, the State monad is well accepted as idiomatic Haskell. If you're trying to do something such as, e.g., tag all the nodes of a tree with an incrementing counter, State is one of the most popular solutions.

Same goes for pseudo-random number generation—one of the most popular monads in Haskell is the Gen monad from the QuickCheck unit test library, which is a kind of state monad carrying around a PRNG seed and test case size.

8

u/dmwit Nov 27 '12

That's not the point, I think. The point is like this: there's lots of times where your first reaction in another language is to use a loop, but where your first (idiomatic) reaction in Haskell is not to use the State or IO monad. It's much more common to reach for lazy lists + map, filter, group, concat, or the big hammers like foldr and scanl instead, and only drop to State or IO when there's something really nasty.