## DEV Community is a community of 551,182 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # 12+ ways to Fibonacci

This morning I came across a great little paper showing twelve algorithms to compute Fibonacci numbers in Python. I had to share!

Calculating fibonacci numbers recursively is used to benchmark computer languages and sometimes by interviewers trying to impress job seekers. More importantly, it inspired one of the greatest songs ever so it's worth remembering a few of these algorithms and spiral out :o)

Not to repeat the python examples from the paper, let's instead look at four ways to compute the fibonacci number of N in Javascript.

``````//ES6

// using recursion
const fibonacci = n => n <= 2 ? 1 : fibonacci(n - 1) + fibonacci(n - 2);

// using cache
const fibCached = (n, cache = {1: 1, 2: 1}) => cache[n] ? cache[n] : cache[n] = fibCached(n - 1, cache) + fibCached(n - 2, cache);

// using tail recursion
const fibTailRecursed = (n, sum = 1, prev = 1) => n <= 2 ? sum : fibTailRecursed(n - 1, sum + prev, sum);

// using Binet's formula
const fibBinet = n => Math.floor( (((1 + Math.sqrt(5)) / 2 ) ** n) / Math.sqrt(5) + 0.5);
``````

This very interesting formula discovered by Binet had caught my eye a few years ago when I found out it could be used in Solidity smart contracts.

The Ethereum Virtual Machine is a resource constrained environment where every operation is metered and payed for, which discourages using recursion or iteration, but understanding it in depth does make one a better programmer imho.

``````//Solidity v0.5+

function fibBinet(uint n) external pure returns(uint a) {
if (n <= 2) return 1;

uint h = n / 2;

// find highest set bit in n

a = 1;
uint b = 1;
uint c;

c = a * a + b * b;
if (n & mask > 0) {
b = b * (b + 2 * a);
a = c;
} else {
a = a * (2 * b - a);
b = c;
} 