How to spy on a recursive function in JavaScript
Clash Royale CLAN TAG#URR8PPP
How to spy on a recursive function in JavaScript
Note: I've seen variations of this question asked in different ways and in reference to different testing tools. I thought it would useful to have the issue and solution clearly described. My tests are written using Sinon spies for readability and will run using Jest or Jasmine (and need only minor changes to run using Mocha and Chai), but the behavior described can be seen using any testing framework and with any spy implementation.
ISSUE
I can create tests that verify that a recursive function returns the correct value, but I can't spy on the recursive calls.
EXAMPLE
Given this recursive function:
const fibonacci = (n) =>
if (n < 0) throw new Error('must be 0 or greater');
if (n === 0) return 0;
if (n === 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
...I can test that it returns the correct values by doing this:
describe('fibonacci', () =>
it('should calculate Fibonacci numbers', () =>
expect(fibonacci(5)).toBe(5);
expect(fibonacci(10)).toBe(55);
expect(fibonacci(15)).toBe(610);
);
);
...but if I add a spy to the function it reports that the function is only called once:
describe('fibonacci', () =>
it('should calculate Fibonacci numbers', () =>
expect(fibonacci(5)).toBe(5);
expect(fibonacci(10)).toBe(55);
expect(fibonacci(15)).toBe(610);
);
it('should call itself recursively', () =>
const spy = sinon.spy(fibonacci);
spy(10);
expect(spy.callCount).toBe(177); // FAILS: call count is 1
);
);
You couldn't test performance by spying. The function being spied could be buggy. Recursive is not necessary slow. Recursive could be improved by runtime in future. Test your code as black box and test real requirement from customer. Customer request could be factorized into small function. Testing customer request doesn't mean integration testing. Performance is a customer requestment while how many calls on a function definitely is not.
– qxg
Aug 6 at 4:39
I agree that black box testing is the best approach for production code. It is very possible that the usefulness of spying on recursive calls is limited to an interesting novelty or academic exercise. In any case, if someone wants to spy on the recursive calls of a JavaScript function, this is how it can be done.
– brian-lives-outdoors
Aug 6 at 6:15
1 Answer
1
ISSUE
Spies work by creating a wrapper function around the original function that tracks the calls and returned values. A spy can only record the calls that pass through it.
If a recursive function calls itself directly then there is no way to wrap that call in a spy.
SOLUTION
The recursive function must call itself in the same way that it is called from outside itself. Then, when the function is wrapped in a spy, the recursive calls are wrapped in the same spy.
Example 1: Class Method
Recursive class methods call themselves using this
which refers to their class instance. When the instance method is replaced by a spy, the recursive calls automatically call the same spy:
this
class MyClass
fibonacci(n)
if (n < 0) throw new Error('must be 0 or greater');
if (n === 0) return 0;
if (n === 1) return 1;
return this.fibonacci(n - 1) + this.fibonacci(n - 2);
describe('fibonacci', () =>
const instance = new MyClass();
it('should calculate Fibonacci numbers', () =>
expect(instance.fibonacci(5)).toBe(5);
expect(instance.fibonacci(10)).toBe(55);
);
it('can be spied on', () =>
const spy = sinon.spy(instance, 'fibonacci');
instance.fibonacci(10);
expect(spy.callCount).toBe(177); // PASSES
spy.restore();
);
);
Note: the class method uses this
so in order to invoke the spied function using spy(10);
instead of instance.fibonacci(10);
the function would either need to be converted to an arrow function or explicitly bound to the instance with this.fibonacci = this.fibonacci.bind(this);
in the class constructor.
this
spy(10);
instance.fibonacci(10);
this.fibonacci = this.fibonacci.bind(this);
Example 2: Modules
A recursive function within a module becomes spy-able if it calls itself using the module. When the module function is replaced by a spy, the recursive calls automatically call the same spy:
ES6
// ---- lib.js ----
import * as lib from './lib';
export const fibonacci = (n) =>
if (n < 0) throw new Error('must be 0 or greater');
if (n === 0) return 0;
if (n === 1) return 1;
// call fibonacci using lib
return lib.fibonacci(n - 1) + lib.fibonacci(n - 2);
;
// ---- lib.test.js ----
import * as sinon from 'sinon';
import * as lib from './lib';
describe('fibonacci', () =>
it('should calculate Fibonacci numbers', () =>
expect(lib.fibonacci(5)).toBe(5);
expect(lib.fibonacci(10)).toBe(55);
);
it('should call itself recursively', () =>
const spy = sinon.spy(lib, 'fibonacci');
spy(10);
expect(spy.callCount).toBe(177); // PASSES
spy.restore();
);
);
Common.js
// ---- lib.js ----
exports.fibonacci = (n) =>
if (n < 0) throw new Error('must be 0 or greater');
if (n === 0) return 0;
if (n === 1) return 1;
// call fibonacci using exports
return exports.fibonacci(n - 1) + exports.fibonacci(n - 2);
// ---- lib.test.js ----
const sinon = require('sinon');
const lib = require('./lib');
describe('fibonacci', () =>
it('should calculate Fibonacci numbers', () =>
expect(lib.fibonacci(5)).toBe(5);
expect(lib.fibonacci(10)).toBe(55);
);
it('should call itself recursively', () =>
const spy = sinon.spy(lib, 'fibonacci');
spy(10);
expect(spy.callCount).toBe(177); // PASSES
spy.restore();
);
);
Example 3: Object Wrapper
A stand-alone recursive function that is not part of a module can become spy-able if it is placed in a wrapping object and calls itself using the object. When the function within the object is replaced by a spy the recursive calls automatically call the same spy:
const wrapper =
fibonacci: (n) =>
if (n < 0) throw new Error('must be 0 or greater');
if (n === 0) return 0;
if (n === 1) return 1;
// call fibonacci using the wrapper
return wrapper.fibonacci(n - 1) + wrapper.fibonacci(n - 2);
;
describe('fibonacci', () =>
it('should calculate Fibonacci numbers', () =>
expect(wrapper.fibonacci(5)).toBe(5);
expect(wrapper.fibonacci(10)).toBe(55);
expect(wrapper.fibonacci(15)).toBe(610);
);
it('should call itself recursively', () =>
const spy = sinon.spy(wrapper, 'fibonacci');
spy(10);
expect(spy.callCount).toBe(177); // PASSES
spy.restore();
);
);
Thanks for this answer that explains how spies work and why it couldn’t be used (to answer the question)
– vol7ron
Aug 6 at 13:09
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
Whether it's implemented recursively or not is an implementation detail - IMHO not something you should be explicitly testing.
– eddiewould
Aug 6 at 2:21