# How would you count in the Fibonacci Sequence?

I was wondering if I did this in a remotely acceptable way:

var fib = function(params) {
var iterations = params;
var output = [0];

for(var i = 1, j = 1; j < iterations; j++){
//i is the fibonacci sequence
//j counts iterations
output.push(i);
i = parseInt(output[j]) + parseInt(output[j-1]);

}
console.log(output[iterations-1]);
}

fib("4");


Here the function takes in a parameter (eg 4), then a for loop counts through and adds every Fibonacci number until that iteration to an array (so in this example, 4 values are in the output array).

Mostly I'd just like to know if you guys would reach a similar conclusion and if I did anything that's a huge no-no, particularly using output[iterations-1] to force the counter to be at the same point as the array (due to 0th index) seems iffy.

var fib = function(params) {
var iterations = params;


Why are you copying params into iterations, rather than just naming your parameter iterations?

    var output = [0];


That's not really your output is it? Perhaps there is a better name?

    for(var i = 1, j = 1; j < iterations; j++){
//i is the fibonacci sequence
//j counts iterations
output.push(i);
i = parseInt(output[j]) + parseInt(output[j-1]);


Output already contains ints. There is no reason to parseInt it. Why don't you directly push on the array rather then storing it in an int? Furthermore, you don't actually need an array, you only need the last two elements.

    }
console.log(output[iterations-1]);


Fix the indent here. }

fib("4");


Why are you passing a string?

• 1) Good point, fixed. 2) How else would you name outputs in this usecase? I'm not sure if I see value in that 3) How would I do this without an array, using two seperate variables? 4) The indent appears fine for me - should it be somewhere other than in line with the for that it's ending? 5) I've had issues in the past with "unexpected number" errors, though on testing it doesn't happen here so I need to further test the cause of that. Sorry for the edit, I didn't release enter would send the comment here (doh). Jun 3, 2014 at 15:41
• Also, the parseInt is because sometimes it'll concatenate the numbers together. I'll look into the conditions so that I can be more strict on my parseInt usage though. Jun 3, 2014 at 15:47
• Speaking of naming, why not give the variables meaningful names instead of adding a comment? Jun 3, 2014 at 16:24
• @JoeCollins 2)I'd probably call it fibonacci to indicate that it holds that sequence. 3) One variable holds the last number, and another holds the second last number. In each iteration calculate the new last number as the sum of them, and the second last number becomes the previous last number. 4) See your question above, the indentation is off there. Probably you have a mix of tabs and spaces in your file. 5) You should at most need to parseInt once at the beginning to make sure you are dealing with ints. Its very suspect to do it in a loop like this. Jun 3, 2014 at 17:22
• Also, suspect to use parseInt without passing it a radix argument Jun 4, 2014 at 1:38

First: Upvote Winston Ewert's answer because it's a great and precise review. This is just me trying to illustrate it a bit.

Incorporating Winston's suggestions (somewhat naïvely) into the original code:

function fib(iterations) {
var previous = 0,
current  = 1,
temp, i;

iterations = parseInt(iterations, 10);

for(i = 0 ; i < iterations ; i++) {
temp = current;
current = previous + current;
previous = temp;
}

console.log(current);
}


I'd skip the parseInt, though, because for a function like this, I'd say it's the caller's responsibility to pass proper arguments; Garbage In, Garbage Out. I'd also favor just returning the number, and letting the caller handle the logging.

Doing that, and using an array in the code above, one can write:

function fib(iterations) {
var tail = [0, 1], i;
for(i = 0 ; i < iterations ; i++) {
tail = [tail[1], tail[0] + tail[1]];
}
return tail[1];
}


Or:

function fib(iterations) {
var tail = [0, 1], i;
for(i = 0 ; i < iterations ; i++) {
tail[0] += tail[1];
tail.reverse();
}
return tail[1];
}


Or (needlessly):

function fib(iterations) {
function step(a, b) {
return [b, a + b];
}

var tail = [0, 1], i;
for(i = 0 ; i < iterations ; i++) {
tail = step.apply(null, tail);
}
return tail[1];
}


Et cetera, et cetera ad absurdum

It would be a better design for the function to return a value, rather than outputting it using console.log(). That lets you reuse the code, as the caller has the flexibility to do something else with the result, such as setting the value of a text field to it.

Since you are only interested in outputting the nth element of the Fibonacci Sequence, there is no sense in storing the entire Fibonacci Sequence up to that point. All you need is three variables: the two most recent elements, and an iteration counter. (In technical terms, you're using O(n) space for the computation, when it could be done using just O(1) space.)

/**
* Returns the nth element of the Fibonacci sequence, where fib(1) = 0.
* nth must be at least 1.
*/
function fib(nth) {
var a = 1, b = 0;
while (nth-- > 0) {
var c = a + b;
a = b;
b = c;
}
return a;
}


Had you been interested in returning the first n elements rather than just the nth element, then it would make sense to build the array. In that case, it would be better to pre-allocate the entire array, since you know exactly how long it should be. Your current implementation appends one element at a time, forcing the interpreter to guess at how much contiguous memory is needed for the array; every time it underestimates, it needs to reallocate memory and possibly copy the intermediate results.

function fib(length) {
var result = new Array(length);
if (length > 0) result[0] = 0;
if (length > 1) result[1] = 1;
for (var i = 2; i < length; i++) {
result[i] = result[i - 2] + result[i - 1];
}
return result;
}