Fibonacci sequence in Ruby (recursion)
Here is something I came up with, I find this more straight forward.
def fib(n)
n.times.each_with_object([0,1]) { |num, obj| obj << obj[-2] + obj[-1] }
end
fib(10)
Try this
def fibonacci( n )
return n if ( 0..1 ).include? n
( fibonacci( n - 1 ) + fibonacci( n - 2 ) )
end
puts fibonacci( 5 )
# => 5
check this post too Fibonacci One-Liner
and more .. https://web.archive.org/web/20120427224512/http://en.literateprograms.org/Fibonacci_numbers_(Ruby)
You have now been bombarded with many solutions :)
regarding problem in ur solution
you should return n
if its 0
or 1
and add
last two numbers not last and next
New Modified version
def fibonacci( n )
return n if n <= 1
fibonacci( n - 1 ) + fibonacci( n - 2 )
end
puts fibonacci( 10 )
# => 55
One liner
def fibonacci(n)
n <= 1 ? n : fibonacci( n - 1 ) + fibonacci( n - 2 )
end
puts fibonacci( 10 )
# => 55
This approach is fast and makes use of memoization:
fib = Hash.new {|hash, key| hash[key] = key < 2 ? key : hash[key-1] + hash[key-2] }
fib[123] # => 22698374052006863956975682
In case you're wondering about how this hash initialization works read here:
https://ruby-doc.org/core/Hash.html#method-c-new
Linear
module Fib
def self.compute(index)
first, second = 0, 1
index.times do
first, second = second, first + second
end
first
end
end
Recursive with caching
module Fib
@@mem = {}
def self.compute(index)
return index if index <= 1
@@mem[index] ||= compute(index-1) + compute(index-2)
end
end
Closure
module Fib
def self.compute(index)
f = fibonacci
index.times { f.call }
f.call
end
def self.fibonacci
first, second = 1, 0
Proc.new {
first, second = second, first + second
first
}
end
end
None of these solutions will crash your system if you call Fib.compute(256)