Recursion depth

[Kevin Bullock]

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

 

[Mikael Brockman]

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.

 

[Robert Klemme]

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?

Yes. Stack size limitation is a frequently seen problem with recursive
functions in Ruby. You can change the stack size though. Unforntunately I
don't have the idiom at hand...

Personally I found, that often the iterative solution is better in Ruby
although it lacks the beauty and simplicity of recursion.

Regards

robert

 

[Ceri Storey]

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?

In scheme, iteration is almost always defined as tail-recursion. Ergo,
the interpreter / compiler must be able to transform tail-calls into a
goto-like statement, so instead of pushing a new stack frame and then
calling the function, the current stack frame is replaced with that of
the called function.

Sadly, ruby currently doesn't implement this, although I'd expect it'd
be one of those features ear-marked for the RITE VM.

 

[Kevin Bullock]

In scheme, iteration is almost always defined as tail-recursion. Ergo,
the interpreter / compiler must be able to transform tail-calls into a
goto-like statement, so instead of pushing a new stack frame and then
calling the function, the current stack frame is replaced with that of
the called function.

Sadly, ruby currently doesn't implement this, although I'd expect it'd
be one of those features ear-marked for the RITE VM.

Thanks all. That's about what I expected. It seems as though optimizing
tail recursion is something that Ruby ought to do, given that it draws
so much other inspiration from functional languages.

Pacem in terris / Mir / Shanti / Salaam / Heiwa
Kevin R. Bullock