Fibonacci sequence in Ruby (recursion)

Question

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 )

Answer 1

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

Answer 2

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)

Answer 3

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

Answer 4

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)