把一个数组分成多个数组，在尾递归中怎么做？

Question

下面是将数字数组划分为子数组的代码

我使用了递归，

代码如下：

(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


})();

上述代码的输出为

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>

这里我传递变量'arrayOfArrays‘作为参数，这是我不喜欢做的。

我的问题是如何使用尾递归来解决上面的问题，这样就不需要传递参数'arrayOfArrays‘，而函数'divide’只返回一个新的数组'arrayOfArrays‘

Answer 1

您也可以使用简单的while循环和variable chunk-size实现这一点

演示

​

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

​

Answer 2

正如人们所指出的，尾递归可能是过度杀伤力。

但是，我不是尾递归的专家，但我认为下面可能是你想要的，注意对递归拆分的调用是最后一个返回函数，在函数调用中没有其他要求。因此，Javascript引擎应该能够清除堆栈。

​

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

​

Answer 3

下面是一个纯尾递归：

​

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

​