Apple’s event in Chicago last month involved some fibonacci code. This intrigued me to refresh my memory at Wikipedia as to how the algorithm works, and then I played around with some JavaScript implementations for generating a user-specified sequence of fibonacci numbers. The terse two-line version looks like this:

const fib = (amount = 15, nums = [0, 1]) => {
  nums.length >= amount ? nums.length = amount : nums.push(nums[nums.length - 1] + nums[nums.length - 2]);
  return nums.length < amount ? fib(amount, nums) : nums;
};

In real life, that’s too terse; I’d have a hard time approving a PR for a real app that had that sort of code in it. Here is a more reasonable implementation:

const fibonacci = (amount = 15, numbers = [0, 1]) => {
  if (numbers.length >= amount) {
    numbers.length = amount;
    return numbers;
  }
  numbers.push(numbers[numbers.length - 1] + numbers[numbers.length - 2]);
  return fibonacci(amount, numbers);
};

Moreover, if we’re not worried about the edge case scenario in which the user enters fibonacci(n) for all n < 2, then we can simplify the function to this:

const fibonacci = (amount = 15, numbers = [0, 1]) => {
  if (numbers.length >= amount) {
    return numbers;
  }
  numbers.push(numbers[numbers.length - 1] + numbers[numbers.length - 2]);
  return fibonacci(amount, numbers);
};

If we want to find the fibonacci at a specific number, we can simply reference the above function in a convenient wrapping function like so:

const fibonacciAt = (nth) => {
  const numbers = fibonacci(nth);
  return numbers[numbers.lenth - 1];
};

Or we can modify the core function to achieve the same thing, like this:

const fibonacciAt = (nth = 15, numbers = [0, 1]) => {
  if (numbers.length >= nth) {
    numbers.length = nth;
    return numbers[numbers.length - 1];
  }
  numbers.push(numbers[numbers.length - 1] + numbers[numbers.length - 2]);
  return fibonacciAt(nth, numbers);
};

What’s interesting is that this Medium article tries to demonstrate a performant recursive implementation to arrive at an nth fibonacci number, but its most performant implementation still requires n * 2 function calls to arrive at the answer; whereas mine only requires n function calls.