How to test a recursive function in JavaScript

Note: 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 test that it is being called recursively.

EXAMPLE

I created this simplistic function to calculate Fibonnaci numbers:

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 something like this:

describe('fibonacci', () => {
  it('should calculate Fibonacci numbers', () => {
    expect(fibonacci(5)).toBe(5);
    expect(fibonacci(10)).toBe(55);
    expect(fibonacci(15)).toBe(610);
  });
});

That works fine, but if I add a spy to check that the function is called recursively the spy 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
  });
});

IMPORTANCE

Being able to test the recursion is important. For example, I created an optimized and memoized version of the function:

const fibonacci = (n, memo = { 0: 0, 1: 1 }) => {
  if (n < 0) throw new Error('must be 0 or greater');
  if (memo[n] !== undefined) return memo[n];
  if (memo[n - 1] === undefined) {
    memo[n - 1] = fibonacci(n - 1, memo);
  }
  return memo[n - 1] + memo[n - 2];
};

How do I test that this version is called fewer times?