fibonacci_exploration.rb

# Recursive finds number:
def fib_recur(n)
  return n if n <= 1
  fib_recur(n-1) + fib_recur(n-2)
end

# Computes F(n − 2) twice, F(n − 3) three times, etc., each time from scratch.
# O(2^n)

# Recursive with memorization:
@fibonacci = [0, 1]
def fib_recur_memo(n)
  @fibonacci[n] ||= fib_recur_memo(n - 2) + fib_recur_memo(n - 1)
end

# Values are computed once and stored in the memorization instance variable
# O(n^2)

# Recursive prints sequence:
def fib_recur_seq(n)
  (0..n).each do |i|
    puts fib_recur_memo(i)
  end
end

# O(2n^2)

# Iterative solution:
def fib_iter(n)
  current_number = 0
  next_number = 1
  n.times do
    temp_number = current_number
    current_number = next_number
    next_number = temp_number + next_number
  end
  current_number
end

# O(n)

# Iterative solution memoized:
@fibonacci_iter = [0, 1]
def fib_iter_memo(n)
  @fibonacci_iter[n] unless @fibonacci_iter[n].nil?
  (n - 1).times do |i|
    @fibonacci_iter[i + 2] = @fibonacci_iter[i] + @fibonacci_iter[i + 1]
  end
  @fibonacci_iter[n]
end

# < O(n)

# Iterative sequence:
def fib_iter_seq(n)
  current_number = 0
  next_number = 1
  (n - 1).times do
    temp_number = current_number
    current_number = next_number
    next_number = temp_number + next_number
    puts current_number
  end
end

# O(2n)

# Iterative memoized sequence:
@fibonacci_iter = [0, 1]
def fib_iter_memo_seq(n)
  @fibonacci_iter[n] unless @fibonacci_iter[n].nil?
  (n - 1).times do |i|
    @fibonacci_iter[i + 2] = @fibonacci_iter[i] + @fibonacci_iter[i + 1]
  end
  puts @fibonacci_iter.take(n + 1)
end