21

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 )
1
  • 4
    The recursive calls in your code will be made no matter what, since the [n] if ..., while evaluating to a value, will not abort the method execution.
    – waldrumpus
    Aug 29, 2012 at 13:13

27 Answers 27

46

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
8
  • @Maputo you are not returning n when it matches so the loop run and run and runs until the stack is tooo deep :) Aug 29, 2012 at 13:14
  • It works now, thank you. And thank you for the clarification. I didn't realize at first that return is actually supposed to end the recursion.
    – Maputo
    Aug 29, 2012 at 13:16
  • Is if n > 1 redundant if you are returning before that based on (0..1).include? n?
    – Toby
    Mar 13, 2013 at 11:24
  • @Toby great catch I missed it completely :) Mar 13, 2013 at 20:01
  • @toby thanks for pointing it, is was a great exercise to go back to basics, have learnt more ruby to re-factor it now :) Mar 13, 2013 at 20:10
19

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)
4
  • 1
    without side effects: 10.times.reduce([0,1]){|memo, num| memo + [memo[-2] + memo[-1]]} Jul 22, 2014 at 7:41
  • @TylerGillies your method is way slower
    – OlehZiniak
    Dec 28, 2015 at 14:22
  • The issue here is that while this answer might work, it is not recursive.
    – jonlink
    Feb 25, 2017 at 1:25
  • The return value seems a bit unexpected. If I send fib(5), I am either expecting to receive the fibonacci number at index 5 or perhaps the first 5 fibonacci numbers, this answer gives neither. fib 5 => [0, 1, 1, 2, 3, 5, 8] Mar 23, 2019 at 16:50
15

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

13

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)

2
  • Can you explain the recursive solution?
    – Al V
    Aug 29, 2016 at 6:11
  • What is the point of the closure solution ? Seems to me like it is an iterative solution with just some weird abstraction.. Or maybe you wanted to showcase some case of an iterator ? Apart from that and some more information, this answer is by far the best IMHO
    – Ulysse BN
    Nov 18, 2021 at 13:18
11

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) }
1
  • Yes, and thank you for pointing that out. I figured that it might be problematic for larger n's. I implemented it in loops, but this solution of yours is really enlightening.
    – Maputo
    Aug 30, 2012 at 23:38
5

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

4

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

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
2
  • You need to explain your solution
    – Yulia V
    Dec 6, 2014 at 19:59
  • parameter will accept the length of series that you want to see. and when you call the method will print out the total fibonacci series.if input is 5 then it will print 0,1,1,2,3 etc. Dec 7, 2014 at 16:41
4

Try this oneliner

def fib (n)
    n == 0 || n == 1 ? n : fib(n-2) + fib(n-1)
end
print fib(16)

Output: 987

4

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] 
4
PHI = 1.6180339887498959
TAU = 0.5004471413430931

def fibonacci(n)
  (PHI**n + TAU).to_i
end

You don't need recursion.

4
  • This says that 2 + 3 is 4 though 😅
    – Sam Soffes
    May 11, 2020 at 23:24
  • Yeah, floating point issues... Simply replace to_i by round.
    – iblue
    May 27, 2020 at 22:08
  • With to_i, it produces 2, 3, 4, 7. With round, it produces 2, 3, 5, 7. Both miss 8.
    – Sam Soffes
    Jun 3, 2020 at 17:51
  • Indeed you don't. But in CS you should know that floating point issues are going to come your way. The solution provided by Mike Belyakov below is much more suited. stackoverflow.com/a/55948718/476906 Jul 6, 2020 at 7:04
3

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

3

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

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}
2

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
2

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
2

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}
1

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

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.

1

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
1

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)
  }
}
1

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.

1

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
2
  • Simple, yes, but certainly not elegant. What happens when I call fib(1000)?
    – ymbirtt
    Feb 23, 2017 at 14:40
  • It has been quite some time since I actually logged in, but we can add caching as one of the other answers does: cache = Hash.new def fib(n, cache) n > 1 ? cache[n] ||= fib(n-1, cache) + fib(n-2, cache) : n end fib(1000, cache) => big number You'll still get stack level too deep with very large numbers (> 5000) unless you build up the cache incrementally. The recursive solution is not the most efficient, iteration from 0 to n with caching would be faster. May 1, 2018 at 14:41
1

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
1

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
1

Use matrix exponentiation:

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.