> On 2005.12.16 12:41, Mark Ericson <mark.ericson / gmail.com> wrote:
> > In another thread someone mentioned tail recursion doesn't work right
> > in Ruby.   Could someone please expand upon that?

Here's a somewhat lengthy explanation. Well, you asked for it :)

Here's a recursive method:

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

Assuming we call tailrec_max([1,2,3,4]), the stack will at some point
look like this:
- tairec_max([..], 4, 4) # i==arr.length, returns best=4
- tairec_max([..], 3, 3)
- tairec_max([..], 2, 2)
- tairec_max([..], 1, 1)
- tairec_max([..], 0, -Infinity) # initial call
The method calls itself a number of times, and each invocation is
pushed on the stack. The callers stay on the stack, each waiting for
the return of the method it called.

This is standard method invocation, and happens every time a method
calls another. The calls further down the stack are waiting for the
calls above to complete before continuing whatever they were doing.

But in some cases there is no point for a method to hang around..
The tailrec_max method is such a case: After it has called itself,
there is nothing more for it to do, except to wait for the return
value and pass it on unchanged. This is called tail recursion.

Some languages optimize for this: When the compiler or interpreter can
determine that the return value of the method is the same as the
return value of the next method call, it can in effect skip the
recursive calls and recompile the entire method into a for loop, which
is faster and does not run into stack size limitations no matter how
many recursive calls there are.

Here's a similar method that cannot be optimized:

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

The '+1' at the end means that this method needs the stack: It has to
wait for the return value in order to do the add.

Lisp does tail recursion optimization (in most implementations
anyway), Ruby doesn't.

It's not a matter of "not working right": Recursion, tail or no tail,
works just as well as any other method call in Ruby. Plenty of
languages thrive without optimizing for tail recursion, Java is one of
them.

The combination of a small stack and lack of tail recursion
optimization does mean that in Ruby, recursion can hardly replace
every other looping construct the way it can in Lisp. You'll be the
judge of whether that is important.

I think Lisp is a somewhat special case: The entire language grew out
of a recursive definition (called lambda calculus), and a Lisp dialect
I used at university had no 'for', no 'while' and no other data
structure than linked lists. Now in a language like that, it makes
sense to optimize for recursion ;)

jf