Recursion and array

Question

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

You can't use + with arrays. To concatenate arrays you need to use concat — GalAbra
– GalAbra, Commented Jul 26, 2019 at 20:56
This is not really "grouping", as you put the same value in two pairs. — trincot
– trincot, Commented Jul 26, 2019 at 21:03

antonku · Accepted Answer · 2019-07-26 23:19:34Z

3

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)

edited Jul 26, 2019 at 23:19

answered Jul 26, 2019 at 20:58

antonku

7,7252 gold badges18 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

trincot · Accepted Answer · 2019-07-26 21:26:37Z

1

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]));

edited Jul 26, 2019 at 21:26

answered Jul 26, 2019 at 20:58

trincot

357k38 gold badges282 silver badges338 bronze badges

Comments

user11779651 · Accepted Answer · 2019-07-26 21:15:29Z

1

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));
    }
}

answered Jul 26, 2019 at 21:15

user11779651

Comments

גלעד ברקן · Accepted Answer · 2019-07-27 12:08:10Z

0

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])))

answered Jul 27, 2019 at 12:08

גלעד ברקן

24k3 gold badges29 silver badges64 bronze badges

Collectives™ on Stack Overflow

Recursion and array

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related