So I’ve been using a variety of resources for studying algorithms, from InterviewCake to FreeCodeCamp to Coursera, and many more. This is a problem that keeps coming up everywhere, so I thought that it would be helpful to walk through it.

Problem: Write a function fib(n) that takes an integer n and returns the nth Fibonacci number. Example functionality: fib(1) => 1, fib(3)=> 2, fib(5) = 5.

Background: In the Fibonacci sequence, each number is the sum of the previous two Fibonacci numbers. The first few numbers (0 and 1) are base cases. Here are the first few numbers of the sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21…

Approaches:

Since Fibonacci numbers are created by adding together previous numbers in the sequence (also themselves Fibonacci numbers), handling this with recursion is an option.

fib(n) = fib(n – 1) + fib(n-2)

Recursive Solution:

Adding in base cases for 0 and 1, the function would look something like this.

def fib(n)
   if n == 0 || n == 1 # base cases
       return n
   end
   return fib(n-1) + fib(n-2)
end

Of course all of this recursion will require a lot of time, O(2^n) to be exact. This exponential time cost comes from the fact that we’re repeating quite a bit of work. Memoization is a technique that we can use to save results and avoid repeated work, but instead of recursion, we can also go the other way and solve the problem iteratively, AKA “Bottom up.”

Iterative Solution: 

def fib(n)
   # edge cases of negative entries, 0 and 1
   if n < 0
       raise Exception, “Index can’t be negative.”
   elsif n == 0 || n == 1
       return n
   end

   first_num = 0
   second_num = 1

   (n-1).times do
       current_num = first_num + second_num
       first_num = second_num
       second_num = current_num
   end
   return current_num
end

The time complexity for this version of the solution depends on just how big n is, so O(n). The recursive solution is beautiful and short, but I think that the iterative version makes more sense in my head. Shockingly, it’s also faster!