Happy Fibonacci Day!

In mathematics, the Fibonacci sequence is characterized by every number after the first two being the sum of the two preceding numbers:

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Often, especially in modern usage, the sequence is preceded by a zero:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

November 23 (11/23) is Fibonacci day because when the date is written in the MM/DD format, the digits are the start of the sequence: 1,1,2,3

Without Recursion

Basically, I manually sequenced the numbers and wrote my thought process in JavaScript. It’s bulky and a little dumb:

//output
var output = Array();

//the loop
while (output.length < 1000) {
  var push; //what we're gonna add to the output
  if (output.length <= 1) {
    //at the start of the sequence we can't add two previous numbers because they don't exist.
    //so we have to start with 0,1, which this accomplishes
    push = output.length;
  } else {
    //after the first to entries
    //we need to push the sum of the current position and the previous position in the output array
    push = output[output.length - 1] + output[output.length - 2];
  }
  //push the number
  output.push(push);
}

See the Pen Fibonacci in JS by Nate Northway (@the_Northway) on CodePen.

With Recursion

A recursive function calls itself until a condition is met. To use recursion to calculate the Fibonacci sequence, the condition which would stop the recursive step is the base case, 0.
We need a point to start from, too. This will be the length of the return – going from our above example, we’ll return 1,000 numbers.

function fib(n) {
  if (n < 2) return [0,1]; //if the passed integer is less than two, we're at the "base condition", return
  var result = fib(n - 1); //start the recursion
  result.push(result[result.length - 1] + result[result.length - 2]); //push results to an array
  return result; //return the array
}
var output = document.getElementById('result');
output.append(fib(1000));

See the Pen Fibonacci in JS (with recursion) by Nate Northway (@the_Northway) on CodePen.

A word about speed

The recursive example is a lot easier to read than the iterative example. But there is a word about performance I’d like to make. The iterative function is just iterating, counting, and adding numbers. There’s a little bit extra in there for output, but it’s not a lot. The recursive function, on the other hand, is building a huge call stack. So fib(n) actually becomes fib(n) + fib(n -1), which is also then called down. I’ve heard an analogy to a tree and I really like that. It takes a bit for your browser to climb from the top of the tree to the base case. In my tests, the recursive function took 2.5ms, where the iterative solution took .19ms. Not a huge visual difference on my modern MacBook, but on an older browser? That could be huge.
But there is a way to improve our recursive function. We can use tail calls. A tail call is an ES6 feature in which a function returns and calls a function as its very last action. See below for examples:

function test(n) {
  //stuff
  return aFunction(); //this is a tail call
}

function test(n) {
  //do stuff
  return aFunction() + n; //not a tail call, last action is adding "n"
}

function test(n) {
  //do stuff
  return aFunction(n); //this is a tail call
}

function test(n) {
  //do stuff
  return aFunction(n) + anotherFunction(n); //not a tail call, last action is adding the return of two functions
}

function test(n) {
  //do stuff
  return test(n); //this is a tail call
}

Tail calls improve the execution time because the engine treats it more like an iterative loop. The reason this happens is because there is no need to stack execution contexts and all information is packed in to the last action. Let’s see how we can leverage this in a different recursive function:

var r = Array();
function optimizedFib(n, a = 1, b = 0) {
  r.push(b);
  if (n === 0) {
    return b;
  }
  return optimizedFib(n - 1, a + b, a);
}

This took .2ms, 10x faster than our original recursive function.

See the Pen Fibonacci in JS (with recursion [optimized]) by Nate Northway (@the_Northway) on CodePen.

I had fun with this. If I were a humorous person, I’d tell you a Fibonacci joke here, but I’m not very humorous, and any joke I would tell would probably be as bad as the last two you heard combined.

I went in to the performance discussion because I read this article, which does a much better job of explaining tail functions than I could.