Recursion and Ruby

[Glenn Cadman]

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

 

[Elliot Temple]

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.curi.us/blog/

 

[Peña, Botp]

ZnIgZ2xlbm46DQojIGRlZiBmaWIgKCBuICkNCiMgIGlmIG4gPT0gMA0KIyAgIHJldHVybiAwDQoj
ICBlbHNlaWYgbiA9PSAxDQoNCiAgIF5eXl4gIHJ1Ynkgd2FudHMgImVsc2lmIiB3aXRob3V0IHRo
ZSAiZSIgdGhlcmUNCg0KYmVlbiBoaXQgYnkgdGhpcyBhbHdheXMuIGhvcGUgcnVieSB3b3VsZCBh
bHNvIGFsbG93ICJlbHNlaWYiIGluIGZ1dHVyZS4uDQo=

 

[Glenn Cadman]

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

 

[Dominik Bathon]

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%

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

Actually version 3 and version 4 are exactly equivalent for Ruby, it
parses them both as NODE_IF:
[:if,
{:body=>[:vcall, {:mid=>:b}],
:else=>[:vcall, {:mid=>:c}],
:cond=>[:vcall, {:mid=>:a}]}]
=> nil[:if,
{:body=>[:vcall, {:mid=>:b}],
:else=>[:vcall, {:mid=>:c}],
:cond=>[:vcall, {:mid=>:a}]}]
=> nil


Dominik

 

[Daniel Martin]

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]

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

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

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

 

[Erik Veenstra]

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

 

