recursive cat nap

One of my favorite challenges from Week 1 at DBC was looking at pros and cons of writing a method iteratively vs recursively. So naturally I had to blog about it.

Lets use the classic - calculate the nth number of the Fibonacci sequence as an example:

Fibonacci - iterative

def fibonacci_iterative(n)
  array =[0,1]
  2.upto(n) do |num|
    array << (array[num-2] + array[num-1])
  end
  array[n]
end

Fibonacci - recursive

def fibonacci_recursive(n)
  return n if [0,1].include? n
  fibonacci_recursive(n-2) + fibonacci_recursive(n-1)
end

We can measure a program’s runtime by using Ruby’s handy Benchmark module.

puts Benchmark.measure{fibonacci_iterative(20)}
# => (  0.000006)
puts Benchmark.measure{fibonacci_recursive(20)}
# => (  0.001187)

As you can see, my recursive solution performs far worse in terms of runtime than it’s iterative counterpart. This is because our method re-calculates all of the preceeding numbers every time it is run.

What if instead we tell our method to remember the results of our earlier calculations? That’s the concept behind Memoization. We can create an empty hash to store temporary results and have our program check if that calculation has been done already. If it has, we can just pull the stored result.

Refactoring our recursive solution:

Fibonacci recursive - refactored

CACHE = {}
def memoized_fibonacci(n)
  CACHE[n] ||= (n <= 1 ? n : memoized_fibonacci(n-2) + memoized_fibonacci(n-1))
end

As you can see, our runtimes are now much more comparable!

puts Benchmark.measure{fibonacci_iterative(20)}
# => (  0.000006)
puts Benchmark.measure{memoized_fibonacci(20)}
# => (  0.000010)

happy dance

References: