CODEWITHSUNDEEP
unit-testingrecursionjestjs
Gabriel John Rodriguez
Gabriel John Rodriguez

Reputation: 293

Testing recursive calls in Jest

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?

Upvotes: 22

Views: 12583

Answers (3)

hogreflector
hogreflector

Reputation: 358

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

Upvotes: 2

Ing.LkRuiZ
Ing.LkRuiZ

Reputation: 282

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

Upvotes: 0

Brian Adams
Brian Adams

Reputation: 45830

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)

Upvotes: 24

Related Questions