« Back
in javascript challenges mathematics algorythms fibonacci read.

Fibonacci Sequence.

I ❤ mathematics, and I regret not paying them the attention they surely deserved when I was in college, mostly because of things like the one I'm about to tell. Surfing the internet... I found this:

Refactor yourself!

var yourself = {  
    fibonacci : function(n) {
        if (n = 0) {
            return 0;
        }
        if (n = 1) {
            return 1;
        }
        else {
            return this.fibonacci(n - 1) +
                this.fibonacci(n - 2);
        }
    }
};

Correct value, but the execution takes too long. Improve it!

In my amazement, I couldn't think of anything, never thought that the simplest fibonacci algorythm was extremely inefficient. This test was part of a website named codility that outsources the developers recruitment by testing them with hard/mind-blowing programming challenges. Just for reference,

The fibonacci numbers follow this sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...

When I recovered from my astonishment, I started to google for an optimised algorythm, and I finally found it, in a website I highly recommend for searching algorythms, Rosetta Code. This was the final result after a little refactorization (I worked a little):

var yourself = {  
    fibonacci: function(n) {
        return function fib(n, a, b) {
            return n > 0 ? fib(n-1, b, a+b) : a;
        }(n, 0, 1);
    }
};

Simple, elegant, recursive, with closures... brilliant!

When I tried my brand-new discovery, I got this output:

Great! Brag about your success and get updates from us ...

And that is what I am doing, bragging! I'm the best! Jokes apart... I wanted to post this algorythm so that I never forget it, and I hope it will be helpful for you too.

I'm sure Fibonacci is hiding somewhere, waiting for his moment to come back from darkness... and when he comes, we will be ready.


Bonus: ES2015 Iterators

let fibonacci = {  
  [Symbol.iterator]() {
    let pre = 0, cur = 1;
    return {
      next() {
        [pre, cur] = [cur, pre + cur];
        return { done: false, value: cur }
      }
    }
  }
};

Bonus 2: ES2015 Generators

let fibonacci = function* (){  
  var fn1 = 1;
  var fn2 = 1;
  while (true){  
    var current = fn2;
    fn2 = fn1;
    fn1 = fn1 + current;
    var reset = yield current;
    if (reset){
        fn1 = 1;
        fn2 = 1;
    }
  }
};
comments powered by Disqus