Fibonacci sequence in Javascript

Question

I am very new to programming in general and am having a hard time understanding this Fibonacci sequence example:

var fib = [0, 1];
for (var i = 2; i < n; i++) {
    fib[ i ] = fib[ i - 1 ] + fib[ i - 2 ];
    console.log(fib);
}

On the first iteration, index 2 is equal to 1, simple enough. But, when I try the second iteration with i = 3, I get:

fib[ 3 ] = fib[ 3 - 1 ] + fib[ 3 - 2 ];  
fib[ 3 ] = fib[ 2 ] + fib[ 1 ]; 
fib[ 3 ] = fib[ 3 ];

Where am I going wrong with my thinking? So far I have:

var fib = [0,1,1,3]

which I know is not correct.

Answer 1

fib[ 3 ] = fib[ 3 - 1 ] + fib[ 3 - 2 ];  
fib[ 3 ] = fib[ 2 ] + fib[ 1 ]; 
fib[ 3 ] = fib[ 3 ];

So your problem is in line #2. The numbers in the [] brackets are indices, which state which part of an array should be read. When the + operator is applied, they are not added, but instead the two fib[2] and fib[1] are evaluated to their corresponding data, meaning they are evaluated to 1 and 1, which then are added together to 2.

I hope this is understandable. If not, just ask in the comments.

Answer 2

Well, why did you do this in your calculation

fib[3] = fib[2] + fib[1]
fib[3] = fib[3]

When you're dealing with arrays the value at the index represented by the sum of the indices is not equal to the sum of the values of the array at those indices.

To put it simply, you can't add the numbers within the square brackets on paper. Its like having two wallets with 5 and 15 dollars each in them. You can't say you have 15 dollars because 1+1 is two and you'll look into the second wallet. You'll add the 'contents' of the wallets instead to find the total monetary amount. Which is 20

Answer 3

You're code is fine. Ran this and got the proper output:

var fib = [0, 1];
for (var i = 2; i < 10; i++) {
    fib[ i ] = fib[ i - 1 ] + fib[ i - 2 ];
    console.log(fib);
}

Console: 0,1,1,2,3,5,8,13,21,34

Answer 4

fib[ 3 ] = fib[ 3 - 1 ] + fib[ 3 - 2 ];  
fib[ 3 ] = fib[ 2 ] + fib[ 1 ]; 
fib[ 3 ] = fib[ 3 ];

You are adding the indexes up not the value in the array the index points to

fib[ 3 ] = fib[ 3 - 1 ] + fib[ 3 - 2 ];  
fib[ 3 ] = fib[ 2 ] + fib[ 1 ]; 
fib[ 3 ] = 1 + 1;

[0,1,1,2]

fib[0] = 0
fib[1] = 1
fib[2] = 1
fib[3] will equal 2

So next iteration

fib[4] = fib[4-1] +fib[4-2]
fib[4] = fib[3] + fib[2]
fib[4] = 1 + 2
fib[4] = 3

Answer 5

When you are reasoning about the code, you make the jump from fib[3] = fib[2] + fib[1] to fib[3] = fib[3]. This happens to be a transformation that results in a correct statement, but it is not how it works. This code is adding the value at index 2 to the value at index 1. That is not the same as taking the value at index 3. The way this reasoning should work is as follows:

You start with fib = [0, 1]. Then in the first iteration of the loop you have fib[2] = fib[1] + fib[0]. This means that you add the value at index 0 (which happens to be 0) to the value at index 1 (which happens to be 1) to get the value that you put at the end of the array (1). Then in the second iteration, you do a similar thing, adding the value at index 1 (still 1) to the value at index 2 (also 1) to get 2, which goes at the end of the array. This continues, and at each iteration you add together the last two values in the array to get the next value.

In JavaScript, when using an array like fib, fib[i] refers to the ith value in this array, counting from 0. So fib[0] is the first element in the array, fib[1] is the second element in the array, and so on.

Answer 6

Implementation with array reduce()

var a = [3,2,3,6,2,3,4];
var fib  = a.reduce(function(sum, v, i) {
    return i === 0 ? sum.concat(v) : sum.concat(v + sum[i-1]);
},[]);
console.log( fib  );

ES6:

var fibES6 = a.reduce(
    (sum, v, i) => i === 0 ? sum.concat(v) : sum.concat(v + sum[i-1])
, []);
console.log( fibES6  );