DEV Community

OneDev
OneDev

Posted on

EXTRA: Fibonacci Sequence

#fibonacci #performance #algorithms #datastructures

The Fibonacci sequence is a series where each number is the sum of the two preceding ones:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Enter fullscreen mode Exit fullscreen mode

The general formula is:

F(n)=F(n−1)+F(n−2)
Enter fullscreen mode Exit fullscreen mode

Simple Fibonacci Function 

function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}
Enter fullscreen mode Exit fullscreen mode

Example: Find fibonacci(5) 

fibonacci(5)
= fibonacci(4) + fibonacci(3)
= (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
= ((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))) + ((fibonacci(1) + fibonacci(0)) + fibonacci(1))
= ((1 + 1) + (1 + 0)) + ((1 + 0) + 1)
= (2 + 1) + (1 + 1)
= 3 + 2
= 5
Enter fullscreen mode Exit fullscreen mode

Or simply in code:

console.log(fibonacci(5)); // Output: 5
Enter fullscreen mode Exit fullscreen mode

Top comments (0)