将多个递归调用转换为尾递归 [英] Convert multiple recursive calls into tail-recursion

问题描述

只是想知道这样的函数是否可以尾递归完成.我觉得这很困难，因为它会调用自己两次.

Just wondering if a function like this can be done tail-recursively. I find it quite difficult because it calls itself twice.

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

Here is my non-tail-recursive implementation in javascript. (Yes I know most javascript engine doesn't support TCO, but this is just for theory.) The goal is to find all sublists of a certain length(size) of a given array(arr). Ex: getSublistsWithFixedSize([1,2,3] ,2) returns [[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);
}

推荐答案

这是我借助累加器的解决方案.它远非完美，但确实有效.

Here is my solution with the help of an accumulator. It's far from perfect but it works.

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

这篇关于将多个递归调用转换为尾递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！