This is an example of not being precise enough when checking for a value in an object. I inadvertently caused this bug during a live coding exercise in a job interview, and spent a couple minutes debugging before I found it.
The exercise was to code up the Fibonnaci sequence, and I was doing a variation where
I memoized previously computed values of the sequence (dynamic programming). I had set
up an object to hold values of the sequence as key-value pairs, where the key is n
and the value is f(n).
I called the object fibMemo, and initialized it with the first two entries in the
Fibonnaci sequence f(0) = 0 and f(1) = 1:
var fibMemo = {0:0, 1:1};Inside the function I checked for previously memoized values of f(n)
using a conditional of the form
if (fibMemo[n]) {
// use the memoized value
} else {
// compute f(n) and memoize it
}For almost all cases this works fine, since if fibMemo[n] hasn't
been memoized for some n (say n=5), then fibMemo[n] ==> undefined, which is falsey.
Then the else condition will evaluate and memoize the value for future calls. Exactly
what I want.
HOWEVER, in the case of n = 0, while fibMemo[0] IS memoized, fibMemo[0] ==> 0.
In this case even though the memoized value exists, the value returned is zero, which
is falsey! So while fibMemo[n] is always falsey if n is NOT memoized, it is NOT
always truthy if it IS memoized.
My code assumes that fibMemo[n] is truthy if
memoized and falsey if not memoized, for any value of n >= 0. Since the n = 0 case
never returns a value, the recursion proceeds unbounded into negative values of n, and
overflows the call stack. (This is a remaining problem in the code:
there's no check to make sure n >= 0.)
The better way to check for the memoized values is to explicitly check for the type of the value in the memoized object:
if (typeof fibMemo[n] === 'number') {
// memoized
} else {
// not memoized
}
Now the conditional is always truthy if the value IS memoized, and always falsey if the value IS NOT memoized.