Recursively square each number in an array

Question

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?

Does this answer your question? [Javascript recursive array flattening](https://stackoverflow.com/questions/30048388/javascript-recursive-array-flattening) — JΛYDΞV, Mar 28 '21 at 02:19

CertainPerformance · Accepted Answer · 2021-03-27T05:16:54.220

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

Thank you. This is very interesting.. I never thought of storing the values in a parameter. I'm seriously mindblown how you came up with solutions so quickly. If I may ask, how would the function look like if with just one parameter `input`, without `squares = []`? I tried a variation where I have a constant inside the function, but the value gets reset by the recursive call (expected), and I'm not sure how to escape it unless I create an inner function to separate scopes. — , Mar 27 '21 at 05:14
See edit, take the other approach I mentioned at first - create the array at the final iteration and return it for the others to push to — CertainPerformance, Mar 27 '21 at 05:17
You could put it all in one function instead of two, but one function would be inefficient since I think you'd have to `.sort` on each iteration, instead of only once — CertainPerformance, Mar 27 '21 at 05:19

score 0 · Answer 2 · answered Mar 28 '21 at 01:14

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

Recursively square each number in an array

2 Answers2