From: Lars Christensen <larsch@...>
Date: 2001-09-22T00:08:59+09:00
Subject: [ruby-talk:21492] Re: SV:  Re: Ruby/objects book in style of The Little Lisper

On Fri, 21 Sep 2001, Mikkel Damsgaard wrote:

> Hey! Ruby is proper tail recursive, so since the recursive
> factorial is much easier to understand and runs as fast, it
> is a nice starting example. It would be cool to get back to it
> later to explain tail recursiveness.

Is it?

The simple approach:

def fact(n)
  if n == 1
    1
  else
    n * fact(n-1)
  end
end

... cannot be tail recusive because the multiplication is done after
recursion. This version is a bit slower than the Kevin Smith's imperative
approach.

Rewriting the method so that it can be tail recursive:

def fact(n, m = 1)
  return m if n == 1
  fact(n-1, n * m)
end

... is even slower (more than 25% slower than the imperative solution).

And finally, Ruby fails at recursive level five-thousand-something,
reporting, "Stack level too deep" :-)

-- 
Lars Christensen, larsch@cs.auc.dk