# Recursion and Ruby

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-forum.com/.

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

···

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

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

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

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

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-forum.com/.

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

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

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:

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

···

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

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

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 Schierbeck wrote that.

···

On 7/13/06, Erik Veenstra <erikveen@gmail.com> wrote:

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

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

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

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
but did not paste it into the post so that OP can try to come up with
his/her own solution.

Cheers
Robert

fibo.rb (625 Bytes)

···

On 7/13/06, Dominik Bathon <dbatml@gmx.de> wrote:

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

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

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

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

Daniel Martin <martin@snowplow.org> writes:

"Erik Veenstra" <erikveen@gmail.com> 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)...

···

--
Christian Neukirchen <chneukirchen@gmail.com> http://chneukirchen.org

Daniel Martin wrote:

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

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.

···

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

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

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

VERSION PERC AVE RUN1 RUN2 RUN3 DESCRIPTION

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

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

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

···

On Thu, 13 Jul 2006 15:35:33 +0200, Erik Veenstra <erikveen@gmail.com> wrote:

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

···

On 7/13/06, Christian Neukirchen <chneukirchen@gmail.com> wrote:

Daniel Martin <martin@snowplow.org> writes:

> "Erik Veenstra" <erikveen@gmail.com> 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)...

--

Christian Neukirchen <chneukirchen@gmail.com> 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

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]}") }

···

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

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

···

Daniel Martin wrote:
>
> \$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.