#fiboanacci

[gertieparr]

[professionalshaps-blog]

Take a Memo

I've been doing a lot of practice code puzzles lately, on sites like HackerRank and Codewars. One of the problems that came up was to implement a function that tells you what number would be at a given spot in the Fibonacci sequence.

The Fibonacci sequence, if you don't remember offhand, is a series of numbers in which each number equals the sum of the number before it and the number before that one. The formula for that sounds like some pretty basic recursion stuff, right?

And you can, in fact, write it thusly. But once your input number gets to be a certain size, the recursive stack level gets too deep. (The below implementation started noticibly stalling out around fibo(35).)

So let's think about recursion for a second. By the time you call fibo(n-2), you've actually already calculated the result, because n-2 is the same thing as saying n-1 when you're in the fibo(n-1) call. All these ns are confusing, but I'm just saying that 35-2 is the same as 34-1.

So maybe we can save our previous calculations somewhere? The array where we store them can't be scoped to the method, because then it'll get reset every time we call it. Let's make an array right above our method, and then have our method check that array before it bothers doing any math at all.

Turns out, this process is called memoization, and can be very useful when you have "expensive" function calls or database queries that recur in your code. I found a number of useful articles about how memoization might help you.

The coolest thing I found was that, in Ruby, a lot of memoized calls use the ||= operator. ||= basically means: if the left hand has a (truthy) value, then keep that value; otherwise, assign it the right hand value. That gives us this awesome one-line solution!