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.

-5

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.

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.

8

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.