6. Write a recursive function to compute the number of sequences of n binary digits that do not contain two 1s in a row. (Hint: compute how many such sequences exists that start with 0, and how many exists that start with a 1)

algo.rb

  ## Problem no 6 recursion
class Algo
  def count_binary_count_rec(n)
    if n == 1
      return 2 ** n
    elsif n.zero?
      return 1
    else
      count_binary_count_rec(n-1) + count_binary_count_rec(n-2)
    end
  end
end