[Dominik Bathon]

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:
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.
[: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

 

[Glenn Cadman]

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

Well whilst my orginal exercise was just to get recursion working in
ruby, I have to say this solution is very quick to calculate any result
and is recursive in a way that is quite "foriegn" to me. The problem for
me is that I find it difficult to understand what is happening in this
code. I would have though the stack would collapse due to referencing
something that is not defined yet. eg. h[k-2] for example in the intial
state of the $fib hash would not be found unless the k was 3 or 2. eg
$fib(30) would return "I dont have any thing to reference for h[30] =
h[28] + h[29], has h[28] and h[29] havent been defined.

BTW How would I then access $fib to puts an output of the sequence eg. 0
1 1 2 3 5 8 13 etc.

 

[Glenn Cadman]

BTW How would I then access $fib to puts an output of the sequence eg. 0
1 1 2 3 5 8 13 etc.

The best I could do was something like:

printf("Enter a number: ")
i = gets
puts "The #{i.to_i} Fibonacci number is #{fib(i.to_i)} "
0.upto(i.to_i){|k| printf(" #{$fib[k]}") }

 

[Martin DeMello]

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

Well whilst my orginal exercise was just to get recursion working in
ruby, I have to say this solution is very quick to calculate any result
and is recursive in a way that is quite "foriegn" to me. The problem for
me is that I find it difficult to understand what is happening in this
code. I would have though the stack would collapse due to referencing
something that is not defined yet. eg. h[k-2] for example in the intial
state of the $fib hash would not be found unless the k was 3 or 2. eg
$fib(30) would return "I dont have any thing to reference for h[30] =
h[28] + h[29], has h[28] and h[29] havent been defined.

The block form of Hash.new calls the block for every
nonexistent-hash-key access. So $fib[30] looks for the key 30, doesn't
find it, and calls the block instead, passing it $fib and 30. The
block tries to return h[29] + h[28], but since they don't exist
either, the calls to [] will again call the block, and so on.

martin

 

[Kroeger, Simon (ext)]

=20

From: Glenn Cadman
Sent: Friday, July 14, 2006 10:50 AM
=20

BTW How would I then access $fib to puts an output of the=20 sequence eg. 0=20
1 1 2 3 5 8 13 etc.

=20
The best I could do was something like:
=20
printf("Enter a number: ")
i =3D gets
puts "The #{i.to_i} Fibonacci number is #{fib(i.to_i)} "
0.upto(i.to_i){|k| printf(" #{$fib[k]}") }

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

print "Enter a number: "

i =3D gets.to_i

puts "The #{i} Fibonacci number is #{fib}"
puts (0..i).map{|k| fib[k]}.join(' ')

 

[Peña, Botp]

fr simon:
# puts (0..i).map{|k| fib[k]}.join(' ')

cool. only one puts speeds things up.

 

[Rob Biedenharn]

 

[Patrick Hurley]

When I am confused (which happens all too often), I like to "see" what
is happening. Below is the same algorithm with a slightly different
implementation (I used class variables rather than a global). I also
provided a simple accessor to the class variable.

Good Luck
pth

class Integer
@@fib = Hash.new do |h,k|
puts "Calculate fib[#{k}]"
h[k] = h[k-2] + h[k-1]
end

@@fib[0] = 0
@@fib[1] = 1

def fib
@@fib[self]
end

def self.fibs
@@fib
end
end

puts 10.fib
puts 7.fib.fib
p Integer.fibs

----- Output ------
Calculate fib[10]
Calculate fib[8]
Calculate fib[6]
Calculate fib[4]
Calculate fib[2]
Calculate fib[3]
Calculate fib[5]
Calculate fib[7]
Calculate fib[9]
55
Calculate fib[13]
Calculate fib[11]
Calculate fib[12]
233
{5=>5, 11=>89, 0=>0, 6=>8, 12=>144, 1=>1, 7=>13, 13=>233, 2=>1, 8=>21,
3=>2, 9=>34, 4=>3, 10=>55}

 

[Rob Biedenharn]

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

Well whilst my orginal exercise was just to get recursion working in
ruby, I have to say this solution is very quick to calculate any
result
and is recursive in a way that is quite "foriegn" to me. The
problem for
me is that I find it difficult to understand what is happening in this
code. I would have though the stack would collapse due to referencing
something that is not defined yet. eg. h[k-2] for example in the
intial
state of the $fib hash would not be found unless the k was 3 or 2. eg
$fib(30) would return "I dont have any thing to reference for h[30] =
h[28] + h[29], has h[28] and h[29] havent been defined.

BTW How would I then access $fib to puts an output of the sequence
eg. 0
1 1 2 3 5 8 13 etc.

(I hate when the email doesn't get through)

I first saw this Hash trick in a RubyQuiz solution. I've used it in
different ways since, but here's some amazing evidence as to it's power:

I ran the comparisons locally to try things out. Basically, you just
can't beat memoization with a Hash for something this simple (it's
just addition after all). I did adjust some of the implementations
so that they produced the same sequence: fib(0) = 0, fib(1) = 1, fib
(2) = 1, fib(3) = 2, etc. (Some of them had fib(0) == fib(1) == 1)


100.times { 0.upto(30) { |n| fib(n) } }
user system total real
fib1.rb: if 682.070000 1.850000 683.920000 (689.604829)
fib2.rb: case 631.260000 1.380000 632.640000 (636.994644)
fib3.rb: simple if 512.770000 0.860000 513.630000 (515.151776)
fib4.rb: simple ?: 498.760000 0.470000 499.230000 (499.626195)
fib6.rb: Hash 0.000000 0.000000 0.000000 ( 0.007612)
fib7.rb: formula 0.030000 0.000000 0.030000 ( 0.023598)
fib8.rb: BigMath 2.750000 0.010000 2.760000 ( 2.762493)

user system total real
fib1.rb: if 100.000 % 1.850000 683.920000 (689.604829)
fib2.rb: case 92.550 % 1.380000 632.640000 (636.994644)
fib3.rb: simple if 75.178 % 0.860000 513.630000 (515.151776)
fib4.rb: simple ?: 73.124 % 0.470000 499.230000 (499.626195)
fib6.rb: Hash 0.000 % 0.000000 0.000000 ( 0.007612)
fib7.rb: formula 0.004 % 0.000000 0.030000 ( 0.023598)
fib8.rb: BigMath 0.403 % 0.010000 2.760000 ( 2.762493)


Let's peel those fast ones apart a bit:

10_000.times { 0.upto(30) { |n| fib(n) } }
user system total real
fib6.rb: Hash 0.240000 0.000000 0.240000 ( 0.246511)
fib7.rb: formula 2.610000 0.010000 2.620000 ( 2.635959)
fib8.rb: BigMath 302.950000 0.810000 303.760000 (306.202394)


What about when the numbers get bigger? Does the formula start to
have an advantage?

1000.times { 0.upto(300) { |n| fib(n) } }
user system total real
fib6.rb: Hash 2.310000 0.010000 2.320000 ( 2.322534)
fib7.rb: formula 45.720000 0.090000 45.810000 ( 46.018314)

Uh, not really.


Let's see them all together again:

fib1.rb: if for 30: 832040
fib2.rb: case for 30: 832040
fib3.rb: simple if for 30: 832040
fib4.rb: simple ?: for 30: 832040
fib6.rb: Hash for 30: 832040
fib7.rb: formula for 30: 832040
fib8.rb: BigMath for 30: 832040
1000.times { 0.upto(30) { |n| fib(n) } }
user system total real
fib1.rb: if 6158.150000 3.740000 6161.890000 (6167.126104)
fib2.rb: case 5702.300000 5.630000 5707.930000 (5722.498983)
fib3.rb: simple if 4837.140000 3.320000 4840.460000 (4846.447905)
fib4.rb: simple ?: 4969.330000 5.540000 4974.870000 (4986.140834)
fib6.rb: Hash 0.020000 0.000000 0.020000 ( 0.021521)
fib7.rb: formula 0.240000 0.000000 0.240000 ( 0.245543)
fib8.rb: BigMath 27.740000 0.040000 27.780000 ( 27.828623)

==> fib.rb <==
require 'benchmark'
include Benchmark

require '../constantize.rb'

fibsto = ENV['FIBS_UPTO'] || 30
fibrep = ENV['FIB_REPTS'] || 1000

algorithms = [ ]
Dir.glob(ARGV.empty? ?
'fib[1-46-9].rb' :
ARGV.each { |p| Regexp.quote(p) }.unshift('{').push
('}').join(%{,})) do |f|

require f
mod = constantize(File.basename(f,'.rb').capitalize)
include mod
algorithms << Hash[ :description => "#{f}: #{mod.module_eval
{ description }}",
:alg => lambda { fibrep.times { 0.upto(fibsto)
{ |n| mod.fib(n) } } },
:fib => lambda { |n| mod.fib(n) }
]
end

