Javascript Fibbonacci Sequence
The Fibonacci Sequence is (wikipedia):
By definition, the first two numbers in the Fibonacci sequence are either 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.
Fun fact: The fibonacci sequence also appears in the smallest, to the largest objects in nature. It is a way for information to flow in a very efficient manner.
Let’s create Fibonacci functions.
1. Write a JavaScript function to get the first n Fibonacci numbers.
const fibonacciSequence = (n) => {
if (n === 1) {
return [1]
} else if (n === 2) {
return [1, 1]
} else {
let result = fibonacciSequence(n - 1)
let length = result.length
result.push(result[length - 1] + result[length - 2])
return result
}
}fibonacciSequence(9)
=> [ 1, 1, 2, 3, 5, 8, 13, 21, 34 ]
Base case: If the number passed in is 1 or 2, return the corresponding sequences.
Each subsequent number is the sum of the previous two numbers. So using recursion, we get the first sequence and then push in the new number by adding the last 2 numbers in the sequence.
If we were finding fibonacci(3), we’d first find fibonacci(3 — 1). That would return an array of [1,1]. We then push in the new value — the sum of the last 2 numbers in the array. 1 + 1 = 2. So the result would be [1, 1, 2].
2. Given a number N return the index value of the Fibonacci sequence
We can use a simple loop to achieve our solution.
const fibonacci = (num) => {
let a = 1, b = 0, c
while(num >= 1) {
c = a
a = a + b
b = c
num--
}
return b
}If the number we are given is greater than or equal to 1, then we calculate the next number by adding the current number to the old number. Then we subtract 1 from the number given and recalculate…
Another option would be to do it recursively.
const fibonacci = (num) => {
if(num <= 1) {
return 1
} else {
return fibonacci(num - 1) + fibonacci(num - 2)
}
}Base case: if the number given is less than or equal to one, return 1.
We know that F(n) = F(n — 1) + F(n — 2). So if the number is more than one then we call the function again with number — 1 and number — 2 and add those values together.