Recursion and Ruby

Ruby
#1

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:infib’
from test.rb:7:in `fib’
from test.rb:11
from test.rb:11
pstyovm010:/home/glenn#
for recursion

#2

On Jul 13, 2006, at 12:13 AM, Glenn C. 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 T.

#3

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…

#4

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!!!

#5

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.erikveen.dds.nl/

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)}”}

#6

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.erikveen.dds.nl/

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]}”}

#7

Try CachedProc

class CachedProc
def initialize(&block)
@proc = block
@cache = Hash.new{|cache, args| cache[args] = @proc.call(*args) }
end

 def call(*args)
   @cache[args]
 end

 alias_method :[], :call

 def method_missing(name, *args, &block)
   @proc.send(name, *args, &block)
 end

end

def cached_proc(&block)
CachedProc.new(&block)
end

Daniel S. wrote that.

j`ey
http://www.eachmapinject.com

#8

On Thu, 13 Jul 2006 10:57:29 +0200, Erik V. [email protected]
wrote:

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

#9

On 7/13/06, Dominik B. [email protected] wrote:

On Thu, 13 Jul 2006 10:57:29 +0200, Erik V. [email protected]
wrote:
[SNIP]

It might be of interest to the OP to examine the recursive calls in the
original method
after typo correction :wink:

f(n) calss f(n-1) and f(n-2),
f(n-1) calls f(n-2) and f(n-3)
f(n-2): f(n-3) and f(n-4)
etc etc

In other words f(n-1) will redo almost all the work done in f(n-2)
In order to avoid this would it not be nice to have the result of f(n-2)
handy when computing f(n-1)?

I have attached an implementation of that and the not surprising
performance
gain (we are going from O(2**n) to O(n) after all :wink:
but did not paste it into the post so that OP can try to come up with
his/her own solution.

Cheers
Robert

–
Deux choses sont infinies : l’univers et la bêtise humaine ; en ce qui
concerne l’univers, je n’en ai pas acquis la certitude absolue.

  • Albert Einstein
#10

“Erik V.” [email protected] 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))

#11

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.erikveen.dds.nl/

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
…?..:…

#12

On 7/13/06, Erik V. [email protected] wrote:

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?

Sorry if I misplaced my reply, it was intended for OP and did not in any
way
concern what you have said or done, neither reply to your questions, yes
I
have definitely chosen the wrong message to reply.
Sorry for the confusion.
Cheers
Robert

#13

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.erikveen.dds.nl/

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]}”}

#14

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
…?..:…

#15

On Thu, 13 Jul 2006 15:35:33 +0200, Erik V. [email protected]
wrote:

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.)

Indeed you are right, I forgot the newline nodes:

pp <<code.parse_to_nodes.transform(:keep_newline_nodes => true)
if a
b
else
c
end
code
[:newline,
{:next=>
[:if,
{:body=>[:newline, {:next=>[:vcall, {:mid=>:b}]}],
:else=>[:newline, {:next=>[:vcall, {:mid=>:c}]}],
:cond=>[:vcall, {:mid=>:a}]}]}]
=> nil

vs.

pp “a ? b : c”.parse_to_nodes.transform(:keep_newline_nodes => true)
[:newline,
{:next=>
[:if,
{:body=>[:vcall, {:mid=>:b}],
:else=>[:vcall, {:mid=>:c}],
:cond=>[:vcall, {:mid=>:a}]}]}]
=> nil

The newline nodes are basically no-ops but they still slow things down a
bit.

In Ruby 1.9 there are no more newline nodes, so there it really is
equivalent.

Dominik

#16

http://rubynode.rubyforge.org/

#17

(stupid question): what have you used to parse the code and show the
nodes?

./alex

.w( the_mindstorm )p.

#18

Daniel M. [email protected] writes:

“Erik V.” [email protected] writes:

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

Given you have an reasonably exact approximation of the square root of
5,
this can be done O(1)…

#19

On 7/13/06, Christian N. [email protected] wrote:

Daniel M. [email protected] writes:

“Erik V.” [email protected] writes:

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

Given you have an reasonably exact approximation of the square root of 5,
this can be done O(1)…

I challange this, as there is no algorithm to compute c**n in O(1) it is
O(log n).

–

Christian N. [email protected] http://chneukirchen.org

–
Deux choses sont infinies : l’univers et la bêtise humaine ; en ce qui
concerne l’univers, je n’en ai pas acquis la certitude absolue.

  • Albert Einstein
#20

“Robert D.” [email protected] writes:

On 7/13/06, Christian N. [email protected] wrote:

Given you have an reasonably exact approximation of the square root of 5,
this can be done O(1)…

I challange this, as there is no algorithm to compute c**n in O(1) it is
O(log n).

OT, but…

http://mathforum.org/library/drmath/view/52686.html

-Doug