在Jest中测试递归调用

Question

我目前正在测试使用memoization + recursion的Fibonacci算法.

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];
}

我想在Jest中测试函数的memoization方面,以确保函数正确使用哈希并且不执行冗余工作:

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

但是,mock.calls仅报告使用初始参数值调用此函数一次,并且不跟踪其他递归调用.有任何想法吗？

Answer 1

JavaScript中的间谍依赖于作为对象属性的函数. 它们通过使用包装和跟踪对原始调用的新函数替换object属性来工作.

如果递归函数直接调用自身,则无法监视这些调用,因为它们直接引用该函数.

为了监视递归调用,他们必须引用可以被监视的函数.幸运的是,这是可能的,可以通过两种方式之一完成.

第一种解决方案是将递归函数包装在一个对象中,并引用递归的object属性:

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;

第二种解决方案是将递归函数导入到自己的模块中,并使用导入的函数进行递归:

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

上面的测试使用Jest,但这些想法扩展到其他测试框架.例如,以下是使用Jasmine的第二个解决方案的测试:

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];
}

(我优化了memoization以要求最少的调用次数)