Why is this wrapped function call faster than a regular function?

Question

Executing this recursive fibonacci function takes around 9.5 seconds on my machine, using a traditional approach:

const fib = n => {
  if (n == 1) return 0;
  if (n == 2) return 1;
  return fib(n - 1) + fib(n - 2);
};

console.log(fib(45));

➜ time node index.js
701408733
node index.js  9,50s user 0,04s system 99% cpu 9,566 total

However, when I wrap the body of the function in another function that gets executed right away, execution drops to 7.5 seconds:

const fib = n => {
  return (() => {
    if (n == 1) return 0;
    if (n == 2) return 1;
    return fib(n - 1) + fib(n - 2);
  })();
};

console.log(fib(45));

➜ time node index.js
701408733
node index.js  7,58s user 0,25s system 99% cpu 7,852 total

This is a huge speedup (~30%!), but I cannot figure out why wrapping the function would make this difference.

Answer 1

This is indeed a very strange behaviour.

After some digging, I see that it's mentioned in a few past questions (for example, this one) that JS performs worse with recursion, such as in fib1.

Now the question that rises is whether fib2 isn't a recursive function. I assume that because it creates a new anonymous function - rather than using the same memory reference to fib2 - it's practically "less recursive" and therefore performs better.

EDIT: After reading this question it looks like what's going on is some sort of Tail Call handling (fib2 uses tail recursion, as opposed to fib1, where each call is calculated before the result can be returned).

Another interesting observation is that - to a certain degree - the recursion does work better, but then it's getting exponentially slower.

function fib1(n) {
  if (n === 1) return 0;
  if (n === 2) return 1;
  return fib1(n - 1) + fib1(n - 2);
};

function fib2(n) {
  return (() => {
    if (n === 1) return 0;
    if (n === 2) return 1;
    return fib2(n - 1) + fib2(n - 2);
  })();
};

function calculateAverageTime(func, iterations = 5) {
  let sum = 0;

  [...Array(iterations)].forEach(() => {
    const start = new Date();
    func();
    const finish = new Date();
    sum += (finish - start);
  });

  return Math.round(sum / iterations);
}

function compare(i) {
  const fib1RunTime = calculateAverageTime(() => fib1(i));
  const fib2RunTime = calculateAverageTime(() => fib2(i));
  console.log(`Difference for fib(${i}) is ${(fib2RunTime - fib1RunTime)}ms`);
}

[10, 20, 30, 40].forEach(i => compare(i));