Testing recursive calls in Jest

Question

I'm currently testing a Fibonacci algorithm that uses memoization+recursion.

function memoization(num, hash = {'0': 0, '1':1}) {
  if (!hash.hasOwnProperty(num)) {
    hash[num] = memoization(num-1,hash) + memoization(num-2,hash);
  }
  return hash[num];
}

I want to test the memoization aspect of the function in Jest to ensure that the function is properly using the hash and not doing redundant work:

test('is never run on the same input twice', ()=>{
    fib.memoization = jest.fn(fib.memoization);
    fib.memoization(30);
    expect(allUniqueValues(fib.memoization.mock.calls)).toBeTruthy();
  });

However, the mock.calls only reports this function being called once with the initial parameter value and doesn't keep track of the additional recursive calls. Any ideas?

Answer 1

For this case, I would suggest taking a Functional Programming approach.

1. Build your function to accept as 1st parameter the recursive function
2. Create a Factory function to bind the recursive to itself
3. Use the Factory function to produce your function

function memoizationRecursive(self, num, hash = {'0': 0, '1':1}) {
  if (!hash.hasOwnProperty(num)) {
    hash[num] = self(self, num-1,hash) + self(self, num-2,hash);
  }
  return hash[num];
}

const memoizationFactory = (recursiveFn) => recursiveFn.bind(null, recursiveFn);

const memoization = memoizationFactory(memoizationRecursive);

Then in your test file, wrap the recursive function with a jest mock and use the Factory to produce the same function.

test('is never run on the same input twice', ()=>{
  const memoizationRecursiveSpy = jest.fn(fib.memoizationRecursive);
  const memoization = fib.memoizationFactory(memoizationRecursiveSpy);

  memoization(30);

  expect(allUniqueValues(memoizationRecursiveSpy.mock.calls)).toBeTruthy();
});

Answer 2

I've found out that it works as expected if you turn memoization() into an arrow function:

fib.js

// Don't import module in itself

export const memoization = (num, hash = { '0': 0, '1': 1 }) => {
    if (hash[num - 1] === undefined) {
        hash[num - 1] = memoization(num - 1, hash); // <= call memoization as you would, without module
    }
    return hash[num - 1] + hash[num - 2];
};

fib.test.js

describe('memoization', () => {
    it('should memoize correctly', () => {
        const mock = jest.spyOn(fib, 'memoization');

        const result = fib.memoization(50);
        expect(result).toBe(12586269025);
        expect(mock).toHaveBeenCalledTimes(49);

        mock.mockRestore();
    });
});