c++ - 这是进行递归的有效方法(好风格)吗

Question

除了这段代码效率极低之外，我在这里编写递归函数的方式是否被认为是“好的风格”。例如，我正在做的是创建一个包装器，然后将其传递给 int mid 和一个计数器 int count。

此代码的作用是从数组中获取值，然后查看该值与 blockIndex 的组合是否大于 mid。那么，除了效率低下之外，我还能找到一份编写这样的递归函数的工作吗？

int NumCriticalVotes :: CountCriticalVotesWrapper(Vector<int> & blocks, int blockIndex)
{

    int indexValue = blocks.get(blockIndex);
    blocks.remove(blockIndex);
    int mid = 9;

    return CountCriticalVotes(blocks, indexValue, mid, 0);
}


int NumCriticalVotes :: CountCriticalVotes(Vector<int> & blocks, int blockIndex, int mid, int counter)
{
    if (blocks.isEmpty())
    {
        return counter;
    }

    if (blockIndex + blocks.get(0) >= mid)
    {
        counter += 1;
    } 

    Vector<int> rest = blocks;
    rest.remove(0);
    return CountCriticalVotes(rest, blockIndex, mid, counter);
}

Answer 1

这在适用于足够小的集合的范围内是有效的。

但是，它的效率非常低——对于每个递归调用，您都在创建 Vector 的整个未计数部分的拷贝。因此，如果您计算一个包含 1000 个项目的 vector ，您将首先创建一个包含 999 个项目的 vector ，然后创建另一个 998 个项目，然后另一个 997 个项目，依此类推，一直到 0 个项目。

这本身就很浪费，但似乎更糟。然后您要从 Vector 中删除一个项目——但您要删除的是第一个 项目。假设您的 Vector 类似于 std::vector，移除最后一项需要常数时间，但移除第一项需要线性时间——即，移除第一项，之后的每一项都会移动“前进”进入腾出的位置。

这意味着您的算法不是采用常数空间和线性时间，而是在空间和时间上都是二次的。除非所涉及的集合非常小，否则会相当浪费。

我不会为每次调用创建一个全新的 Vector，而是将偏移量传递到现有 Vector。这将避免复制和删除项目，因此使其在时间和空间上都呈线性非常简单(这仍然远未达到最佳状态，但至少不像二次方那么糟糕)。

为了进一步减少使用的空间，将数组视为两半。分别数每一半，然后将结果加在一起。这会将递归深度减少到对数而不是线性，这通常相当相当大(例如，对于 1000 个项目，它的深度大约是 10 而不是大约 1000。对于一百万个项目，深度上升到大约 20 而不是 100 万)。