From: Mikael Brockman <phubuh@...>
Date: 2004-05-15T06:05:24+09:00
Subject: Re: Recursion depth

Kevin Bullock <kbullock@ringworld.org> writes:

> Take the following two recursive implementations of Euclid's
> algorithm, the first in Guile, the second in Ruby:
> 
> (define (euclid m n)
> 	(if (= n 0)
> 		m
> 		(euclid n (remainder m n))))
> 
> def euclid(m, n)
>      if n == 0 then m
>      else euclid(n, m % n)
>      end
> end
> 
> The results of running each function (which are both the same) are as
> follows:
> 
> guile> (euclid (random (expt 10 1000)) (random (expt 10 1000)))
> 
> irb(main):001:0> euclid(rand(10**1000),rand(10**1000))
> SystemStackError: stack level too deep
> 
> Why is it that guile can handle such recursion but Ruby can't? Is it
> that guile is implemented with iterative recursion in mind, and so
> optimizes for it better?
> 
> Pacem in terris / Mir / Shanti / Salaam / Heiwa
> Kevin R. Bullock

If you run that algorithm in your head, you'll notice that even though
there's lots of recursion going on, you don't have to remember more and
more stuff.  There's just two numbers to keep track of: m and n.

Scheme realizes that.  Just like you, it uses a constant amount of
memory.  It doesn't remember more and more stuff; in effect, the
recursive call is transformed into a GOTO.  Every Scheme is required by
law -- err, by the R5RS -- to perform this optimization.  Loops in
Scheme are very commonly written like this:

  (define (call-infinitely-many-times k)
    (k)
    (call-infinitely-many-times k))

and it'd be a darn shame to limit infinity to some number proportional
to the stack size.

Ruby, on the other hand, doesn't realize that.  But you can easily
rewrite your function into this:

  def euclid(m, n)
    while n != 0
      m, n = n, m % n
    end
    m
  end

That'll happily keep running forever.  For lots of functions that are
recursive in this way (tail-recursive), it's really easy to rewrite it
as a loop.  Tail recursion is more elegant in many (most?) cases,
though, and boy do the Schemers care about that.  Admittedly, there are
some cases when manually optimizing tail calls is really tedious, and
it'd be great if Rite did it automatically, but I don't think it's that
big of a deal.