Divide an array into array of arrays, how to do it in tail recursion?

Question

Below is the code which divides an array of numbers into array of sub-arrays

I have used recursion,

the code is as follows,

(function(){
    'use strict';

    mainFunction();

    function mainFunction(){
        var inputArray = [12,54,76,6,1,88,7,11,66];
        var arrayOfArrays = [];
        console.log("Input Array is ",inputArray);
        divide(inputArray,arrayOfArrays);
        console.log("Output Array is ",arrayOfArrays);
    } // end of mainFunction

    function divide(numArray,arrayOfArrays){
        var pivot = numArray.length/2,
            leftArray = undefined,
            rightArray = undefined;

        pivot = parseInt(pivot);

        if(pivot >= 1){
            leftArray = numArray.slice(0,pivot);
            rightArray = numArray.slice(pivot,numArray.length);

            if(leftArray.length > 2){
                divide(leftArray,arrayOfArrays);
            }else{
                arrayOfArrays.push(leftArray);  
            }

            if(rightArray.length > 2){
                divide(rightArray,arrayOfArrays);
            }else{
                arrayOfArrays.push(rightArray); 
            }
        }// end of if
    } // end of divide


})();

The output of the above code is

E:\DataStructuresAndAlgorithms\array>node divideArray01.js
Input Array is  [ 12, 54, 76, 6, 1, 88, 7, 11, 66 ]
Output Array is  [ [ 12, 54 ], [ 76, 6 ], [ 1, 88 ], [ 7 ], [ 11, 66 ] ]

E:\DataStructuresAndAlgorithms\array>

Here I am passing variable 'arrayOfArrays' as argument, which I don't like to do.

my question is how will solve the above problem using tail recurssion so that no need to pass argument 'arrayOfArrays' and the function 'divide' just returns a new array 'arrayOfArrays'

Rahul, any specific reason for going with recursion? Also, why is the output `[ 7 ], [ 11, 66 ]` and not `[ 7, 11 ], [ 66 ]`? — gurvinder372, Jan 30 '18 at 11:20
The out which you mentioned is also accepted. I don't want to use loops, and I want to better myself by trying tail recursion — Rahul Shivsharan, Jan 30 '18 at 11:25
You still need to return the value in intermediate steps and have the intermediate values passed as a parameter. Check this https://stackoverflow.com/questions/33923/what-is-tail-recursion?rq=1 — gurvinder372, Jan 30 '18 at 11:30
But tail-recursion seems to be an overkill for the choice of problem statement you are working on, I will give a simple `while` based solution. — gurvinder372, Jan 30 '18 at 11:31
@Rajesh, it looks the main problem is tail recusion, not just making chunks. — Nina Scholz, Jan 30 '18 at 14:44

score 0 · Answer 1 · answered Jan 30 '18 at 11:31

You can do so with a simple while loop and variable chunk-size as well

Demo

var arr = [ 12, 54, 76, 6, 1, 88, 7, 11, 66 ];
var chunkSize = 2;
var output = [];
var counter = 0;
while ( counter <= arr.length - 1 )
{
   output.push( arr.slice( counter, counter + chunkSize ) );
   counter += chunkSize;
}
console.log( output );

score 0 · Answer 2 · answered Jan 30 '18 at 11:38

0

As people have pointed out, tail recursion is maybe overkill.

But saying that, I'm no expert on tail recursion but I think the following might be what your after, notice how the call to the recursive split is the last return function, nothing else requires it in the function call. As such the Javascript engine should be able to clear down the stack.

const inputArray = [12,54,76,6,1,88,7,11,66];

function split(root, index = 0, output = []) {
  if (index < root.length) {
    output.push(index + 1 < root.length ?
      [root[index], root[index + 1]] :
      [root[index]]
     );
    return split(root, index + 2, output);
  } else {
    return output;
  }
}

console.log(split(inputArray));

answered Jan 30 '18 at 11:38

Keith

22,005
2
27
44

