Can someone debug this code? I cannot for the life of me find the (run-time) error:

function generate_fibonacci(n1, n2, max, out){
    var n = n1+n2;
    if(n<max){
        out.push(n);
        generate_fibonacci(n2, n, max, out);
    }
}

function generate_fibonacci_sequence(max){
    var out = [1];
    generate_fibonacci(0, 1, max, out);
    return out;
}

function remove_odd_numbers(arr){
    for (var i = 0; i < arr.length; i++) {
        if(!(arr[i]%2==0)){
            arr.splice(i, 1);
        }
    }
    return arr;
}

function sum(array){
    var total = 0;
    for (var i = 0; i < array.length; i++) {
        total+=array[i];
    }
    return total;
}

var fib_sq = generate_fibonacci_sequence(4000000);

console.log("Before: " + fib_sq);

remove_odd_numbers(fib_sq);

console.log("After: " + fib_sq);

console.log("WTH?: " + remove_odd_numbers([1,2,3,4,5,6,7,8,9]));

Output:

Before: 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578
After: 1,2,5,8,21,34,89,144,377,610,1597,2584,6765,10946,28657,46368,121393,196418,514229,832040,2178309,3524578
WTH?: 2,4,6,8
[Finished in 0.3s]

I'm going crazy or something. For some reason, all odd numbers are not being removed. But as you can see at the end, it works perfectly. I have no idea what is going on.

Can someone debug this code? I cannot for the life of me find the (run-time) error:

function generate_fibonacci(n1, n2, max, out){
    var n = n1+n2;
    if(n<max){
        out.push(n);
        generate_fibonacci(n2, n, max, out);
    }
}

function generate_fibonacci_sequence(max){
    var out = [1];
    generate_fibonacci(0, 1, max, out);
    return out;
}

function remove_odd_numbers(arr){
    for (var i = 0; i < arr.length; i++) {
        if(!(arr[i]%2==0)){
            arr.splice(i, 1);
        }
    }
    return arr;
}

function sum(array){
    var total = 0;
    for (var i = 0; i < array.length; i++) {
        total+=array[i];
    }
    return total;
}

var fib_sq = generate_fibonacci_sequence(4000000);

console.log("Before: " + fib_sq);

remove_odd_numbers(fib_sq);

console.log("After: " + fib_sq);

console.log("WTH?: " + remove_odd_numbers([1,2,3,4,5,6,7,8,9]));

Output:

Before: 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578
After: 1,2,5,8,21,34,89,144,377,610,1597,2584,6765,10946,28657,46368,121393,196418,514229,832040,2178309,3524578
WTH?: 2,4,6,8
[Finished in 0.3s]

I'm going crazy or something. For some reason, all odd numbers are not being removed. But as you can see at the end, it works perfectly. I have no idea what is going on.

• javascript

• What's the actual error? – Ja͢ck Commented Aug 19, 2013 at 1:55
• For my fib_sq, all odd numbers are not being removed. Look at the output, specifically "After." Can you run the code? – user2316667 Commented Aug 19, 2013 at 1:58
• You're talking about a (run-time) error; typically that refers to an error thrown by JavaScript itself. I think what you meant is that you get an unexpected result. – Ja͢ck Commented Aug 19, 2013 at 1:59
• Ah, I appreciate the clarification! – user2316667 Commented Aug 19, 2013 at 2:10

5 Answers 5

The problem in the original code is that when you remove the first 1 at index 0, the array gets shifted; now arr[i] is contains the second 1; but you just step over it.

You need to use while instead of if here, or copy to a separate list. This is an example for splicing:

function remove_odd_numbers1(arr){
    for (var i = 0; i < arr.length; i++) {
        // here
        while (arr[i] % 2) {
            arr.splice(i, 1);
        }
    }
    return arr;
}

But it will be slow though. Better to create a new array:

function remove_odd_numbers2(arr){
    var rv = [];
    for (var i = 0; i < arr.length; i++) {
        if (! (arr[i] % 2)) {
            rv.push(arr[i]);
        }
    }
    return rv;
}

Generally the best algorithm however is to use the same array, if the original is not needed, so that no extra memory is required (though on javascript this is of a bit dubious value):

function remove_odd_numbers3(arr){
    var out = 0; 
    for (var i = 0; i < arr.length; i++) {
        if (! (arr[i] % 2)) {
            arr[out++] = arr[i]; 
        }
    }
    arr.length = out;
    return arr;
}

Notice however that unlike the splice algorithm, this runs in O(n) time.

Also, the Array.prototype.filter() is not bad, being a builtin. It also creates a new array and thus is parable to the 2.

Here is a really simple, fast way to do it. Using your data, it only took 48ms to plete. Hope this helps..

function noOdds(values){
  return values.filter(function (num) {
    return num % 2 === 0;
  });
}

I'm not sure about this, however I doubt using splice is efficient pared to creating a new array.

function remove_odd_numbers(arr) {
    var notOdd = [],
        i = 0,
        len = arr.length,
        num;

    for (; i < len; i++) {
        !((num = arr[i]) % 2) && notOdd.push(num);
    }

    return notOdd;
}

EDIT: You should probably use the native filter function, as suggested by @Jack. I leave this answer as a reference.

Because splice() modifies the array, your index will be off in the next iteration; you need to either decrease the loop variable, use a while loop like Antti proposed or iterate backwards like Crazy Train mentioned.

That said, the use of splice() is awkward to work with because it modifies the array in-place. This functionality can be easily acplished using a filter function as well:

function remove_odd_numbers(arr) 
{
    return arr.filter(function(value) {
        return value % 2 == 0;
    });
}

This creates and returns a new array with only the even values.

Given the recency of this function, check the patibility section how to handle browsers IE < 9. Many popular libraries, such as jQuery, underscore, etc. take care of this for you.

Update

Instead of filtering the array afterwards, it would be more memory efficient to only add the even values as you perform the recursion:

function generate_fibonacci(previous, current, max, callback)
{
    var next = previous + current;

    if (next < max) {
        callback(next);
        generate_fibonacci(current, next, max, callback);
    }
}

function generate_fibonacci_sequence(max, callback)
{
    callback(1);
    callback(1);
    generate_fibonacci(1, 1, max, callback);
}

var out = [];
generate_fibonacci_sequence(4000000, function(value) {
    if (value % 2 == 0) {
        out.push(value);
    }
});

Instead of passing the out array, I'm passing a function to be called whenever a new sequence value is generated; the filtering is done inside that callback.

ES6 version from "Tabetha Moe" answer

function noOdds(arr) {
    return arr.filter(value => value % 2 === 0);
}