I have an assignment where I need to find the smallest number in an array using a recursive function. To be clear: I have been provided a working solution. I just for the life of me can't figure out why my own algorithm doesn't work.

function minimum(ns) {
    if (ns.length === 1) {
        return ns[0];
    }
    else {
        const first = ns[0]
        const second = ns[1]
        if (first >= second) {
            return minimum(ns.slice(1))
        }
        else {
            return minimum(ns.splice(1,1))
        }
    }
}

minimum([0, 1]

<iframe name="sif1" sandbox="allow-forms allow-modals allow-scripts" frameborder="0"></iframe>

This code returns 1 instead of zero... My thinking goes as follows:

1. First check if the list length is 1, if so return the only element in it
2. If not: compare the first element in the list with the second, the largest element gets removed. The new list gets put into the function again to make it recursive.
3. This goes on until the list is actually of length 1 and the function will then return the smallest number.

Why does this return 1 instead of 0?

Hope someone can help Kind regards!

CodePudding user response：

You need to splice outside of the call, because Array#splice returns the deleted elemenst of the array.

function minimum(ns) {
    if (ns.length === 1) return ns[0];

    const first = ns[0]
    const second = ns[1]
    if (first >= second) return minimum(ns.slice(1));
    ns.splice(1, 1);
    return minimum(ns);
}

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

<iframe name="sif2" sandbox="allow-forms allow-modals allow-scripts" frameborder="0"></iframe>

Mabe another approach would help better by separating the first element and take the rest of the array.

function minimum([first, ...ns]) {
    if (ns.length === 0) return first;
    if (first >= ns[0]) return minimum(ns);
    return minimum([first, ...ns.slice(1)]);
}

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

<iframe name="sif3" sandbox="allow-forms allow-modals allow-scripts" frameborder="0"></iframe>

CodePudding user response：

Rather than Array.slice() and Array.splice, you can use destructuring assignment:

function minimum(ns)
{
    if (ns.length === 1)
    {
        return ns[0];
    }
    const [first, second, ...tail] = ns;
    if (first >= second)
    {
       return minimum([second, ...tail]);
    } else {
       return minimum([first, ...tail]);
    }
}

or

function minimum(ns)
{
    if (ns.length === 1) return ns[0];
    const [first, second, ...tail] = ns;
    return minimum([(first >= second?second:first), ...tail]);
}

console.log(minimum([1]));
console.log(minimum([3,1,2]));
console.log(minimum([3,2,2,3,4]));

<iframe name="sif4" sandbox="allow-forms allow-modals allow-scripts" frameborder="0"></iframe>