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

Spies in JavaScript depend on the function being the property of an object. They work by replacing the object property with a new function that wraps and tracks calls to the original.

If a recursive function calls itself directly it is not possible to spy on those calls since they refer directly to the function.

In order to spy on recursive calls they must refer to functions that can be spied on. Fortunately, this is possible and can be done in one of two ways.

---

The first solution is to wrap the recursive function in an object and refer to the object property for the recursion:

fib.js

const wrappingObject = {
  memoization: (num, hash = { '0':0, '1':1 }) => {
    if (hash[num-1] === undefined) {
      hash[num-1] = wrappingObject.memoization(num-1, hash);
    }
    return hash[num-1] + hash[num-2];
  }
};
export default wrappingObject;

fib.test.js

import fib from './fib';

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();
  });
});

---

The second solution is to import a recursive function back into its own module and use the imported function for the recursion:

fib.js

import * as fib from './fib';  // <= import the module into itself

export function memoization(num, hash = { '0':0, '1':1 }) {
  if (hash[num-1] === undefined) {
    hash[num-1] = fib.memoization(num-1, hash);  // <= call memoization using the module
  }
  return hash[num-1] + hash[num-2];
}

fib.test.js

import * as fib from './fib';

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();
  });
});

The tests above are using Jest, but the ideas extend to other testing frameworks. For example, here is the test for the second solution using Jasmine:

// ---- fib.test.js ----
import * as fib from './fib';

describe('memoization', () => {
  it('should memoize correctly', () => {
    const spy = spyOn(fib, 'memoization').and.callThrough();

    const result = fib.memoization(50);
    expect(result).toBe(12586269025);
    expect(spy.calls.count()).toBe(49);
  });
});

(I optimized memoization to require the minimum number of calls)