algorithms.each do |a|
fibsto.upto(fibsto) do |n|
puts "#{a[:description]} for #{n}: #{a[:fib].call(n)}"
end
end

puts "#{fibrep}.times { 0.upto(#{fibsto}) { |n| fib(n) } }"
bm(1 + algorithms.inject(9) { |mx,h| mx<h[:description].length ? h
[:description].length : mx }) do |x|
algorithms.each do |a|
x.report(a[:description]) { a[:alg].call }
end
end

==> fib1.rb <==
# VERSION 1
module Fib1
def description; "if"; end

def self.fib(n)
# puts "#{File.basename(__FILE__,'.rb')}(#{n})"
if n == 0
return 0
elsif n == 1
return 1
else
return fib(n-1) + fib(n-2)
end
end
end

==> fib2.rb <==
# VERSION 2
module Fib2
def description; "case"; end

def self.fib(n)
# puts "#{File.basename(__FILE__,'.rb')}(#{n})"
case n
when 0
0
when 1
1
else
fib(n-1) + fib(n-2)
end
end
end

==> fib3.rb <==
# VERSION 3
module Fib3
def description; "simple if"; end

def self.fib(n)
# puts "#{File.basename(__FILE__,'.rb')}(#{n})"
if n<=1
n.zero? ? 0 : 1
else
fib(n-1) + fib(n-2)
end
end
end

==> fib4.rb <==
# VERSION 4
module Fib4
def description; "simple ?:"; end

def self.fib(n)
# puts "#{File.basename(__FILE__,'.rb')}(#{n})"
n<=1 ? (n.zero? ? 0 : 1) : fib(n-1) + fib(n-2)
end
end

==> fib5.rb <==
# Version 5
module Fib5
def description; "lambda"; end

fib = lambda{|n|
# puts "#{File.basename(__FILE__,'.rb')}(#{n})"
n<=1 ? (n.zero? ? 0 : 1) : fib[n-1] + fib[n-2]
}
end

==> fib6.rb <==
# Version 6
module Fib6
def description; "Hash"; end

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

