javascript - 如何将这个递归变成尾递归？

Question

对于始终大于 0 的唯一数字的给定数组，我需要找到这些数字的所有可能的唯一组合，这些数字在求和时等于某个数字。

例如，getNumberComponents([7, 4, 3, 2, 5, 6, 8, 1], 8) 应返回

[ [ 7, 1 ], [ 4, 3, 1 ], [ 3, 5 ], [ 2, 5, 1 ], [ 2, 6 ], [ 8 ] ] 因为每个子数组中所有数字的总和等于8。

我的解决方案:

function getNumberComponents(numArray, number) {
    const arrayLength = numArray.length;
    const allVariants = [];

    function findComponents(currentIndex = 0, currentVariant = []) {
        while (currentIndex < arrayLength) {
            const currentElement = numArray[currentIndex];

            const currentSum = currentVariant.reduce((acc, cur) => acc + cur, 0);

            const sumWithCurrent = currentSum + currentElement;

            if (sumWithCurrent === number) {
        allVariants.push([...currentVariant, currentElement]);
            }

            currentIndex++;

            if (sumWithCurrent < number) {
                findComponents(currentIndex, [...currentVariant, currentElement]);
            }
        }
    }
    
    findComponents();
    
    return allVariants;
}

但我想知道是否可以使用尾递归？我不知道如何将我的解决方案变成尾递归。

Answer 1

要使此尾部递归，您可以:

• 跟踪为得出当前总和而选择的所有指数。这样您就可以轻松地将选定索引替换为后继索引。

• 在函数的每次执行中，获取“下一个”索引组合。这可以按如下方式完成:

  • 如果尚未达到总和，则在最近选择的索引之后添加紧随其后的索引，并调整总和
  • 如果总和已达到或超过，则删除最近选择的索引，然后添加后继索引，并调整总和
  • 如果没有后继索引，则忽略该索引并替换列表中的前一个索引，再次调整总和
  • 如果索引列表中没有更多条目，则一切都已完成。

• 除了累加总和之外，您还可以减少传递给递归的数字——保存一个变量。

• 使函数返回包含所有变体的数组，因此不需要内部函数，也不需要跟随函数调用的任何操作。

这是一个实现:

function getNumberComponents(numArray, number, selectedIndices=[], allVariants=[]) {
    let i = selectedIndices.at(-1)??-1;
    if (number < 0) { // Sum is too large. There's no use to adding more
        i = numArray.length; // Force the while-condition to be true
    } else if (number == 0) { // Bingo
        allVariants.push(selectedIndices.map(idx => numArray[idx]));
    }
    while (++i >= numArray.length) { // No more successor index available
        if (selectedIndices.length == 0) return allVariants; // All done
        i = selectedIndices.pop(); // Undo a previous selection
        number += numArray[i]; // Remove from sum
    }
    selectedIndices.push(i); // Select index and recur:
    return getNumberComponents(numArray, number - numArray[i], selectedIndices, allVariants);
}

console.log(getNumberComponents([7, 4, 3, 2, 5, 6, 8, 1], 8));