From: Johannes Friestad <johannes.friestad@...>
Date: 2005-12-17T06:03:42+09:00
Subject: Re: Ruby tail recursion

> I wouldn't really call it optimization (although I guess it is), it's more like implementing them in such a way that you get around the limitations of computer memory. (As opposed to just making them run faster or something.) It doesn't really have anything to do with efficiency in that sense.

I agree that it's not (just) optimization in the sense of 'runs
faster'. Without tail-recursion optimization there are things you
simply cannot do in a recursive  fashion.

A simple example is iterating over a collection.
For example, these two 'max' methods are equivalent, so which one you
prefer is mainly a matter of style preferences.

def each_max(elms)
  max=-Infinity
  elms.each {|x| max=x if x>max }
  max
end

def for_max(elms)
  max=-Infinity
  for elm in elms
      max=elm if elm>max
  end
  max
end

The tail recursive version,

def tailrec_max(arr, i=0, max=-Infinity)
  return max if i==arr.length
  tailrec_max(arr, i+1, (arr[i]>max ? arr[i] : max)
end

would be equivalent to the first two, and offer a third style, if Ruby
had tail optimization.
As it is, each element access adds another method call on the stack,
and the recursion does not bottom out before the end of the sequence,
so we will get an exception whenever there are more than 'stack-limit'
elements in the sequence. The limit is 1200 on my system.
1200 elements in a sequence is nothing - consider iterating over
characters in a string, or lines in a log file, it doesn't take much
to have 1200 characters or lines.
This makes recursive iteration in Ruby a curiosity that cannot be
actually used for very much.

> By the way, is there a particular reason why tail calls aren't implemented that way?
My guess is that it's not implemented simply because recursion isn't
used very much in Ruby. (It's the chicken and egg: Recursion won't be
generally viable until the optimization is in place.)

Although I can live without it, I'd like to see tail recursion
optimization in Ruby.
If it's up to debate, I'm voting yes :)


jf