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
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
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...
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...
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?
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))
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.
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?
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 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?
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)
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
···
On 7/14/06, Glenn Cadman <glenn.cadman@gmail.com> wrote:
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.
