数字在数组中出现的次数 [英] Number of times number appears in an array

问题描述

我在C ++书中找到一个练习：写一个函数来计算一个数字在数组中出现的次数。一切都很好，程序是工作。但是该练习还表示函数应该是递归的。

I found an exercise in a C++ book that says "Write a function that will count the number of times a number appears in an array.". Everything is fine, the program is working. But the exercise also says that the function should be recursive.

如何使递归函数像这样工作？

How can I make a recursive function working like this?

#include <iostream>

int count(int number, int array[], int length)
{
    int counter = 0; 
    for(int i = 0; i < length; i++)
        if(array[i] == number)
            counter++;
    return counter;
}

int main()
{
    int numbers[10] = {3,4,1,2,4,5,6,5,4,5};
    int number_to_search = 5;
    std::cout << number_to_search << " appears "
              << count(number_to_search, numbers, 10)
              << " times in the array.";
    return 0;
}

推荐答案

你现在，返回 0 + recursive_step 或 1 + recursive_step ，其中 recursive_step 是对 count（...）的调用，其中增加了数组指针并减少了 length 。 length == 0 ，此时您只需返回 0 。

Instead of the loop and counter you have now, return 0 + recursive_step or 1 + recursive_step, where recursive_step is a call to count(...) where you have increased the array pointer and decreased length. Your base case is when length == 0, at which point you just return 0.

一个很好的理解递归的方法是研究如何进行计算，一步一步。在你的例子中，你会做这样的：

A nice way of understanding recursion is to study how the calculation is carried out, step by step. In your example you will do something like this:

count(5, {3,4,1,2,4,5,6,5,4,5})
0+count(5, {4,1,2,4,5,6,5,4,5})
0+0+count(5, {1,2,4,5,6,5,4,5})
0+0+0+count(5, {2,4,5,6,5,4,5})
0+0+0+0+count(5, {4,5,6,5,4,5})
0+0+0+0+0+count(5, {5,6,5,4,5})
0+0+0+0+0+1+count(5, {6,5,4,5})
0+0+0+0+0+1+0+count(5, {5,4,5})
0+0+0+0+0+1+0+1+count(5, {4,5})
0+0+0+0+0+1+0+1+0+count(5, {5})
0+0+0+0+0+1+0+1+0+1+count(5,{})
0+0+0+0+0+1+0+1+0+1+0  <---The last 0 is the base case
3

---

如果您允许更改函数说明，你也可以做一些酷的称为尾递归。而不是 return 1 + count（...），添加累积的数量，直到计数器计数： int count（int number，int array []，int length，int acc）

---

If you are allowed to change the function specification, you can do also something cool called tail recursion. Instead of return 1 + count(...), add the accumulated number so far as a paremeter to count: int count(int number, int array[], int length, int acc)

）或 return count（...，acc + 0）。一些编译器然后能够进行尾调用优化，将其转换为编译代码中的循环。与常规递归相比，这可以节省内存。

And do return count(..., acc+1) or return count(..., acc+0). Some compilers are then able to do tail call optimization , transforming it into a loop in the compiled code. This saves memory compared to a regular recursion.

这篇关于数字在数组中出现的次数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！