CODEWITHSUNDEEP
javascriptalgorithmrecursiontail-recursion
queques
queques

Reputation: 21

How do I turn this recursion into tail recursion?

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.

Upvotes: 2

Views: 118

Answers (1)

trincot
trincot

Reputation: 351369

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

Upvotes: 2

Related Questions