Ruby Fibonacci Algorithm

Fibonacci sequence in Ruby (recursion)

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

Ruby Fibonacci algorithm

Naive fibonacci makes a lot of repeat calculations - in fib(14) fib(4) is calculated many times.

You can add memoization to your algorithm to make it a lot faster:

def fib(n, memo = {})
  if n == 0 || n == 1
    return n
  end
  memo[n] ||= fib(n-1, memo) + fib(n-2, memo)
end
fib 14
# => 377
fib 24
# => 46368
fib 124
# => 36726740705505779255899443

Recursive Fibonacci in Ruby

The code can be simplified a bit by removing the temporary array variable. It's a distraction. It also only applies when num == 2; num < 2 will be handled by the other base cases. num < 0 is illegal and should be handled by an error check.

I've also added in an explicit return. Explicit returns make it very obvious what's being returned and that helps understand recursion. In this case it's seq. ("Explicit returns are evil!" all the Ruby style people cry. Tough cookies. Good style isn't an absolute.)

def fib_seq(num)
  # Error check
  if num < 0 then
      raise ArgumentError, "The number must be a positive integer"
  end

  # Terminating base cases
  return [] if num == 0
  return [0] if num == 1
  return [0,1] if num == 2 

  # Recursion
  seq = fib_seq(num - 1) 

  # The recursive function
  seq << seq[-2] + seq[-1]

  return seq
end

Now it's a bit clearer that return [0,1] if num == 2 is one of three base cases for the recursion. These are the terminating conditions which stops the recursion. But processing doesn't end there. The result isn't [0,1] because after that first return the stack has to unwind.

Let's walk through fib_seq(4).

fib_seq(4) calls fib_seq(3)
fib_seq(3) calls fib_seq(2)
fib_seq(2) returns `[0,1]`

We've reached the base case, now we need to unwind that stack of calls.

The call to fib_seq(3) picks up where it left off. seq returned from fib_seq(2) is [0,1]. It adds seq[-2] + seq[-1] onto the end and returns [0,1,1].

fib_seq(4) picks up where it left off. seq returned from fib_seq(3) is [0,1,1]. It adds seq[-2] + seq[-1] to the end and returns [0,1,1,2].

The stack is unwound, so we get back [0,1,1,2].

As you can see, the actual calculation happens backwards. f(n) = f(n-1) + f(n-2) and f(2) = [0,1]. It recurses down to f(2), the base case, then unwinds back up doing f(3) using the result of f(2), and f(4) using the result of f(3) and so on.

Fibonacci One-Liner

Inspired on Alex's answer:

# Ruby 1.8.7
f = lambda { |x| x < 2 ? x : f.call(x-1) + f.call(x-2) }
puts f.call(6)   #=> 8

# Ruby 1.9.2
f = ->(x){ x < 2 ? x : f[x-1] + f[x-2] }
puts f[6]        #=> 8

How to fix aborting Fibonacci sequence code

The problem with this program is likely the memory constraints. But do you really need all those numbers? If yes, then you better get more hardware.

Otherwise, if you need just the five millionth number in the sequence, you could greatly speed up your program by storing just the two last numbers.

The final step of improvement: calculating an arbitrary member of fibonacci sequence in constant time! -
"Find The Millionth Fibonacci in Java".

Lazy Fibonacci Sequence in Ruby

Don't use recursive enumerators but do it like in Python? With a loop?

def fib()
  Enumerator.new do |yielder|
    a, b = 1, 2
    yielder << a << b
    loop do
      a, b = b, a + b
      yielder << b
    end
  end
end  

What you did there in Ruby looks in Python like this:

def fib():
    yield from (1, 2)
    for a, b in zip(fib(), islice(fib(), 1, None)):
        yield a + b

That's slow as well.

Btw, worse than the exponential time is the exponential amount of memory. That recursive Python version crashes for me when trying to compute the 32nd Fibonacci number. At that point I already have almost 4 million generators running. And your Ruby version crashes for me when trying to compute the 20th Fibonacci number, with error can't create fiber (FiberError). At that point I have almost 12000 fibers running.

---

Related Topics