Asp Forum - Recursion and Ruby

Glenn Cadman

7/13/2006 7:13:00 AM

As a practice to learn ruby I tried to create a recursive program
(Fibonacci sequence), as a step up from "hello world", but I get a stack
level too deap error, any ideas what I am doing wrong?

-----------------

def fib ( n )
if n == 0
return 0
elseif n == 1
return 1
else
return fib(n-1) + fib(n-2)
end
end

0.upto(30) { |i| puts "The #{i} Fibonacci number is #{fib(i)}"
}

--------------
ruby test.rb
The 0 Fibonacci number is 0
test.rb:7:in `fib': stack level too deep (SystemStackError)
from test.rb:7:in `fib'
from test.rb:7:in `fib'
from test.rb:11
from test.rb:11
pstyovm010:/home/glenn#
for recursion

--
Posted via http://www.ruby-....

31 Answers

Elliot Temple

7/13/2006 7:21:00 AM

On Jul 13, 2006, at 12:13 AM, Glenn Cadman wrote:

> def fib ( n )
> if n == 0
> return 0
> elseif n == 1
> return 1
> else
> return fib(n-1) + fib(n-2)
> end
> end

You have a typo. it is elsif not elseif.

elseif is just treated like a method call. it doesn't exist, but that
error didn't come up because it was never reached. 0 gets returned
first in that branch. otherwise it goes straight to the else clause.

-- Elliot Temple
http://www.cur...

Peña, Botp

7/13/2006 7:24:00 AM

fr glenn:
# def fib ( n )
# if n == 0
# return 0
# elseif n == 1

^^^^ ruby wants "elsif" without the "e" there

been hit by this always. hope ruby would also allow "elseif" in future..

Glenn Cadman

7/13/2006 8:22:00 AM

Dear Elliot, PeÃ±a

Thanks for that, I was completely mesmerized by the "stack level too
deep" (recursion problem) to even consider that I had made a basic
typo!!!

--
Posted via http://www.ruby-....

Erik Veenstra

7/13/2006 8:57:00 AM

You could use "case" as well (see version 2). It's faster.
Using an ordinary if..else (without the elsif part) is faster
(see version 3). And version 4 is once again faster.

4 is faster than 3 is faster than 2 is faster than 1...

gegroet,
Erik V. - http://www.erikve...

----------------------------------------------------------------

Version 1 100,0%
Version 2 90,3%
Version 3 72,7%
Version 4 70,2%

----------------------------------------------------------------

# VERSION 1

def fib(n)
if n == 0
return 0
elsif n == 1
return 1
else
return fib(n-1) + fib(n-2)
end
end

0.upto(30){|i| puts "The #{i} Fibonacci number is #{fib(i)}"}

# VERSION 2

def fib(n)
case n
when 0
1
when 1
1
else
fib(n-1) + fib(n-2)
end
end

0.upto(30){|i| puts "The #{i} Fibonacci number is #{fib(i)}"}

# VERSION 3

def fib(n)
if n<=1
1
else
fib(n-1) + fib(n-2)
end
end

0.upto(30){|i| puts "The #{i} Fibonacci number is #{fib(i)}"}

# VERSION 4

def fib(n)
n<=1 ? 1 : fib(n-1) + fib(n-2)
end

0.upto(30){|i| puts "The #{i} Fibonacci number is #{fib(i)}"}

----------------------------------------------------------------

Erik Veenstra

7/13/2006 9:01:00 AM

Only the lambda version (versions 5) is much slower. Why is the
lambda version so much slower? I like the lambda version!

gegroet,
Erik V. - http://www.erikve...

----------------------------------------------------------------

Version 5 195,6%

----------------------------------------------------------------

# VERSION 5

fib = lambda{|n| n<=1 ? 1 : fib[n-1] + fib[n-2]}

0.upto(30){|i| puts "The #{i} Fibonacci number is #{fib[i]}"}

----------------------------------------------------------------

Dominik Bathon

7/13/2006 10:12:00 AM

On Thu, 13 Jul 2006 10:57:29 +0200, Erik Veenstra <erikveen@gmail.com>
wrote:

> You could use "case" as well (see version 2). It's faster.
> Using an ordinary if..else (without the elsif part) is faster
> (see version 3). And version 4 is once again faster.
>
> 4 is faster than 3 is faster than 2 is faster than 1...
>
> gegroet,
> Erik V. - http://www.erikve...
>
> ----------------------------------------------------------------
>
> Version 1 100,0%
> Version 2 90,3%
> Version 3 72,7%
> Version 4 70,2%
>
> ----------------------------------------------------------------

Actually version 3 and version 4 are exactly equivalent for Ruby, it
parses them both as NODE_IF:

>> pp "if a; b; else; c; end".parse_to_nodes.transform
[:if,
{:body=>[:vcall, {:mid=>:b}],
:else=>[:vcall, {:mid=>:c}],
:cond=>[:vcall, {:mid=>:a}]}]
=> nil
>> pp "a ? b : c".parse_to_nodes.transform
[:if,
{:body=>[:vcall, {:mid=>:b}],
:else=>[:vcall, {:mid=>:c}],
:cond=>[:vcall, {:mid=>:a}]}]
=> nil

Dominik

Daniel Martin

7/13/2006 1:06:00 PM

"Erik Veenstra" <erikveen@gmail.com> writes:

> You could use "case" as well (see version 2). It's faster.
> Using an ordinary if..else (without the elsif part) is faster
> (see version 3). And version 4 is once again faster.
>
> 4 is faster than 3 is faster than 2 is faster than 1...

All of these suffer from the problem that they make approximately fib(n)
function calls to compute fib(n). Why not remember the value of
fib(n) the ruby way, with a Hash that computes it naturally?

$fib = Hash.new{|h,k| h[k] = h[k-2] + h[k-1]}
$fib[0] = 0
$fib[1] = 1

def fib(n)
$fib[n]
end

This will be faster, and O(n), rather than O(fib(n)). Also note that
the base cases of 0 and 1 are handled simply and declaratively without
messing up the main body of the code.

(Of course, now someone will respond with one of the O(log(n))
algorithms for computing fib(n))

Erik Veenstra

7/13/2006 1:19:00 PM

> Try CachedProc

I could easily implement a cache myself, even a cleaner one
(see below), but that's not my point. My point is: Why is a
lambda call much slower then a method call?

gegroet,
Erik V. - http://www.erikve...

----------------------------------------------------------------

# Without cache.

fib = lambda{|n| n<=1 ? 1 : fib[n-1] + fib[n-2]}

0.upto(30){|i| puts "The #{i} Fibonacci number is #{fib[i]}"}

----------------------------------------------------------------

# With cache.

fib = lambda{|n| n<=1 ? 1 : fib[n-1] + fib[n-2]}

cache = lambda{|f| h={} ; lambda{|*args| h[*args] ||= f[*args]}}
fib = cache[fib]

0.upto(30){|i| puts "The #{i} Fibonacci number is #{fib[i]}"}

----------------------------------------------------------------

Erik Veenstra

7/13/2006 1:36:00 PM

> > ----------------------------------------------------------------
> >
> > Version 1 100,0%
> > Version 2 90,3%
> > Version 3 72,7%
> > Version 4 70,2%
> >
> > ----------------------------------------------------------------
>
> Actually version 3 and version 4 are exactly equivalent for
> Ruby, it parses them both as NODE_IF:

Well, _finally_ the AST is the same. But somehow, it's
slower... Maybe the translation from source/syntax to AST is
slower?

The numbers don't lie. They are averages of 3 test runs, with a
standard deviation of almost zero. (see below for the full
results.)

Oh, by the way, but you've probably already figured it out: The
number is the percentage of time Version 1 needed to complete.

gegroet,
Erik V. - http://www.erikve...

----------------------------------------------------------------

VERSION PERC AVE RUN1 RUN2 RUN3 DESCRIPTION
Version 1 100,0% 10,154 10,174 10,214 10,181
if..elsif..else..end
Version 2 90,3% 9,183 9,236 9,173 9,197
case..when..when..else..end
Version 3 72,7% 7,360 7,390 7,440 7,397 if..else..end
Version 4 70,2% 7,110 7,170 7,160 7,147 ..?..:..
Version 5 195,6% 19,868 20,068 19,808 19,915 lambda with
..?..:..

----------------------------------------------------------------

Erik Veenstra

7/13/2006 2:03:00 PM

> VERSION PERC AVE RUN1 RUN2 RUN3 DESCRIPTION

Oops... Wrong headers...

VERSION PERC RUN1 RUN2 RUN3 AVE DESCRIPTION
Version 1 100,0% 10,154 10,174 10,214 10,181
if..elsif..else..end
Version 2 90,3% 9,183 9,236 9,173 9,197
case..when..when..else..end
Version 3 72,7% 7,360 7,390 7,440 7,397
if..else..end
Version 4 70,2% 7,110 7,170 7,160 7,147 ..?..:..
Version 5 195,6% 19,868 20,068 19,808 19,915 lambda with
..?..:..

comp.lang.ruby

Recursion and Ruby

Glenn Cadman

Elliot Temple

Peña, Botp

Glenn Cadman

Erik Veenstra

Erik Veenstra

Dominik Bathon

Daniel Martin

Erik Veenstra

Erik Veenstra

Erik Veenstra

x Login to ForumsZone