I'm trying to implement the following function, but it keeps giving me the stack level too deep (SystemStackError) error.
Any ideas what the problem might be ?
def fibonacci( n )
[ n ] if ( 0..1 ).include? n
( fibonacci( n - 1 ) + fibonacci( n - 2 ) ) if n > 1
end
puts fibonacci( 5 )
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
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)
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:
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)
This is not the way you calculate fibonacci, you are creating huge recursive tree which will fail for relatively small ns. I suggest you do something like this:
def fib_r(a, b, n)
n == 0 ? a : fib_r(b, a + b, n - 1)
end
def fib(n)
fib_r(0, 1, n)
end
p (0..100).map{ |n| fib(n) }
Recursion's very slow, here's a faster way
a = []; a[0] = 1; a[1] = 1
i = 1
while i < 1000000
a[i+1] = (a[i] + a[i-1])%1000000007
i += 1
end
puts a[n]
It's O(1), however you could use matrix exponentiation, here's one of mine's implementation, but it's in java => http://pastebin.com/DgbekCJM, but matrix exp.'s O(8logn) .Here's a much faster algorithm, called fast doubling. Here's a java implementation of fast doubling.
class FD {
static int mod = 1000000007;
static long fastDoubling(int n) {
if(n <= 2) return 1;
int k = n/2;
long a = fastDoubling(k+1);
long b = fastDoubling(k);
if(n%2 == 1) return (a*a + b*b)%mod;
else return (b*(2*a - b))%mod;
}
Yet, using karatsuba multiplication, both matrix exp. and fast doubling becomes much faster, yet fast doubling beats matrix exp. by a constant factor, well i didn't want to be very thorough here. But i recently did a lot of research on fibonacci numbers and i want my research to be of use to anyone willing to learn, ;).
This may help you.
def fib_upto(max)
i1, i2 = 1, 1
while i1 <= max
yield i1
i1, i2 = i2, i1+i2
end
end
fib_upto(5) {|f| print f, " "}
i think this is pretty easy:
def fibo(n) a=0 b=1 for i in 0..n c=a+b print "#{c} " a=b b=c end
end
We can perform list fibo series using below algorithm
def fibo(n)
n <= 2 ? 1 : fibo(n-1) + fibo(n-2)
end
We can generate series like below
p (1..10).map{|x| fibo(x)}
below is the output of this
=> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
Try this oneliner
def fib (n)
n == 0 || n == 1 ? n : fib(n-2) + fib(n-1)
end
print fib(16)
Output: 987
PHI = 1.6180339887498959
TAU = 0.5004471413430931
def fibonacci(n)
(PHI**n + TAU).to_i
end
You don't need recursion.
fastest and smallest in lines solution:
fiby = ->(n, prev, i, count, selfy) {
i < count ? (selfy.call n + prev, n, i + 1, count, selfy) : (puts n)
}
fiby.call 0, 1, 0, 1000, fiby
functional selfie pattern :)
1) Example, where max element < 100
def fibonachi_to(max_value)
fib = [0, 1]
loop do
value = fib[-1] + fib[-2]
break if value >= max_value
fib << value
end
fib
end
puts fibonachi_to(100)
Output:
0
1
1
2
3
5
8
13
21
34
55
89
2) Example, where 10 elements
def fibonachi_of(numbers)
fib = [0, 1]
(2..numbers-1).each { fib << fib[-1] + fib[-2] }
fib
end
puts fibonachi_of(10)
Output:
0
1
1
2
3
5
8
13
21
34
a = [1, 1]
while(a.length < max) do a << a.last(2).inject(:+) end
This will populate a with the series. (You will have to consider the case when max < 2)
If only the nth element is required, You could use Hash.new
fib = Hash.new {|hsh, i| hsh[i] = fib[i-2] + fib[i-1]}.update(0 => 0, 1 => 1)
fib[10]
# => 55
Here is a more concise solution that builds a lookup table:
fibonacci = Hash.new do |hash, key|
if key <= 1
hash[key] = key
else
hash[key] = hash[key - 1] + hash[key - 2]
end
end
fibonacci[10]
# => 55
fibonacci
# => {1=>1, 0=>0, 2=>1, 3=>2, 4=>3, 5=>5, 6=>8, 7=>13, 8=>21, 9=>34, 10=>55}
This is the snippet that I used to solve a programming challenge at URI Online Judge, hope it helps.
def fib(n)
if n == 1
puts 0
else
fib = [0,1]
(n-2).times do
fib << fib[-1] + fib[-2]
end
puts fib.join(' ')
end
end
fib(45)
An it outputs
# => 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733
Joining the Fibonacci train:
Regular:
def fib(num)
return num if (num < 2) else fib(num-1) + fib(num-2)
end
With caching:
module Fib
@fibs = [0,1]
def self.calc(num)
return num if (num < 2) else @fibs[num] ||= self.calc(num-1) + self.calc(num-2)
end
end
yet another ;)
def fib(n)
f = Math.sqrt(5)
((((1+f)/2)**n - ((1-f)/2)**n)/f).to_i
end
will be convenient to add some caching as well
def fibonacci
@fibonacci ||= Hash.new {|h,k| h[k] = fib k }
end
so we'll be able to get it like
fibonacci[3] #=> 2
fibonacci[10] #=> 55
fibonacci[40] #=> 102334155
fibonacci #=> {3=>2, 10=>55, 40=>102334155}
If you want to write the fastest functonal algorithem for fib, it will not be recursive. This is one of the few times were the functional way to write a solution is slower. Because the stack repeats its self if you use somethingn like
fibonacci( n - 1 ) + fibonacci( n - 2 )
eventually n-1 and n-2 will create the same number thus repeats will be made in the calculation. The fastest way to to this is iteratvily
def fib(num)
# first 5 in the sequence 0,1,1,2,3
fib1 = 1 #3
fib2 = 2 #4
i = 5 #start at 5 or 4 depending on wheather you want to include 0 as the first number
while i <= num
temp = fib2
fib2 = fib2 + fib1
fib1 = temp
i += 1
end
p fib2
end
fib(500)
Another approach of calculating fibonacci numbers taking the advantage of memoization:
$FIB_ARRAY = [0,1]
def fib(n)
return n if $FIB_ARRAY.include? n
($FIB_ARRAY[n-1] ||= fib(n-1)) + ($FIB_ARRAY[n-2] ||= fib(n-2))
end
This ensures that each fibonacci number is being calculated only once reducing the number of calls to fib method greatly.
Someone asked me something similar today but he wanted to get an array with fibonacci sequence for a given number. For instance,
fibo(5) => [0, 1, 1, 2, 3, 5]
fibo(8) => [0, 1, 1, 2, 3, 5, 8]
fibo(13) => [0, 1, 1, 2, 3, 5, 8, 13]
# And so on...
Here's my solution. It's not using recursion tho. Just one more solution if you're looking for something similar :P
def fibo(n)
seed = [0, 1]
n.zero? ? [0] : seed.each{|i| i + seed[-1] > n ? seed : seed.push(i + seed[-1])}
end
Here is one in Scala:
object Fib {
def fib(n: Int) {
var a = 1: Int
var b = 0: Int
var i = 0: Int
var f = 0: Int
while(i < n) {
println(s"f(${i+1}) -> $f")
f = a+b
a = b
b = f
i += 1
}
}
def main(args: Array[String]) {
fib(10)
}
}
I think this is the best answer, which was a response from another SO post asking a similar question.
The accepted answer from PriteshJ here uses naive fibonacci recursion, which is fine, but becomes extremely slow once you get past the 40th or so element. It's much faster if you cache / memoize the previous values and passing them along as you recursively iterate.
It's been a while, but you can write a fairly elegant and simple one line function:
def fib(n)
n > 1 ? fib(n-1) + fib(n-2) : n
end
A nice little intro to Ruby Fiber -
def fibs x, y
Fiber.new do
while true do
Fiber.yield x
x, y = y, x + y
end
end
end
Above we create an infinite stream of fibs numbers, computed in a very efficient manner. One does not simply puts an infinite stream, so we must write a small function to collect a finite amount of items from our stream, take -
def take t, n
r = []
while n > 0 do
n -= 1
r << t.resume
end
r
end
Finally let's see the first 100 numbers in the sequence, starting with 0 and 1 -
puts (take (fibs 0, 1), 100)
0
1
1
2
3
5
8
13
21
34
55
.
.
.
31940434634990099905
51680708854858323072
83621143489848422977
135301852344706746049
218922995834555169026
This one uses memoization and recursion:
def fib(num, memo={})
return num if num <= 1
if memo[num]
return memo[num]
else
memo[num] = fib(num - 2, memo) + fib(num - 1, memo)
end
end
Don't use recursion because the stack accumulates and you'll hit a limit at some point where the computer can't handle any more. That's the stack level too deep (SystemStackError) you're seeing. Use matrix exponentiation instead:
def fib(n)
(Matrix[[1,1],[1,0]] ** n)[1,0]
end
fib(1_000_000) #this is too much for a recursive version
