Ruby Best Practices

Memoization

A typical “Hello World” program in functional programming languages is a recursive function that computes the Fibonacci sequence. In Ruby, the trivial implementation looks like this:

def fib(n)
  return n if (0..1).include? n
  fib(n-1) + fib(n-2)
end

However, you’ll feel the pain that is relying on deep recursion in Ruby if you compute even modest values of n. On my machine, fib(30) computes within a few seconds, but I’m too impatient to even give you a time for fib(40). However, there is a special characteristic of functions like this that makes it possible to speed them up drastically.

In mathematics, a function is said to be well defined if it consistently maps its input to exactly one output. This is obviously true for fib(n), as fib(6) will always return 8, no matter how many times you compute it. This sort of function is distinct from one that is not well defined, such as the following:

def mystery(n)
  n + rand(1000)
end

If we run this code a few times with the same n, we see there isn’t a unique relationship between its input and output:

>> mystery(6)
=> 928
>> mystery(6)
=> 671
>> mystery(6)
=> 843

When we have a function like this, there isn’t much we can assume about it. However, well-defined functions such as fib(n) can get a massive performance boost almost for free. Can you guess how?

If your mind wandered to tail-call optimization or rewriting the function iteratively, you’re thinking too hard. However, the idea of reducing the amount of recursive calls is on track. ...