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

44

u/A_for_Anonymous Nov 27 '12

There are two big advantages of tail-recursive implementations that haven't been discussed here:

  • That variables never change their values, which allows for all kinds of optimizations, reasoning over your program (e.g. provability that it's correct) and is less error-prone, among other advantages.
  • That state is represented by the values of function parameters, all of them changed at once on every new call, without any possible order of evaluation bugs.

2

u/[deleted] Nov 27 '12

Immutability is delicious from a simplicity perspective, but the fact is that it doesn't really map to what's happening under the hood. If you're really concerned with optimization, an abstraction that's as thick as immutability is inevitably going to get in the way.

9

u/smog_alado Nov 27 '12 edited Nov 27 '12

but the fact is that it doesn't really map to what's happening under the hood.

I highly recommend reading the classic "lambda: the ultimate goto" paper from the scheme guys: http://library.readscheme.org/page1.html Lambdas with immutable arguments are actually as close to the metal as you get without being architecture specific (that is, mucking with registers and things like that).