Fibonacci Sequence in Ruby (Recursion)

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

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.

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

Fibonacci - Recursion - Ruby

This is just the direct 1:1 translation (with a simple twist) of the standard mathematical definition of the Fibonacci Function:

Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n-2) + Fib(n-1)

Translated to Ruby, this becomes:

def fib(n)
  return 0 if n.zero?
  return 1 if n == 1
  fib(n-2) + fib(n-1)
end

It's easy to see that the first two cases can be combined: if n is 0, the result is 0, if n is 1, the result is 1. That's the same as saying if n is 0 or 1, the result is the same as n. And "n is 0 or 1" is the same as "n is less than 2":

def fib(n)
  return n if n < 2
  fib(n-2) + fib(n-1)
end

There's nothing special about this, it's the exact translation of the recursive definition of the mathematical Fibonacci function.

Ruby Sum of Integers for Fibonacci Sequence

puts "Total: %i" %
  ((1..10).inject(0) do |t,i|
    f = fib(i)
    puts "%s: %s" % [i.to_s.rjust(2), f.to_s.rjust(3)]
    t + f
  end)
 1:   1
 2:   1
 3:   2
 4:   3
 5:   5
 6:   8
 7:  13
 8:  21
 9:  34
10:  55
Total: 143

How this Fibonacci code(Ruby) works?

Recursion works by calling itself again and again until the 'break point' happens.
Fib(4) calls for fib(3) and fib(2), fib(3) calls for fib(2) and fib(1)... method has given the value of fib(1) and fib(0) as 1.

Let me try to explain it visually:

> fib(4) =         fib(3)                 +            fib(2) 
> =>       fib(2)        +   fib(1)       +        fib(1)  +  fib(0)
> =>   fib(1) + fib(0)   +   1            +          1     +   1

---

Related Topics