Fibonacci sequence in Ruby (recursion)

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

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.

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)

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

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

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

[To see links please register here]

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

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)

This is not the way you calculate fibonacci, you are creating huge recursive tree which will fail for relatively small `n`s. 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) }