将多个递归调用转换为尾部递归

Question

我只是想知道这样的函数是否可以递归地完成。我觉得很难，因为它自己叫了两次。

这是我在javascript中的非尾部递归实现。（是的，我知道大多数javascript引擎不支持TCO，但这只是理论上的。）目标是找到给定数组（arr）中具有特定长度（大小）的所有子列表。例如：getSublistsWithFixedSize（[1,2,3]，2）返回[[1,2]、[1,3]、[2,3]]

function getSublistsWithFixedSize(arr, size) {
    if(size === 0) {
        return [[]];
    }
    if(arr.length === 0 ) {
        return [];
    }
    let [head, ...tail] = arr;
    let sublists0 = getSublistsWithFixedSize(tail, size - 1);
    let sublists1 = getSublistsWithFixedSize(tail, size);
    let sublists2 = sublists0.map(x => {
        let y = x.slice();
        y.unshift(head);
        return y;
    });

    return  sublists1.concat(sublists2);
}

Answer 1

这是我借助累加器的解决方案。虽然还远远不够完美，但它确实有效。

function getSublistsWithFixedSizeTailRecRun(arr, size) {
    let acc= new Array(size + 1).fill([]);
    acc[0] = [[]];
    return getSublistsWithFixedSizeTailRec(arr, acc);
}


function getSublistsWithFixedSizeTailRec(arr, acc) {
    if(arr.length === 0 ) {
        return acc[acc.length -1];
    }
    let [head, ...tail] = arr;
    //add head to acc
    let accWithHead = acc.map(
        x => x.map(
            y => {
                let z = y.slice()
                z.push(head);
                return z;
            }
        )
    );
    accWithHead.pop();
    accWithHead.unshift([[]]);

    //zip accWithHead and acc
    acc = zipMerge(acc, accWithHead);

    return getSublistsWithFixedSizeTailRec(tail, acc);
}

function zipMerge(arr1, arr2) {
    let result = arr1.map(function(e, i) {
        return uniq(e.concat(arr2[i]));
    });
    return result;
}

Answer 2

一种这样的方法是使用延续传递样式。在这种技术中，将一个附加参数添加到您的函数中以指定如何继续计算

下面我们用/**/强调每个尾部调用

function identity(x) {
/**/return x;
}

function getSublistsWithFixedSize(arr, size, cont = identity) {
    if(size === 0) {
/**/   return cont([[]]);
    }
    if(arr.length === 0 ) {
/**/    return cont([]);
    }
    let [head, ...tail] = arr;
/**/return getSublistsWithFixedSize(tail, size - 1, function (sublists0) {
/**/    return getSublistsWithFixedSize(tail, size, function (sublists1) {
            let sublists2 = sublists0.map(x => {
                let y = x.slice();
                y.unshift(head);
                return y;
            });
/**/        return cont(sublists1.concat(sublists2));
        });
    });
}

console.log(getSublistsWithFixedSize([1,2,3,4], 2))
// [ [ 3, 4 ], [ 2, 4 ], [ 2, 3 ], [ 1, 4 ], [ 1, 3 ], [ 1, 2 ] ]