How do I turn this recursion into tail recursion?-CodePudding

With given array on unique numbers which are always greater than 0 I need to find all possible unique combinations of those numbers that are equal to a certain number when summed.

For example, getNumberComponents([7, 4, 3, 2, 5, 6, 8, 1], 8) should return

[ [ 7, 1 ], [ 4, 3, 1 ], [ 3, 5 ], [ 2, 5, 1 ], [ 2, 6 ], [ 8 ] ] because sum of all numbers in every subarray equals 8.

My solution:

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

But I wonder if it's possible to use tail recursion for that? I have no idea how to turn my solution into tail recursion.

CodePudding user response：

Here is my version of your function, but using tail recursion. This is still a complex subject for me, check if there are no mistakes

function getNumberComponents(numArray, number, currentIndex = 0, currentVariant = [], allVariants = new Set()) {
    if (currentIndex >= numArray.length) {
        const currentSum = currentVariant.reduce((acc, cur) => acc   cur, 0);
        if (currentSum === number) {
            allVariants.add(currentVariant);
        }
        return Array.from(allVariants);
    }
    const currentElement = numArray[currentIndex];
    const currentSum = currentVariant.reduce((acc, cur) => acc   cur, 0);
    const sumWithCurrent = currentSum   currentElement;
    if (sumWithCurrent <= number) {
        allVariants = new Set([...allVariants, ...getNumberComponents(numArray, number, currentIndex   1, [...currentVariant, currentElement], allVariants), ...getNumberComponents(numArray, number, currentIndex   1, currentVariant, new Set())]);
    } else {
        allVariants = new Set([...allVariants, ...getNumberComponents(numArray, number, currentIndex   1, currentVariant, new Set())]);
    }
    return Array.from(allVariants);
}

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

CodePudding user response：

To make this tail recursive, you could:

Keep track of all indices that were selected to arrive at the current sum. That way you can easily replace a selected index with the successor index.
In each execution of the function get the "next" combination of indices. This could be done as follows:
- If the sum has not been achieved yet, add the index the follows immediately after the most recently selected index, and adjust the sum
- If the sum has achieved or exceeded, remove the most recently selected index, and then add the successor index instead, and adjust the sum
- If there is no successor index, then forget about this index and replace the previous one in the list, again adjusting the sum
- If there are no more entries in the list of indices, then all is done.
Instead of accumulating a sum, you could also decrease the number that you pass to recursion -- saving one variable.
Make the function return the array with all variants, so there is no need for an inner function, nor any action that follows the function call.

Here is an impementation:

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