How to write fibonacci-sequence using recrusion in Ruby?

Question

I have tried to create a method in Ruby which returns true if number is included fibonacci-sequence or false if it's not.

I think I got a problem when I return true or false.

Could anybody tell me why the first code doesn't work please?

def is_fibonacci?(num, array=[0,1])

  n = array.length - 1

  if array[n] > num
    array.include?(num) ? true : false
  end

  array << array[n] + array[n-1]
  is_fibonacci?(num, array)

end

When I run this code, I got this error message.

=>filename.rb:36:in `include?': Interrupt

def is_fibonacci?(num, array=[0,1])
  n = array.length - 1

  if array[n] > num
    if array.include?(num)
        return true
    else
        return false
    end
  end

  array << array[n] + array[n-1]
  is_fibonacci?(num, array)

end

Second code worked.

Why can't I use

array.include?(num) ? true : false 

in the code?

Thank you for helping.

Answer 1

Shivam already gave an good answer to the question why your first version does not work.

I just want to note that there is no reason to keep all calculated fibonacci numbers in the array. That is a waste of space and probably a bit inefficient. Therefore you could simplify your method to:

def fibonacci?(number)
  fibos = [0, 1]
  fibos << (fibos.shift + fibos.last) while fibos.last < number
  fibos.include?(number)
end

Answer 2

In your first version, the block

if array[n] > num
  array.include?(num) ? true : false
end

is syntactically correct (although nasty), but semantically incorrect for your program because you don't return the result. You can either add an explicit return on that statement, or make the rest of your program an else clause. The following version works because by default Ruby returns the result on the last statement executed and only one branch of the if/else gets evaluated:

def is_fibonacci?(num, array=[0,1])
  n = array.length - 1
  if array[n] > num
    array.include?(num)
  else
    array << array[n] + array[n-1]
    is_fibonacci?(num, array)
  end
end

Answer 3

Why can't I use array.include?(num) ? true : false

Syntactically there is nothing wrong in this statement and it should work fine. (it may return SystemStackError: stack level too deep though in context of your code as you are not returning any value).

Here is an example:

array = [0,1]
num = 1
array.include?(num) ? true : false
# => true
num = 3
array.include?(num) ? true : false
# => false

However this is horrible code. Official documentation for .include? clearly states:

Returns true if the given object is present in self (that is, if any object == anObject), false otherwise.

Which means:

num = 1
array.include?(num)
# => true
num = 3
array.include?(num)
# => false

Again you are repeating the same mistake in the following code:

 if array.include?(num)
    return true
 else
    return false
 end

All of the above code can be replaced with just one line:

return array.include?(num)

Answer 4

The reason array.include?(num) ? true : false does not work is because you have no return statement. Change it to return array.include?(num) ? true : false. WIthout it will just call another level of the recursion algorithm and in the end run too deep into into the stack.

And just as a bonus, here is the famous one-liner using a hash:

fibonacci = Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2] }

p fibonacci[2]  # => 1
p fibonacci[23] # => 28657

Answer 5

Using the hash concept by @hirolau we can do this in two lines.

def fib?(n)
  @fibonacci ||= Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2] }
  (0..n+1).any? { |x| @fibonacci[x] == n }
end

Answer 6

Fibonacci numbers algorithm can be done two ways: with and w/o recursion. Recursion version must have a memoization implemented to avoid exponential complexity of algorithm.

Variant 1:

class Fibonacci
  def initialize(num)
    @num = num
    @array = [0,1]
  end

  def process
    return @num if [0,1].include?(@num)
    2.upto(@num).each do |i|
      @array[i] = @array[i-1] + @array[i-2]
    end
    @array[@num]
  end
end

Variant 2:

class FibonacciMemoizedRecursion
  def initialize(num)
    @num = num
    @memo = {0 => 0, 1 => 1, 2 => 1}
  end

  def process
    recursion(@num)
  end

  private

  def recursion(a)
    return @memo[a] if @memo.include?(a)
    @memo[a] = recursion(a-1) + recursion(a-2)
  end
end

To test we can use MiniTest library:

require 'minitest/autorun'

class FibonacciTest < Minitest::Unit::TestCase
  def test_process_1
    assert_equal 0, Fibonacci.new(0).process
  end

  def test_process_2
    assert_equal 1, Fibonacci.new(1).process
  end

  def test_process_3
    assert_equal 1, Fibonacci.new(2).process
  end

  def test_process_4
    assert_equal 2, Fibonacci.new(3).process
  end

  def test_process_5
    assert_equal 3, Fibonacci.new(4).process
  end

  def test_process_6
    assert_equal 5, Fibonacci.new(5).process
  end

  def test_process_7
    assert_equal 8, Fibonacci.new(6).process
  end

  def test_process_8
    assert_equal 13, Fibonacci.new(7).process
  end
end