Tail recursion

ruby-talk
1

Greetings, Ruby hackers!

I have a small implementation question: does Ruby support tail
recursion optimisation a la Scheme? e.g, if I write the following:

  def factorial x
    fail if x < 1
    (x == 1) ? x : x * factorial(x - 1)
  end

Am I going to get at most one stack frame or zillions?

–Mirian

2

zillions, depending on x, I believe.

···

— Mirian Crzig Lennox mirian@cosmic.com wrote:

Greetings, Ruby hackers!

I have a small implementation question: does Ruby support tail
recursion optimisation a la Scheme? e.g, if I write the following:

def factorial x
  fail if x < 1
  (x == 1) ? x : x * factorial(x - 1)
end

Am I going to get at most one stack frame or zillions?

=====

Yahoo IM: michael_s_campbell

Do you Yahoo!?
HotJobs - Search new jobs daily now
http://hotjobs.yahoo.com/

3

Zillions, since your function isn’t tail recursive:

def fact-iter x, acc
fact-iter x-1, x * acc
end

def fact x
fact-itern x, 1
end

But even this gives you the zillion frames, since ruby doesn’t handle tail
recursion yet: from what I recall an experimental version exists.

– Nikodemus

···

On Thu, 7 Nov 2002, Mirian Crzig Lennox wrote:

def factorial x
  fail if x < 1
  (x == 1) ? x : x * factorial(x - 1)
end

Am I going to get at most one stack frame or zillions?

4

Hi,

···

In message “tail recursion” on 02/11/07, Mirian Crzig Lennox mirian@cosmic.com writes:

I have a small implementation question: does Ruby support tail
recursion optimisation a la Scheme?

No, not yet.

						matz.
5

Sorry, should have been, of course:

def fact-iter x, acc
if x == 0
acc
else
fact-iter x-1, x * acc
end
end

– Nikodemus

···

On Thu, 7 Nov 2002, Nikodemus Siivola wrote: