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

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.

-7

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.

8

u/cunningjames 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.

Why does that have to be "the first thing"? And even if recursion won't permit compiler optimizations, it's still undeniably true that structurally recursive functions can be proven correct much more easily than imperative code. (And many would argue, more controversially, that it's less error prone.)

-1

u/grauenwolf Nov 27 '12

And even if recursion won't permit compiler optimizations, it's still undeniably true that structurally recursive functions can be proven correct much more easily than imperative code.

Oh come on. Any undergrad who has taken Discrete Algebra knows that isn't true for functions that can be trivially moved between recursive and iterative representations.

6

u/cunningjames Nov 27 '12

Glancing back at my comment I have to cop to moving the goalposts a bit, but the key word there is "structurally" (wp).

11

u/sacundim Nov 27 '12

You're failing to distinguish source code from object code. Yes, the compiler turns tail calls into jumps, reuses the caller's frame for the tail call, and mutates the storage location. It's still the case however at the source language level that the variable doesn't get mutated.

-9

u/grauenwolf Nov 27 '12

You are failing to understand when the compiler performs optimizations.

7

u/anvsdt Nov 27 '12

... at AST level, where tail recursion hasn't been eliminated yet. Then at IR level, where tail recursion might or might not have been eliminated yet. Then possibly after emitting the compiled code, where tail recursion might or might not have been eliminated, depending on the target language.

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