使用递归函数查找数组的最小数字

Question

我有一个作业需要使用 递归函数 找到数组中的最小数字。需要明确的是：我已经获得了一个可行的解决方案。我只是为了我的生活无法弄清楚为什么我自己的算法不起作用。

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]

这段代码returns 1 而不是零...我的思路是这样的：

首先检查列表长度是否为1，如果是return其中唯一的元素
如果不是：将列表中的第一个元素与第二个元素进行比较，删除最大的元素。新列表再次放入函数中以使其递归。
这一直持续到列表实际长度为 1，然后函数将 return 最小的数字。

为什么这个 return 是 1 而不是 0？

希望有人能帮忙亲切的问候！

Answer 1

需要在调用外进行拼接，因为Array#splice returns删除数组元素

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

也许另一种方法会更好，方法是分离第一个元素并获取数组的其余部分。

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

Answer 2

而不是 Array.slice() 和 Array.splice，您可以使用 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]);
    }
}

或

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

使用递归函数查找数组的最小数字

Finding the smallest number of an Array using a recursive function

javascript

arrays

recursion

minimum