This includes the paramater, 'output', akin to 'arrayOfArrays', which the OP expressly asked to avoid. – גלעד ברקן Jan 30 '18 at 11:55
@גלעד ברקן I assume he's talking about invocation, as in `divide(numArray,arrayOfArrays)`, where as this is -> `split(inputArray)` – Keith Jan 30 '18 at 11:58
Seems to me he's talking about "passing variable 'arrayOfArrays' as argument." Since the function is recursive, each call is another "invocation." – גלעד ברקן Jan 30 '18 at 12:01
@גלעד ברקן Sorry, not sure what point your trying to make. Do you have a better solution?. `Here I am passing variable 'arrayOfArrays' as argument, which I don't like to do.`, that with this he doesn't need to do, maybe the OP could clarify. – Keith Jan 30 '18 at 12:08
Yes, I've posted a tail recursion without the 'output' variable. It sems to me that you've just renamed 'arrayOfArrays' to 'output' but it is used similarly as an accumulator. – גלעד ברקן Jan 30 '18 at 12:16

גלעד ברקן · Answer 3 · 2018-01-30T13:09:48.077

0

Here's a pure tail recursion:

function f(arr){
  if (!arr.length)
    return [];

  if (typeof arr[0] == 'object')
    return arr;
    
  if (typeof arr[arr.length-1] != 'object')
    arr = arr.slice(0);
    
  let next;
  
  if (typeof arr[1] == 'object')
    next = arr.splice(0,1);
  else
    next = arr.splice(0,2);

  arr.push(next);

  return f(arr);
}

var a = [12,54,76,6,1,88,7,11,66];

console.log(JSON.stringify(f(a)));
console.log(JSON.stringify(a));
console.log(JSON.stringify(f([])));

edited Jan 30 '18 at 13:09

answered Jan 30 '18 at 11:46

גלעד ברקן

23,602
3
25
61

This mutates the original array, is that what the OP wanted? – Keith Jan 30 '18 at 12:21
Just another small one. `[]` == `[[]]` rather than `[]` – Keith Jan 30 '18 at 12:34
@Keith what do you mean? – גלעד ברקן Jan 30 '18 at 12:38
If you set `a = []`, and run the script you will get `[[]]`, to me that would be wrong, for example if you now did `f(a).length` on this it would return 1, that to me is logically incorrect. IOW: if the question after running this was, how many splits are there, you would think `f(a).length` would give the correct result. – Keith Jan 30 '18 at 12:41

Nina Scholz · Answer 4 · 2018-01-30T13:36:44.410

0

You could take the following approach with extending arguments for an index for the actual position of splicing.

It takes a new array for calling the function again

array.slice(0, i).concat([array.slice(i, i + size)], array.slice(i + size)),
^^^^^^^^^^^^^^^^^                                                            grouped part
                         ^^^^^^^^^^^^^^^^^^^^^^^^^^                          new group
                                                     ^^^^^^^^^^^^^^^^^^^^^   rest of array

function divide(array, size, i = 0) {
    if (i >= array.length) {
        return array;
    }
    return divide(
        array.slice(0, i).concat([array.slice(i, i + size)], array.slice(i + size)),
        size,
        i + 1
    );
}

var array = [12, 54, 76, 6, 1, 88, 7, 11, 66];

console.log(divide(array, 2));
console.log(array);

.as-console-wrapper { max-height: 100% !important; top: 0; }

edited Jan 30 '18 at 13:36

answered Jan 30 '18 at 12:25

Nina Scholz

376,160
25
347
392

Your solution uses the extra parameter 'arrayOfArrays' as an accumulator, which the OP asked to avoid. You're just hiding its invocation with a default. I agree in general that referencing the original over slicing may be more efficient in general, though. – גלעד ברקן Jan 30 '18 at 12:36
With your edit, you are now mutating the original array.. :( I personally think the OP avoid `arrayOfArrays` is to do with the initial call, but we really need to wait for the OP to clarify,.. – Keith Jan 30 '18 at 12:59
@Keith, acutally a copy is taken and used. – Nina Scholz Jan 31 '18 at 07:28
It does now, but not when I posted the comment. – Keith Jan 31 '18 at 09:59
@Keith, that's why i added the comment. – Nina Scholz Jan 31 '18 at 10:04
Yes, maybe your comment was just worded slightly wrong. (actually), implies I was mistaken, you maybe meant to say I've modified and it's now making a copy. ps. I personally think your first post was the better option, I might be bias as it was similar to mine. :) – Keith Jan 31 '18 at 10:07

Divide an array into array of arrays, how to do it in tail recursion?

4 Answers4