Fibonacci

Definition

The Fibonacci numbers or Fibonacci series or Fibonacci sequence are the numbers in the following integer sequence:[1][2]

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

or (often, in modern usage):

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

By definition, the first two numbers in the Fibonacci sequence are 1 and 1, or 0 and 1, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two.

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation

F(n) = F(n-1) + F(n-2)

Source: Wikipedia

Code: https://github.com/felipernb/algorithms.js/blob/master/algorithms/math/fibonacci.js

Test: https://github.com/felipernb/algorithms.js/blob/master/test/algorithms/math/fibonacci.js

How to use

This package offers three different implementations of Fibonacci:

• require('algorithms').Math.fibonacci
• require('algorithms').Math.fibonacci.withMemoization
• require('algorithms').Math.fibonacci.exponential

Fibonacci in linear time (default implementation)

This implementation calculates fibonacci in linear time (O(n)) with constant space (O(1)).

var fib = require('algorithms.js').Math.fibonacci;
fib(10); // 55

Fibonacci with memoization

This implementation also calculates fibonacci in linear time (O(n)) due to the memoization, but also due to the memoization it consumes O(n) space and is more appropriate when multiple calls are going to be made and you can take advantage of the caching.

var fib = require('algorithms.js').Math.fibonacci.withMemoization;
fib(10); // 55

Exponential Fibonacci

This implementation is based in the pure definition of the fibonacci sequence:

• fib(0) = 0
• fib(1) = 1
• fib(n) = fib(n-1) + fib(n-2) And takes exponential time to run.

It should not be used unless if to prove some concept.

var fib = require('algorithms.js').Math.fibonacci.exponential;
fib(10); // 55