From: Robert Klemme <bob.news@...>
Date: 2004-05-15T06:13:51+09:00
Subject: Re: Recursion depth


"Kevin Bullock" <kbullock@ringworld.org> schrieb im Newsbeitrag
news:17C32102-A5E4-11D8-8488-000393BDB320@ringworld.org...
> 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