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)