CODEWITHSUNDEEP
javascriptarraysrecursion
Max Van de Velde
Max Van de Velde

Reputation: 27

Recursion and array

I have to group an given array by sets of 2 using recursion, whenever i return my answer is not in an array

I've created an array then returning that array

input: [5,1,4,2,3]

function pairs(xs) {
    if (xs.length <= 1){
        return [];
    } else {

        let [first,second,...rest] = xs;
        let result = [first,second];
        let newxs = xs.slice(1);
        return [result] + pairs(newxs);
    }
}

Expected output: [[5, 1], [1, 4], [4, 2], [2, 3]]

Actual output: 5,11,44,22,3

Upvotes: 1

Views: 106

Answers (4)

גלעד ברקן
גלעד ברקן

Reputation: 23955

Note that JavaScript array slice makes a new copy of the segment each time it's called. If you want to be a bit more efficient about it, use indexing. Something like:

function f(A, i=0){
  if (i >= A.length - 1)
    return []

  return [[A[i], A[i+1]]].concat(f(A, i + 1))
}

console.log(JSON.stringify(f([5, 1, 4, 2, 3])))

Upvotes: 0

antonku
antonku

Reputation: 7685

You can fix the function by using the spread operator instead of the +:

function pairs(xs) {
  if (xs.length <= 1){
    return [];
  } else {
    let [first, second,] = xs;
    let result = [first,second];
    let newxs = xs.slice(1);
    return [result, ...pairs(newxs)];
  }
}


const result = pairs([5,1,4,2,3]);
console.log(result)

Upvotes: 3

trincot
trincot

Reputation: 351384

The mistake is the +. Arrays don't add up like that. The + will convert the array-operands to strings and then concatenate those. Instead use spread syntax or concat to concatenate arrays.

But for the recursive part, I would make two recursive calls, each on one half of the array. That way your recursion stack will use O(logn) space instead of O(n), which is a good safety against stack overflow. See the difference with for instance an array with 100 000 values.

function pairs(xs) {
    if (xs.length <= 1){
        return [];
    } else {
        let i = xs.length >> 1;
        return [...pairs(xs.slice(0, i)),
                xs.slice(i-1, i+1),
                ...pairs(xs.slice(i))];
    }
}

console.log(pairs([5, 1, 4, 2, 3]));

Upvotes: 1

Ruchit Parikh
Ruchit Parikh

Reputation: 23

You can concat both array using concat function like this

function pairs(xs) {
    if (xs.length <= 1){
        return [];
    } else {

        let [first,second,...rest] = xs;
        let result = [first,second];
        let newxs = xs.slice(1);
        return [result].concat(pairs(newxs));
    }
}

Upvotes: 1

Related Questions