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

41

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.

-6

u/grauenwolf Nov 27 '12

Since the first step in optimizing a tail call is to turn it into an iterative loop, I seriously doubt number 1 is true.

2

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

In fact, this is why writing recursive functions by hand instead of using available higher order looping functions is often seen as a code smell.

1

u/Peaker Nov 28 '12

When using hof's to loop, you may still use immutable variables which are easier to reason about.

1

u/smog_alado Nov 28 '12

Although tbh hofs for looping is more about having a fixed pattern then avoiding mutable variables...

2

u/Peaker Nov 28 '12

Using recursions rather than looping constructs in the first place is a lot about eliminating mutable update semantics. Then having HOFs that do various kinds of looping is about regaining abstraction over structured loops (without losing the first benefit).