Fibonacci Sequence

I first learned about the Fibonacci sequence in high school, if I remember correctly. I remember in my calculus class after the AP exam, we would make art using the Fibonacci sequence because we did not have any assignments after the exam. We all were able to make some interesting and creative art with them. Because high school was years ago, I no longer have the art anymore.

So what is the Fibonacci sequence? The Fibonacci sequence is basically the sum of the previous two numbers. In mathematical form, it is

F[n] = F[n - 2] + F[n - 1],

with F[0] = 0 and F[1] = 1. Using just these 2 numbers, we can determine F[2], F[3], and so on. The first five numbers of the Fibonacci sequence is

0, 1, 1, 2, 3, 5,

with 0 as the zeroth term. The Fibonacci sequence first appeared in Indian mathematics in its connection to Sanskrit prosody. Outside of India, it appeared in a book by Fibonacci in which it was used to calculate the growth of the rabbit population. It has many applications such as in nature where we see in branching of a tree, arrangements of leaves on a stem to name a few examples. Another application is in computer science such as determining the greatest common divisor of two integers.

I want to discuss solving this problem because the Fibonacci sequence, as I heard, is asked in a technical interview and is a common question. To start off, we have an array with the first two numbers

arr = [0, 1]. 

Then we use a for-loop starting at x = 2, and ending at a number n, add

arr[x - 2] + arr[x - 1],

and then we push the number into the array

arr.push(arr[x - 2] + arr[x - 1]). 

The full code is then

function fibonacci(n){
    let arr = [0, 1]
    for(var x = 2; x <= n; x++){
        arr.push(arr[x - 2] + arr[x - 1])
    }
    return arr
}. 

Let’s test it out with n = 7. The answer is

[0, 1, 1, 2, 3, 5, 8, 13], 

and indeed, from figure 7, it is.

Fig. 1: Answer for n = 7.

With one way of solving it done, let’s look at another by using recursion. When using this method, I had to use two functions to get my answer. The first function is a recursion. In the recursion function, any number n that is less than 2, simply

return n. 

Then we return

return fib(n - 1) + fib (n - 2).

Full code is

function fib(n) {
  if (n < 2){
    return n
  }
  return fib(n - 1) + fib (n - 2)
}. 

That is all. Now let’s work on the next function. It is similar to the first function we used except we replace

arr.push(arr[x - 2] + arr[x - 1])

with

arr.push(fib(x)).

The code in the entirety is

function fib(n) {
  if (n < 2){
    return n
  }
  return fib(n - 1) + fib (n - 2)
}
function fibonacci(n){
    let arr = [0, 1]
    for(var x = 2; x <= n; x++){
        arr.push(fib(x))
    }
    return arr
}. 

Using n = 7, we get the exact same answer as the previous code. SO both methods work. If you know a more effective method of solving it, let me know.