java - 递归方法计算数组中奇数的个数

Question

我需要编写一个递归方法来计算数组中奇数的数量。

这是我到目前为止的代码:

public static int countOdd(int[] numbers, int startIndex, int endIndex) {
    if (startIndex == endIndex) {
        if (numbers[startIndex] % 2 != 0) {
            return 1;
        } else {
            return 0;
        }
    } else {
        return countOdd(numbers, startIndex, endIndex - 1);
    }
}

Answer 1

您的递归行不正确:

return countOdd(numbers, startIndex, endIndex - 1);

您已经丢失了 endIndex 是否为奇数。这会有所帮助:

return countOdd(numbers, startIndex, endIndex - 1) + 
  countOdd(numbers, endIndex, endIndex); 

我不确定你的说法是否正确，我假设是:

countOdd(numbers, 0, numbers.length-1);

解释:为了理解如何实现它，您需要分解问题。如果我想递归地计算数组中的奇数:

[a, b, c, d, e, f, g, .... z]

上面的代码基本上是这样做的:

countOdd([a, b, c, d, e, f, g, ...y]) + countOdd([z])

请注意，第二个操作数将返回 0 或 1，因为子集的大小为 1。第一个操作数的长度基本上要小 1。继续递归:

countOdd([a, b, c, d.... x]) + countOdd([y]) + countOdd([z])
...
countOdd([a]) + countOdd([b]) + countOdd([c]) + ... countOdd([z])

一旦它们都是大小为 1 的子集，它就可以计算它。

 0 + 1 + 0 + 1 + 1 .. 

并返回奇数个数的求和结果。

额外说明:请注意，递归可以以不同的方式完成，但仍然会得到相同的结果(例如:

return countOdd(numbers, startIndex, startIndex) + 
  countOdd(numbers, startIndex + 1, endIndex);