Recursively square each number in an array

Admin 1
Viewed 224

I came up with the following solution for returning an array of squared numbers, sorted in ascending order.

function sortedSquaredArray(array) {
    let squaredArray = [];
    for(i=0;i<array.length;i++){
        squaredArray.push(array[i] ** 2);
    }
  return squaredArray.sort((a,b) => a-b);
}

I'm trying to get better at writing recursions, so I'm attempting to turn the above into a pure recursive function (with no inner function).

This is my attempt.

function sortedSquaredArray(array) {
    let squaredArray = [];
    squaredArray.push(array[0] ** 2);
    
    if(array.length) sortedSquaredArray(array.shift());

    return squaredArray.sort((a,b) => a-b);
}

I believe its the sortedSquaredArray(array.shift()) that's causing this to fail.. I thought about using .slice and .concat somehow, but struggling to wrap my head around it.

What am I missing?

recursion javascript
2 Answers

.shift returns the removed element - it doesn't return the array after being mutated.

For proper recursion, you also either need to pass along the array as a parameter, or create it during the final iteration and return it back for the prior callers to insert their items into.

So that you only sort at the end, I'd recommend passing it as a parameter, so that the final call with no recursion can sort.

function sortedSquaredArray(input, squares = []) {
  if (!input.length) {
    return squares.sort((a, b) => a - b);
  }
  squares.push(input.pop() ** 2);
  return sortedSquaredArray(input, squares);
}


function sortedSquaredArray(input, squares = []) {
  if (!input.length) {
    return squares.sort((a, b) => a - b);
  }
  squares.push(input.pop() ** 2);
  return sortedSquaredArray(input, squares);
}

console.log(sortedSquaredArray([2, 4, 1]));

A similar option that doesn't mutate the parameter:

function sortedSquaredArray(input, squares = []) {
  if (!input.length) {
    return squares.sort((a, b) => a - b);
  }
  const [firstItem, ...rest] = input;
  squares.push(firstItem ** 2);
  return sortedSquaredArray(rest, squares);
}

or

function sortedSquaredArray(input, squares = []) {
  if (!input.length) {
    return squares.sort((a, b) => a - b);
  }
  squares.push(input[0] ** 2);
  return sortedSquaredArray(input.slice(1), squares);
}

If you want just one parameter, then do the other approach I mentioned - create the array during the final iteration and return it back up:

const recurse = (input) => {
  if (!input.length) {
    return [];
  }
  const square = input.pop() ** 2;
  return sortedSquaredArray(input).concat(square);
  
};

function sortedSquaredArray(input) {
  return recurse(input).sort((a, b) => a - b);
}

console.log(sortedSquaredArray([2, 4, 1]));

user_95152070

I would separate the sorting from the squaring, since the squaring might be useful on its own. This is a useful way to do this sort of recursion for smallish problems:

const squaredArray = ([n, ...ns]) =>
  n == undefined
    ? []
    : [n * n, ... squaredArray (ns)]

const sortedSquaredArray = (ns) =>
  squaredArray (ns) .sort ((a, b) => a - b)

console .log (sortedSquaredArray ([4, 9, 2, 5, 8]))

user_12436410
Related