def self.fib(n)
# puts "#{File.basename(__FILE__,'.rb')}(#{n})"
# puts "#{File.basename(__FILE__,'.rb')}(#{n}) => #{$fib[n]}" if
n == 30
$fib[n]
end
end

==> fib7.rb <==
# Version 7
# Weisstein, Eric W. "Binet's Fibonacci Number Formula." From
MathWorld--A Wolfram Web Resource.
# http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html

module Fib7
def description; "formula"; end

SQRT5 = Math.sqrt(5)
def self.fib(n)
# puts "#{File.basename(__FILE__,'.rb')}(#{n})"
(((1+SQRT5)**n - (1-SQRT5)**n)/(2**n * SQRT5)).round
end
end

==> fib8.rb <==
# Version 8
# Weisstein, Eric W. "Binet's Fibonacci Number Formula." From
MathWorld--A Wolfram Web Resource.
# http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html

require 'bigdecimal'
require 'bigdecimal/math'
include BigMath

module Fib8
def description; "BigMath"; end

SQRT5 = BigMath.sqrt(BigDecimal("5"),20)
def self.fib(n)
# puts "#{File.basename(__FILE__,'.rb')}(#{n})"
(((1+SQRT5)**n - (1-SQRT5)**n)/(2**n * SQRT5)).round.to_i
end
end

==> ../constantize.rb <==
# from Jim Weirich (based on email correspondence)
def constantize(camel_cased_word)
camel_cased_word.
sub(/^::/,'').
split("::").
inject(Object) { |scope, name| scope.const_get(name) }
end

==> timing.txt <==
user system total real
fib1.rb: if 682.070000 1.850000 683.920000 (689.604829)
fib2.rb: case 631.260000 1.380000 632.640000 (636.994644)
fib3.rb: simple if 512.770000 0.860000 513.630000 (515.151776)
fib4.rb: simple ?: 498.760000 0.470000 499.230000 (499.626195)
fib6.rb: Hash 0.000000 0.000000 0.000000 ( 0.007612)
fib7.rb: formula 0.030000 0.000000 0.030000 ( 0.023598)
fib8.rb: BigMath 2.750000 0.010000 2.760000 ( 2.762493)

user system total real
fib1.rb: if 100.000 % 1.850000 683.920000 (689.604829)
fib2.rb: case 92.550 % 1.380000 632.640000 (636.994644)
fib3.rb: simple if 75.178 % 0.860000 513.630000 (515.151776)
fib4.rb: simple ?: 73.124 % 0.470000 499.230000 (499.626195)
fib6.rb: Hash 0.000 % 0.000000 0.000000 ( 0.007612)
fib7.rb: formula 0.004 % 0.000000 0.030000 ( 0.023598)
fib8.rb: BigMath 0.403 % 0.010000 2.760000 ( 2.762493)

10_000.times
user system total real
fib6.rb: Hash 0.240000 0.000000 0.240000 ( 0.246511)
fib7.rb: formula 2.610000 0.010000 2.620000 ( 2.635959)
fib8.rb: BigMath 302.950000 0.810000 303.760000 (306.202394)

0.upto(300)
user system total real
fib6.rb: Hash 2.310000 0.010000 2.320000 ( 2.322534)
fib7.rb: formula 45.720000 0.090000 45.810000 ( 46.018314)

fib1.rb: if for 30: 832040
fib2.rb: case for 30: 832040
fib3.rb: simple if for 30: 832040
fib4.rb: simple ?: for 30: 832040
fib6.rb: Hash for 30: 832040
fib7.rb: formula for 30: 832040
fib8.rb: BigMath for 30: 832040
1000.times { 0.upto(30) { |n| fib(n) } }
user system total real
fib1.rb: if 6158.150000 3.740000 6161.890000 (6167.126104)
fib2.rb: case 5702.300000 5.630000 5707.930000 (5722.498983)
fib3.rb: simple if 4837.140000 3.320000 4840.460000 (4846.447905)
fib4.rb: simple ?: 4969.330000 5.540000 4974.870000 (4986.140834)
fib6.rb: Hash 0.020000 0.000000 0.020000 ( 0.021521)
fib7.rb: formula 0.240000 0.000000 0.240000 ( 0.245543)
fib8.rb: BigMath 27.740000 0.040000 27.780000 ( 27.828623)