fibonacci.rb

require 'benchmark'

def it_fibonacci(n)
  fib_arr = [0,1]
  (2..(n.to_i) - 1).each do |x| 
    fib_arr << fib_arr[x-1] + fib_arr[x-2]
  end
  return fib_arr
end

def rec_fibonacci(n,arr=[])
  size = arr.length
  return arr if n == 0
  return rec_fibonacci(n-1,[0]) if arr.empty?
  return rec_fibonacci(n-1,[0,1]) if size == 1
  return rec_fibonacci(n-1,arr << (arr[size - 2] + arr[size - 1]))
  #return 1 if n == 1
  #return 0 if n < 0
  #return rec_fibonacci(n-1) + rec_fibonacci(n-2)
end

num = 10000

i_arr = it_fibonacci(num)
r_arr = rec_fibonacci(num)
puts i_arr.last
puts i_arr.length
puts "*****"
puts r_arr.last
puts r_arr.length
puts it_fibonacci(num) == rec_fibonacci(num)


=begin
num = 1000
Benchmark.bm do |x|
  x.report("Iterative") { it_fibonacci(num) }
  #x.report("Recursive") { rec_fibonacci(num) }
end
=end

@EmptyPond check this out on an explanation of recursion in imperative languages (like Ruby) https://stackoverflow.com/a/3093/334545

Also, from this blog post: https://www.leighhalliday.com/recursion-in-ruby

They made a good use of a lambda:

def recur_fib(n)
  acc = [0, 1]

  f = ->(acc) {
    if acc.size == n
      acc
    else
      cur, last = acc.last(2)
      f.(acc + [cur + last])
    end
  }

  f.(acc)
enda

Still, this code breaks at even a smaller number (5.6k I think). I think it's because of the limitations of Ruby though.